Cover by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

O'Reilly logo

AlphaBeta

The Minimax algorithm properly evaluates a player's best move when considering the opponent's countermoves. However, this information is not used while the game tree is generated! Consider the BoardEvaluation scoring function introduced 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 Minimax plods 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. Minimax takes 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 unproductive searches from the search tree. Using AlphaBeta, the equivalent expansion of the game tree is shown in Figure 7-21.

AlphaBeta fact sheet

Figure 7-20. AlphaBeta fact sheet

AlphaBeta two-ply search

Figure 7-21. AlphaBeta two-ply search

As AlphaBeta searches 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, AlphaBeta determines that X has at least one countermove that ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required