MinMax Trees - When Min Can Win Two Steps

Question

So, I played with minmax trees to create a simple computer player in a dual-player board game. I understand the basics of the algorithm, but there is a case that eludes my intuitive brain infusion ... what happens when MIN can win in two stages?

For example, suppose a game is like connect4 / tic-tac-toe, where only one of the two players can have a square. How to get MAX to occupy a square solely to prevent MIN from getting a square?

Try a simplified example (shown in elegant ASCII text), where the options are Left and Right. Suppose the tree is too large to travel to its final states, so the intermediate values ​​are calculated based on the heuristic function (indicated * below). -INF is the state of the terminal in which MIN wins.

MAX (a) / \ AB / \ MIN (b) MIN (c) / \ / \ ABAB / | | \ -INF *5 *22 *20 

MIN is about to choose action A in state (b) to evaluate -INF
MIN is about to select action B in state (c) to estimate +20
MAX is about to select action B in state (a) for a score of +20

The problem, of course, is that if MAX chooses B, then MIN will perform action A (since this square is still available), and thus MIN will win. I need to get MAX in order to implement the walking action value A in state (a), to prevent MIN from getting -INF next turn.

I would put a bunch of tests in 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 part in determining the value with respect to the MAX that causes this.

(Edited for clarification)

Answer 1

Each node in the minimax tree is a complete game state. When a player selects an action, the game goes into this state, restricting the actions of both players (there is no way to select another action from another branch). So in your example, if in state (a) player Max chooses action B, the game is now in state C. The only two options for the minimum player at this point are A (22) and B (20). The depth of the tree does not matter; max and min players will always choose their best action from the current state of the game.

To play tic-tac-toe, each state must be a complete board (perhaps of course). For example, the first level will be every possible place where X can place its marker. Then each child from these states will be every possible place O can be placed, given the parental state (where X is placed), etc.

Heuristics are useful when you cannot imagine the entire game tree (for example, chess), but do not change how the minimax tree is used.

Answer 2

If the problem is related to the heuristic function. As you say, if MAX chooses B in state (a),

MIN will perform action A (since this square is still available), and thus MIN will win

but on the tree you mark this with * 22 not -Inf, as it should be (MIN wins).