CODEWITHSUNDEEP
pythonminimax
Pete
Pete

Reputation: 489

Minimax Algorithm Clarification

Sorry this may be a bad question, I am trying to implement a minimax algorithm, and I'm confused on how the 'scores' are created. Do I need to make a tree of every possible combination from a state all the way to a win condition, or just one layer, or not at all? EX.

X 0 _ #1
0 0 _ #2
X X _ #3

Would the states would be (X1),(X2),(X3) or (X2,01,X3),(X1,02,X3),(X3),(X2,03,X1)? And for scoring it, do I need to factor in depth at all, or am I just determining max/min score from that ONE depth?

Upvotes: 0

Views: 222

Answers (1)

Nevermore
Nevermore

Reputation: 7409

I think what you're asking about is whether you must traverse the entire tree to evaluate a position. Minimax is used for zero sum games, meaning one side will win and the other will lose (or draw). For a game like Tic Tac Toe it's quite possible to traverse the entire tree, up to the terminal state, and give a score:

  • 1 for the Max player winning
  • -1 for the Min player winning
  • 0 for a draw

For games where traversing the entire tree of all possible moves is too computationally expensive (like chess), you can set a terminal depth (say, 3 or 4 ply into the tree) and return the score of that position.

I think you're also asking whether the evaluation needs to take into account it's depth. The answer is no.

You might then be wondering, if you don't fully traverse the tree, how do you evaluate a position?

There are different ways, most important is to do something efficient (in order to go farther down the tree faster). For chess, sometimes just counting the material (piece) advantage is enough to produce a basic minimax scoring system.

see the chess programming wiki for some nice explanation: https://chessprogramming.wikispaces.com/Minimax

Upvotes: 1

Related Questions