Given a specific position in a game tree from the perspective of an initial player, a search program must find a move that leads to the greatest chance of victory (or at least a draw). Instead of considering only the current game state and the available moves at that state, the program must consider any countermoves that its opponent will make after it makes each move. The program must assume that the opponent will select its best move choice and make no mistakes. The program assumes there is an evaluation function `score(state`

, `player)`

that returns an integer representing the score of the game state from `player`

's perspective; smaller integer numbers (which may be negative) reflect weaker positions.

The game tree is expanded by considering future game states after a sequence of *n* moves have been made. Each level of the tree alternates between *MAX* levels (where the goal is to benefit the player by maximizing the evaluated score of a game state) and *MIN* levels (where the goal is to benefit the opponent by minimizing the evaluated score of a game state). At alternating levels, then, the program selects a move that maximizes `score(state`

, `initial)`

, but when the opponent is making its move, the program assumes the opponent is intelligent and so selects the move that minimizes `score(state`

, `initial)`

. Figure 7-15 illustrates the Minimax algorithm.

Figure 7-15. Minimax fact sheet

**Input/Output ...**

Start Free Trial

No credit card required