Algorithms in a Nutshell

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.

Figure 7-20. AlphaBeta fact sheet

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 ...