## Definition
**Alpha-beta pruning** is an optimisation of the [[Minimax Algorithm]] that prunes branches that *cannot* affect the final decision. Returns the same value as full minimax but explores dramatically fewer nodes.
## The Pruning Principle
Maintain two bounds during the search:
- **$\alpha$** — best value MAX is guaranteed so far (lower bound).
- **$\beta$** — best value MIN is guaranteed so far (upper bound).
When $\alpha \geq \beta$ at any node, the remaining children cannot influence the result — prune.
- At MIN nodes: $\alpha \geq \beta$ means MIN has already found a move worse for MAX than something MAX can guarantee elsewhere → MAX wouldn't enter this subtree.
- At MAX nodes: symmetric.
## Algorithm
```
function alphabeta(node, depth, α, β, player):
if depth = 0 or terminal: return evaluate(node)
if player = MAX:
value ← -∞
for each child of node:
value ← max(value, alphabeta(child, depth-1, α, β, MIN))
α ← max(α, value)
if α ≥ β: break # β-cutoff
return value
else:
value ← +∞
for each child of node:
value ← min(value, alphabeta(child, depth-1, α, β, MAX))
β ← min(β, value)
if α ≥ β: break # α-cutoff
return value
```
Initial call: `alphabeta(root, depth, -∞, +∞, MAX)`.
## Effectiveness
The number of nodes explored depends critically on **move ordering**:
- **Worst case** (random ordering): same as minimax — $O(b^d)$.
- **Best case** (perfect ordering — best moves first): $O(b^{d/2})$. Effectively doubles search depth for the same compute.
## Move Ordering Heuristics
To approach best-case pruning:
- **Iterative deepening** with previous-depth principal variation moves first.
- **Killer move heuristic** — moves that caused beta cutoffs at the same depth elsewhere are tried first.
- **History heuristic** — track moves that frequently produce cutoffs.
- **Static evaluation ordering** — try moves with the best static evaluation first.
A well-tuned ordering reaches ~70-90% of the theoretical best case.
## Transposition Tables
Cache previously computed minimax values for positions. Often the same position is reached by multiple move orders ("transpositions"); the cache avoids re-computation.
## Modern Variants
- **NegaMax** — clean reformulation that exploits symmetry of zero-sum.
- **NegaScout / PVS (Principal Variation Search)** — assumes the first move is best; cheaper null-window verifications for the rest.
- **Aspiration windows** — narrow the alpha-beta range for the next iteration based on the previous iteration's result.
## Limits
For games like Go ($b \approx 250$), even aggressive alpha-beta plus great move ordering wasn't enough — that's where [[Monte Carlo Tree Search]] (and later, deep learning) took over.
## Related
- [[Minimax Algorithm]]
- [[Evaluation Function]]
- [[Monte Carlo Tree Search]]