Algorithms in a Nutshell

(^218) | Chapter 7: Path Finding in AI
The game tree in Figure 7-21 shows the [α,β] values as ALPHABETAexecutes;
initially they are [–∞,∞]. With a two-ply search, ALPHABETAis trying to find the
best move for O when considering just the immediate countermove for X. Since
ALPHABETAis recursive, we can retrace its progress by considering a traversal of
the game tree. The first move ALPHABETAconsiders is for O to play in the
upper-left corner. After all five of X’s countermoves are evaluated, it is evident
that X can only ensure a score of –2 for itself (using the static evaluation
BoardEvaluationfor tic-tac-toe). When ALPHABETAconsiders the second move
for O (playing in the middle of the left column), its [α,β] values are now [–2,∞],
which means “the worst that O can end up with so far is a state whose score is
–2, and the best that O can do is still win the game.” When the first counter-
move for X is evaluated, ALPHABETAdetects that X has won, which falls outside
of this “window of opportunity,” so further countermoves by X no longer need
to be considered.
Figure 7-20. AlphaBeta fact sheet
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