Algorithms in a Nutshell

NegMax | 215

Path Finding

in AI

Consequences

NEGMAXis useful because it prepares a simple foundation on which to extend to

ALPHABETAif required. Because board scores are routinely negated in this algo-

rithm, we must be careful to choose values for the evaluation of winning and

losing states. Specifically, the minimum value must be the negated value of the

maximum value. Note that Integer.MIN_VALUE (in Java this is defined as

0x80000000or –2,147,483,648) is not the negated value ofInteger.MAX_VALUE(in

Java, defined as0x7fffffffor 2,147,483,647). For this reason, we useInteger.MIN_

VALUE+1 as the minimum value, which is retrieved by the static function

MoveEvaluation.minimum(). For completeness, we provideMoveEvaluation.maximum()

as well.

Analysis

Figure 7-19 contains a two-ply exploration of an initial tic-tac-toe game state for

player O using NEGMAX. Note that all possible game states are expanded, even

when it becomes clear that the opponent X can secure a win if O makes a poor

move choice. The scores associated with each of the leaf game states are evalu-

ated from that player’s perspective (in this case, the original player O). Note how

the score for the initial game state is –2, because that is the “maximum of the

negative scores of its children.”

The number of states explored by NEGMAXis the same as MINIMAX, or on the

order ofbd for ad-ply search with a fixed numberb of moves at each game state.

return new MoveEvaluation(player.eval(state));

}

// Try to improve on this lower-bound move.

MoveEvaluation best = new MoveEvaluation (MoveEvaluation.minimum( ));

// get moves for this player and generate the boards that result from

// making these moves. Select maximum of the negative scores of children.

while (it.hasNext( )) {

IGameMove move = it.next( );

move.execute(state);

// Recursively evaluate position using consistent negmax.

// Treat score as negative value.

MoveEvaluation me = negmax (ply-1, opponent, player);

move.undo(state);

if (-me.score > best.score) {

best = new MoveEvaluation (move, -me.score);

}

}

return best;

}

}

Example 7-7. NegMax implementation (continued)

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