Minimax with alphabeta pruning produces the same result as unpruned minimax, but with much greater efficiency. It typically reduces the effective branching factor to its square root, 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.
Further improvement can be achieved without sacrificing accuracy, by using ordering heuristics to search parts of the tree that are likely to force alphabeta cutoffs early. For example, moves that take pieces may be examined before moves that do not, or moves that have scored highly in earlier passes through the gametree analysis may be evaluated before others. Another common, and very cheap, heuristic is the killer heuristic, where the last move that caused a betacutoff at the same level in the tree search is always examined first. This idea can be generalised into a set of refutation tables[?].
Alphabeta search can be made even faster still by only considering 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.
Clike pseudocode is given below
evaluate (node, alpha, beta) if node is a leaf return the heuristic value of node if node is a maximizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return alpha return beta if node is a minimizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return beta return alpha
See also:
Search Encyclopedia
