Algorithms in a Nutshell

(^210) | Chapter 7: Path Finding in AI
TheMAXand MINselectors simply evaluate scores to properly select the
minimum or maximum score as desired. This implementation is simplified by
defining anIComparatorinterface, shown in Figure 7-16, which definesMAXand
MINand consolidates how they select the best move from their perspective.
Switching between theMAXandMINselector is done using theopposite( )
method. The worst score for each of these comparators is returned by
initialValue( ); the actual value is different forMAX andMIN.
public IGameMove bestMove (IGameState s,
IPlayer player, IPlayer opponent) {
this.original = player;
this.state = s.copy( );
MoveEvaluation me = minimax(ply, IComparator.MAX,
player, opponent);
return me.move;
}
private MoveEvaluation minimax (int ply, IComparator comp,
IPlayer player, IPlayer opponent) {
// If no allowed moves or a leaf node, return game state score.
Iterator it = player.validMoves(state).iterator( );
if (ply == 0 || !it.hasNext( )) {
return new MoveEvaluation (original.eval(state));
}
// Try to improve on this lower bound (based on selector).
MoveEvaluation best = new MoveEvaluation (comp.initialValue( ));
// Generate game states that result from all valid moves
// for this player.
while (it.hasNext( )) {
IGameMove move = it.next( );
move.execute(state);
// Recursively evaluate position. Compute Minimax and swap
// player and opponent, synchronously with MIN and MAX.
MoveEvaluation me = minimax (ply-1, comp.opposite( ),
opponent, player);
move.undo(state);
// Select maximum (minimum) of children if we are MAX (MIN)
if (comp.compare(best.score, me.score) < 0) {
best = new MoveEvaluation (move, me.score);
}
}
return best;
}
}
Example 7-6. Minimax Java 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