Alpha-beta pruning
|
|
Alpha-beta pruning is a technique to reduce the number of nodes evaluated by the minimax algorithm for two-player games. It prunes out parts of the search tree that are so good for one player that the opponent will never allow them to be reached.
| Contents |
Improvements over Minimax
The benefit of alpha-beta pruning lies in the fact that branches of the search tree can be eliminated. The search can in this way be limited to the 'more promising' subtree. As its predecessor it belongs to the Branch and Bound class of algorithms. The optimisation typically reduces the effective branching factor to the square root compared to Minimax, or equivalently doubles the number of ply that can be searched in a given time.
The algorithm maintains two values, alpha and beta, which represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. Initially alpha is minus infinity and beta is plus infinity. As the recursion progresses the "window" becomes smaller. When beta becomes less than alpha, it means that the current position cannot be the result of best play by both players and hence need not be explored further.
Heuristic improvements
Further improvement can be achieved without sacrificing accuracy, by using ordering heuristics to search parts of the tree that are likely to force alpha-beta cutoffs early. For example, in chess, moves that take pieces may be examined before moves that do not, or moves that have scored highly in earlier passes through the game-tree analysis may be evaluated before others. Another common, and very cheap, heuristic is the killer heuristic, where the last move that caused a beta-cutoff at the same level in the tree search is always examined first. This idea can be generalised into a set of refutation tables.
Alpha-beta search can be made even faster by considering only a narrow search window (generally determined by guesswork based on experience), but this will be at the expense of accuracy, if any of the true values of the position lie outside the window. If this happens, the search must be performed again with a larger window. This is known as aspiration search. In the extreme case, the search is performed with alpha and beta equal; a technique known as zero-window search or scout search. If an aspiration search fails, it is straightforward to detect whether it failed high (high edge of window was too low) or low (lower edge of window was too high). This gives information about what window values might be useful in a re-search of the position.
Other algorithms
More advanced algorithms that are even faster still while still being able to compute the exact minimax value are known: PVS, Negascout and MTD-f.
Since the minimax algorithm and its variants are inherently depth-first, a strategy such as iterative deepening is usually used in conjunction with alpha-beta so that a reasonably good move can be returned even if the algorithm is interrupted before it has finished execution. Another advantage of using iterative deepening is that searches at shallower depths give move-ordering hints that can help produce cutoffs for higher depth searches much earlier than would otherwise be possible.
Algorithms like SSS-star, on the other hand, use the best-first strategy. This can potentially make them more time-efficient, but typically at a heavy cost in space-efficiency.
Pseudocode
pseudocode for the alpha-beta algorithm is given below
evaluate (node, alpha, beta)
if node is a leaf
return the heuristic value of node
if node is a minimizing node
for each child of node
beta = min (beta, evaluate (child, alpha, beta))
if beta <= alpha
return alpha
return beta
if node is a maximizing node
for each child of node
alpha = max (alpha, evaluate (child, alpha, beta))
if beta <= alpha
return beta
return alpha
See also
External references
- http://www.maths.nott.ac.uk/personal/anw/G13GAM/alphabet.html
- http://chess.verhelst.org/search.html
- http://www.computerchess.us/gtchess (chess program with alpha-beta source code)