MinMax trees - when Min can win in two steps

Question

So, I have been playing around with min-max trees to create a simple computer player in a two-person board game. I understand the basics of the algorithm, but there is a case that eludes my turkey infused brain ... what happens when MIN can win in two steps?

For example, assume a connect4/tic-tac-toe type game where only one of the two players can own a square. How do I get MAX to occupy a square solely to prevent MIN from getting the square?

Let's try a simplified example (shown in nifty ASCII art) where the options are Left and Right. Assume the tree is too big to traverse to the terminal states, so intermediate values are calculated based on a heuristics function (marked with * below). -INF is a terminal state where MIN wins.

                MAX (a)             

                /   \

               A     B

              /       \

           MIN (b)    MIN (c)     

           /  \     / \

          A    B A    B

         /     | |     \

      -INF    *5 *22    *20

MIN is going to pick action A in the state (b) for a score of -INF

MIN is going to pick action B in the state (c) for a score of +20

MAX is going to pick action B in the state (a) for a score of +20

The problem - of course - is that if MAX picks B then MIN will perform action A (since that square is still available) and thus MIN will win. I need to get MAX to realize the value of picking action A in the state (a) to prevent MIN from getting -INF in the next move.

I would put a bunch of tests into the code to check if MIN can win, but it seems to me that the algorithm should take care of this. I think I am missing a piece in the determination of the value with regards to MAX which is causing this.

Answer 1

Each node in the minimax tree is a whole game state. When a player picks an action, the game moves to that state, restricting the actions of both players (there is no way to pick another action from another branch). In your example, if in the state (a) player Max chooses action B, the game is now in state C. The only two choices for the min player at this point are A(22) and B(20). We don't have to concern about the depth of the tree as the max and min players will always pick their best action from the current state of the game.

In the tic-tac-toe game, a player tries to ensure two cases:

• Maximize a player’s chances of a win

• Minimize the opponent’s chances of a win

Maximize profit: The profit can be maximized by either fork or win

Fork: Initially the player will create an opportunity where he can win in two ways.

Win: If there two same X or O in a row, then play the third to get three in a row.

Minimize Loss: The loss can be minimized by a block.

Block: If two ‘x’ or ‘o’ of the opponent is in a row then block it, or else block the opponent’s fork.