Algorithms in a Nutshell

(^222) | Chapter 7: Path Finding in AI
Consequences
Since the resulting moves will be exactly the same as if MINIMAXhad executed,
the primary consequence is reduced execution time, since a number of states are
going to be removed from the expanded game tree.
Analysis
Because ALPHABETA returns the same computed move as MINIMAX and
NEGMAX, one way to measure the benefit of ALPHABETAis to determine the
savings from the size of the game tree. This task is complicated because ALPHA-
BETAwill show its most impressive savings if the opponent’s best move is
evaluated first whenever ALPHABETAexecutes. When there is a fixed numberbof
moves at each game state, the total number of potential game states to search in a
d-ply ALPHABETAis on the order ofbd. If the moves are ordered by decreasing
public IGameMove bestMove (IGameState s,
IPlayer player, IPlayer opponent) {
this.state = s.copy( );
MoveEvaluation move = alphabeta(ply, player, opponent,
MoveEvaluation.minimum( ), MoveEvaluation.maximum( ));
return move.move;
}
private MoveEvaluation alphabeta (int ply, IPlayer player, IPlayer opponent,
int alpha, int beta) {
// If no moves, return evaluation of board from player's perspective.
Iterator it = player.validMoves(state).iterator( );
if (ply == 0 || !it.hasNext( )) {
return new MoveEvaluation (player.eval(state));
}
// Select "maximum of negative value of children" that improves alpha
MoveEvaluation best = new MoveEvaluation (alpha);
while (it.hasNext( )) {
IGameMove move = it.next( );
// Recursively evaluate position.
move.execute(state);
MoveEvaluation me = alphabeta (ply-1, opponent, player, -beta, -alpha);
move.undo(state);
// If improved upon alpha, keep track of this move.
if (-me.score > alpha) {
alpha = -me.score;
best = new MoveEvaluation (move, alpha);
}
if (alpha >= beta) { return best; } // search no longer productive.
}
return best;
}
}
Example 7-8. AlphaBeta 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