Alpha–beta pruning is an algorithm that reduces the work required by minimax search. It avoids exploring branches of a game tree once available information establishes that they cannot improve the relevant decision. For a fixed tree and leaf evaluations, it preserves the minimax value at the root while potentially examining far fewer positions. It is a standard technique in artificial intelligence for adversarial game playing. (cs.cornell.edu)
Minimax setting
The standard setting is a deterministic, two-player, zero-sum game with perfect information. Scores are expressed from one player’s perspective: MAX chooses the highest-valued continuation, while MIN chooses the lowest. Minimax propagates these choices upward from leaf positions to determine the root value. (aima.cs.berkeley.edu)
Search may continue to terminal positions, whose scores represent game outcomes, or stop at a depth limit. In the latter case, a heuristic evaluation function estimates the value of nonterminal positions. Alpha–beta pruning preserves the result of that depth-limited minimax calculation; it does not make the estimates exact or establish an optimal strategy for the entire game. (cs.cornell.edu)
Bounds and cutoffs
The algorithm carries two bounds along the current search path:
- Alpha ((\alpha)) records the best, highest-valued alternative established so far for MAX.
- Beta ((\beta)) records the best, lowest-valued alternative established so far for MIN.
Initially, (\alpha=-\infty) and (\beta=+\infty). At a MAX node, newly discovered values can increase alpha; at a MIN node, they can decrease beta. When (\alpha\geq\beta), the remaining children can be skipped: an ancestor already has an alternative at least as good as anything the current continuation could offer it. (aima.cs.berkeley.edu)
For example, suppose MAX has already found a move worth 5. Another move leads to a MIN node whose first examined child is worth 3. That MIN node’s value can be no greater than 3, regardless of its remaining children. MAX therefore cannot improve on 5 through this move, so those children need not be examined. This illustrates a cutoff without determining the discarded node’s exact value. (cs.cornell.edu)
Algorithm
A depth-limited implementation can use recursion to alternate MAX and MIN. The following pseudocode assumes that every nonterminal node has legal successors and that all evaluations use MAX’s perspective. (cs.cmu.edu)
alpha_beta(node, depth, alpha, beta, maximizing):
if terminal(node):
return utility(node)
if depth == 0:
return evaluate(node)
if maximizing:
value = -infinity
for child in successors(node):
score = alpha_beta(child, depth - 1,
alpha, beta, false)
value = max(value, score)
alpha = max(alpha, value)
if alpha >= beta:
break
else:
value = +infinity
for child in successors(node):
score = alpha_beta(child, depth - 1,
alpha, beta, true)
value = min(value, score)
beta = min(beta, value)
if alpha >= beta:
break
return value
The initial call uses an unrestricted window, ((-\infty,+\infty)). Calls with narrower windows may establish only a bound rather than an exact value. A cutoff result must therefore not automatically be interpreted as the true minimax value of that internal node. (webdocs.cs.ualberta.ca)
Complexity and move ordering
The time complexity depends strongly on successor ordering. For a uniform tree with branching factor (b) and depth (d), the worst case remains (O(b^d)): values can be arranged so that no useful cutoffs occur. With optimal ordering, the number of evaluated leaves is
[ b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1. ]
For even depths, this is (2b^{d/2}-1), conventionally summarized using Big-O notation as (O(b^{d/2})). The exact expression also captures the difference between odd and even depths. (webdocs.cs.ualberta.ca)
Good ordering examines promising moves early—high-valued moves for MAX and low-valued moves for MIN—so that useful bounds become available sooner. Under favorable ordering, alpha–beta can search roughly twice as deeply as ordinary minimax for a comparable amount of work; this is not a worst-case guarantee. (aima.cs.berkeley.edu)
Historical analysis
Donald E. Knuth and Ronald W. Moore’s 1975 paper, An Analysis of Alpha-Beta Pruning, presented the algorithm, proved its correctness, discussed its historical development, and analyzed its behavior under several assumptions about game-tree values. (sciencedirect.com)
References
- Minimax search and alpha-beta pruningcs.cornell.edu
- Chapter 6: Adversarial Searchaima.cs.berkeley.edu
- Alpha-beta searchcs.cmu.edu
- An Analysis of Alpha-Beta Pruningwebdocs.cs.ualberta.ca