Algorithms in a Nutshell

NegMax

The NegMax algorithm replaces the alternative MAX and MIN levels of Minimax with a single approach used at each level of the game tree. It also forms the basis for the AlphaBeta algorithm presented next. In Minimax, the game state is always evaluated from the perspective of the player making the initial move (which requires that this piece of information is stored for use within the evaluation function).

Instead of viewing a game tree as alternating levels where the original player must maximize its score or minimize its opponent's score, NegMax consistently seeks the move that produces the maximum of the negative values of a state's children nodes. Intuitively, after a player has made its move, the opponent will try to make its best move; thus, to find the best move for a player, select the one that restricts the opponent from scoring too highly. If you compare the pseudocode examples in Figures 7-15 and 7-18, you will see two identical game trees in Minimax and in NegMax; the only difference is how the game states are scored. Note that the first of the two available moves for the original player is the best choice, since the opponent is restricted the most.

Figure 7-18. NegMax fact sheet

Input/Output

Input and output are the same as for Minimax.

Context

Context is the same as for Minimax.

Solution

In Example 7-7, note that the score for each MoveEvaluation is simply the evaluation ...