Algorithms in a Nutshell

AlphaBeta | 223

Path Finding

in AI

favorability (i.e., the best move first), then we still have to evaluate allbchildren

for the initiating player (since we are to choose his best move); however, in the

best case we only need to evaluate the first move by the opponent. Note in

Figure 7-21 that, because of move ordering, the prune occurs after several moves

have been evaluated, so the move ordering for that game tree is not optimal.

In the best case, therefore, ALPHABETAevaluatesbgame states for the initial

player on each level, but only one game state for the opponent. So, instead of

expandingb*b*b*...*b*b(a total ofdtimes) game states on thedthlevel of the game

tree, ALPHABETAmay require onlyb*1*b*...*b*1 (a total ofdtimes). The resulting

number of game states isbd/2, an impressive savings.

Instead of simply trying to minimize the number of game states, ALPHABETA

could explore the same total number of game states as MINIMAX, but instead this

would extend the depth of the game tree to 2*d, thus doubling how far ahead the

algorithm can look.

To empirically evaluate MINIMAXand ALPHABETA, we construct a set of initial

tic-tac-toe board states that are possible afterkmoves have been made. We then

compute MINIMAXand ALPHABETAwith a ply ofd=9–k, which ensures all

possible moves are explored. The results are shown in Table 7-5. Observe the

significant reduction of explored states using ALPHABETA.

Individual comparisons show the dramatic improvement of ALPHABETAand

some of these cases explain why ALPHABETA is so powerful. On the game state:

ALPHABETAexplores only 47 game states (instead of 8,232 for MINIMAX, a 99.4%

reduction) to determine that player X should select the center square, after which

a win is assured. However, the only way to achieve such deep reductions is if the

available moves are ordered such that the best move appears first. Since our tic-

tac-toe solution does not order moves, some anomalies will result. For example,

given the same board state rotated 180 degrees:

ALPHABETA will explore 960 game states (an 88.3% reduction).

Table 7-5. Statistics comparing Minimax versus AlphaBeta

k Minimax states AlphaBeta states Aggregate reduction Individual variation

1 549,945 27,565 95% ±1.3%

2 549,936 47,508 91% ±6.8%

3 549,864 112,086 80% ±10.2%

X Ο

Ο X

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