Alpha-Beta Pruning

Alpha-beta pruning never expands a node whose value can't affect the root's minimax value. Same answer as minimax; often expands many fewer nodes.

Algorithm

``` function alphabeta(state, depth, alpha, beta, maximizing): if state is terminal or depth == 0: return utility(state) if maximizing: v = -infinity for action in actions(state): v = max(v, alphabeta(result, depth-1, alpha, beta, False)) alpha = max(alpha, v) if beta <= alpha: break # beta cutoff return v else: v = infinity for action in actions(state): v = min(v, alphabeta(result, depth-1, alpha, beta, True)) beta = min(beta, v) if beta <= alpha: break # alpha cutoff return v ```

$\alpha$ is the best value max can guarantee so far. $\beta$ is the best value min can guarantee so far. If $\beta \leq \alpha$, the current subtree is irrelevant — the opponent won't let the search reach it.

Why it works

If a min node finds a child with value $\leq \alpha$, max's parent will already prefer the value $\alpha$ over anything this min node can guarantee. No need to expand the rest. Symmetric argument for the alpha cutoff.

Time complexity

• Worst case: $O(b^m)$ — same as minimax (when move ordering puts the worst moves first).
• Best case: $O(b^{m/2})$ — when the best move is always tried first at every node. Doubles the effective search depth for the same compute.

Move ordering

The single biggest determinant of alpha-beta's effective performance. Heuristics:

• Killer move: if move M caused a cutoff at a sibling node, try M first at this node.
• History heuristic: track how often each move has caused cutoffs across the search; try high-history moves first.
• Transposition table: cache evaluations from prior nodes (transpositions are common in chess). If the cached value yields an immediate cutoff, you save the entire subtree.
• Static ordering: in chess, captures and checks first — they often produce big swings.

Iterative deepening + alpha-beta

The standard chess engine pattern:

1. Search to depth 1, get a value. 2. Search to depth 2, using results from depth 1 to order moves. 3. Continue until time runs out. 4. Return the best move from the deepest completed depth.

This combines anytime behavior (you can stop at any time and have a reasonable move) with the move-ordering benefits of having shallower results.