Algorithms in a Nutshell

AlphaBeta | 217

Path Finding

in AI

NEGMAXstreamlines the algorithm since there is no longer a need to alternate

betweenMAXandMINnodes evaluating the common state function. Recall how

MINIMAXrequired the scoring function to always be evaluated from the perspec-

tive of the player for whom the initial move is desired? In NEGMAX,itis

imperative that the game state is evaluated based upon the player making the

move. The reason is that the search algorithm selects the child node that is “the

maximum of the negative value of all children.”

AlphaBeta

The MINIMAXalgorithm properly evaluates a player’s best move when consid-

ering the opponent’s countermoves. However, this information is not used while

the game tree is generated! Consider theBoardEvaluationscoring function intro-

duced earlier. Recall Figure 7-17, which shows the partial expansion of the game

tree from an initial game state after X has made two moves and O has made just

one move.

Note how MINIMAXplods along even though each of the subsequent searches

reveals a losing board if X is able to complete the diagonal. A total of 36 nodes is

evaluated. MINIMAXtakes no advantage of the fact that the original decision for

O to play in the upper-left corner prevented X from scoring an immediate victory.

Instead of seeking ad-hoc strategies to use past information found during the

search, ALPHABETA(Figure 7-20) defines a consistent strategy to prune unpro-

ductive searches from the search tree. Using ALPHABETA, the equivalent

expansion of the game tree is shown in Figure 7-21.

As ALPHABETAsearches for the best move, it remembers that X can score no

higher than 2 if O plays in the upper-left corner. For each subsequent other move

for O, ALPHABETAdetermines that X has at least one countermove that outper-

forms the first move for O (indeed, in all cases X can win). Thus, the game tree

expands only 16 nodes (a savings of more than 50% from MINIMAX). More

importantly, there is no need to compute potential moves and modify state when

the end result is not going to matter.

ALPHABETAselects the same move that MINIMAXwould have selected, with

potentially significant performance savings. As with the other path-finding algo-

rithms already described in this chapter, ALPHABETAassumes that players make

no mistakes, and it avoids exploring parts of the game tree that will have no

impact on the game under this assumption.

ALPHABETArecursively searches through the game tree and maintains two values,

αandβ, that define a “window of opportunity” for a player as long asα<β. The

valueαrepresents the lower bound of the game states found for the player so far

(or –∞if none have been found) and declares that the player has found a move to

ensure it can score at least that value. Higher values ofαmean the player is doing

well; whenα=+∞, the player has found a winning move and the search can termi-

nate. The valueβrepresents the upper bound of game states so far (or +∞if none

have been found) and declares the maximum board that the player can achieve.

Whenβdrops lower and lower, it means that the opponent is doing better at

restricting the player’s options. Since ALPHABETAhas a maximum ply depth beyond

which it will not search, any decisions that it makes are limited to this scope.

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