Algorithms in a Nutshell

NegMax | 213

Path Finding

in AI

MINcomputes aminValuethat determines the lowest achievable score that player

MINcan ensure.MINcan stop searching aMAXsubtree once playerMAXis able

to counter with a move whose resulting game state evaluates to greater than this

minValue. Instead of trying to deal with both of these cases (one forMINand one

forMAX), we first discuss an alternate arrangement for evaluating the game tree

that uses a consistent approach, regardless of level in the game tree.

Variations

The ply depth can be eliminated if the game tree is small enough to be repre-

sented completely in memory.

NegMax

The NEGMAX algorithm replaces the alternativeMAX and MIN levels of

MINIMAXwith a single approach used at each level of the game tree. It also forms

the basis for the ALPHABETAalgorithm 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, NEGMAXconsistently 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 MINIMAXand 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.

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 eachMoveEvaluationis simply the evalua-

tion of the game state from the perspective of the player making that move.

Reorienting each evaluation toward the player making the move simplifies the

algorithm implementation.

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use