Algorithms in a Nutshell

AlphaBeta | 221

Path Finding

in AI

Player’s turn

Assume O plays in the middle of the left column and X responds by playing

in the middle of the top row (this is the leftmost grandchild of the root node

in the search tree). Now, from O’s perspective, the best score that O can

force is –1 (note that in the diagram the scores are shown as 1 since ALPHA-

BETAuses NEGMAXto score its children). This value is remembered when

we try to determine what O can achieve if X had instead countered by playing

in the middle of the bottom row. Note that [α,β] is now [–∞,–1]. ALPHABETA

evaluates the result when O plays in the middle of the top row and computes

the score 1. Since this value is greater than or equal to the –1 value, the

remaining three potential moves for O in this level are ignored.

Opponent’s turn

Assume O plays in the middle of the left column and X responds by playing

in the upper-right corner, immediately winning the game. ALPHABETAdoes

not have to consider X’s two other potential moves, since O will prune the

remaining search nodes in the search subtree “rooted” in the decision to play

in the middle of the left column.

The pruning of the search occurs whenα≥β, or in other words, when the

“window of opportunity” closes. When ALPHABETAis based on MINIMAX, there

are two ways to prune the search, known asα-prune andβ-prune; in the simpler

ALPHABETAbased on NEGMAX, these two cases are combined into the one

discussed here. Because ALPHABETAis recursive, the range [α,β] represents the

window of opportunity for the player, and the window of opportunity for the

opponent is [–β,–α]. Within the recursive invocation of ALPHABETAthe player

and opponent are swapped, and the window is similarly swapped. ALPHABETA

always returns the same move that MINIMAX(or NEGMAX, for that matter)

would have returned; it just requires less expansion of the game tree. ALPHABETA

still seeks to expand a tree to a fixed depth, and so in this regard it behaves simi-

larly to DEPTH-FIRSTSEARCH.

Input/Output

Input and output are the same as for MINIMAX. The primary distinction is that

ALPHABETAtakes advantage of the calculated states when determining whether

to continue searching a particular subtree.

Solution

The ALPHABETAimplementation shown in Example 7-8 augments NEGMAXby

terminating early the evaluation of a set of game states once it becomes clear that

either the player can’t guarantee a better position (theα-prune) or the opponent

can’t force a worse position (theβ-prune).

Example 7-8. AlphaBeta implementation

public class AlphaBetaEvaluation implements IEvaluation {

IGameState state; /** State to be modified during search. */

int ply; /** Ply depth. How far to continue search. */

public AlphaBetaEvaluation (int ply) { this.ply = ply; }

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