Minimax, Alpha–Beta & Game-Tree Search

Game-tree search asks a different question from ordinary pathfinding: not “what happens if I choose this action?” but “what happens after I choose it and an opponent chooses the most damaging reply?” Minimax makes that recursive dependence precise. Alpha–beta search computes the same minimax decision while omitting subtrees that cannot change it.

The clean theory applies to a finite, deterministic, alternating-turn, two-player, zero-sum game with perfect information. Chess end positions, tic-tac-toe, and many abstract board games fit this model once draw and repetition rules are included in the state. Chance, hidden information, simultaneous actions, more than two players, or non-zero-sum payoffs require different models; treating them as minor implementation details gives the wrong objective.

Shannon's 1950 chess paper established the enduring engineering tension between searching every move to a limited depth and selectively extending promising lines. Modern engines add sophisticated control around the same recursive core, but the correctness boundary between exact pruning and heuristic selectivity still matters.

Minimax semantics #

Let $s$ be a game state, $A(s)$ its legal actions, and $T(s,a)$ the successor after action $a$. Define terminal utility $u(s)$ from Max's perspective: larger is better for Max and smaller is better for Min. Then

$$V(s)= \begin{cases} u(s), & s\text{ is terminal},\\[4pt] \max\limits_{a\in A(s)} V(T(s,a)), & \text{Max to move},\\[8pt] \min\limits_{a\in A(s)} V(T(s,a)), & \text{Min to move}. \end{cases}$$

The recurrence is not a prediction that the opponent will choose a likely move. It defines the value that Max can guarantee against an optimal adversary. At a Max node, one action is under Max's control, so the best child is chosen. At a Min node, Max must withstand the least favorable child because Min controls the choice.

The recursive implementation follows the definition directly:

def minimax(state):
    if terminal(state):
        return utility_for_max(state)

    values = [minimax(play(state, move)) for move in legal_moves(state)]
    return max(values) if max_to_move(state) else min(values)

A correctness proof is structural induction on the remaining game depth. Terminal states are correct by the definition of utility. If all child values are correct, choosing their maximum at a Max state or minimum at a Min state is exactly the value of optimal play at the parent. Finiteness provides the well-founded recursion needed for termination.

In a symmetric zero-sum representation, values can instead be measured from the player-to-move's perspective. Switching turns negates the perspective, giving negamax:

$$N(s)=\max_{a\in A(s)}\bigl(-N(T(s,a))\bigr).$$

Negamax removes duplicated Max/Min code, but only if the evaluation, terminal utility, and sign change all use the same perspective. Many game-search bugs are not search bugs at all; they are inconsistent value conventions.

Alpha and beta are proof bounds #

Plain minimax explores every reachable leaf to its horizon. Alpha–beta search carries an interval $(\alpha,\beta)$ describing which results can still matter to ancestors:

• $\alpha$ is a lower bound on the value Max can already force along the current path;
• $\beta$ is an upper bound on the value Min can already force along the current path.

At a Max node, each examined child can raise $\alpha$. At a Min node, each examined child can lower $\beta$. When $\alpha\ge\beta$, the current subtree cannot affect the ancestor's choice, so its remaining children may be skipped.

def alphabeta(state, depth, alpha, beta, maximizing):
    if terminal(state):
        return utility_for_max(state)
    if depth == 0:
        return evaluate_for_max(state)

    if maximizing:
        value = float("-inf")
        for move in ordered_moves(state):
            child = play(state, move)
            value = max(value,
                        alphabeta(child, depth - 1, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value

    value = float("inf")
    for move in ordered_moves(state):
        child = play(state, move)
        value = min(value,
                    alphabeta(child, depth - 1, alpha, beta, True))
        beta = min(beta, value)
        if beta <= alpha:
            break
    return value

An initial full-window call uses $\alpha=-\infty$ and $\beta=+\infty$. The pseudocode is fail-soft: after a cutoff it returns the best value actually observed, which may lie outside the requested window. Such a return is sufficient as a bound, but it is not automatically an exact value. That distinction becomes essential when results are cached.

Worked pruning trace #

Suppose the root is a Max node with two moves, A and B. Each leads to a Min node:

• A has terminal children with utilities 3 and 5;
• B has terminal children with utilities 2 and 9.

Search A first, then B from left to right.

Why is the last step safe? B is a Min node. Once one child has value 2, examining more children can only leave B's minimum at 2 or lower; it can never raise the minimum above 2. The root already has an alternative worth 3. Therefore no unseen child under B can make B preferable to A.

This argument generalizes. The alpha–beta invariant records a choice already available to an ancestor and a bound on what the current subtree can return. A cutoff occurs only when those facts prove the current subtree irrelevant. Knuth and Moore's analysis formalizes that alpha–beta returns the same root result as full minimax over the same finite tree.

Alpha–beta is therefore closer to branch and bound than to guesswork: it prunes with a proof inequality. Unlike ordinary optimization, however, the bound directions alternate because control alternates between Max and Min.

Move order changes work, not the answer #

For a uniform tree with branching factor $b$ and depth $d$, full minimax examines $b^d$ leaves. Alpha–beta's result is independent of move order, but its work is not.

The exact ideal-order count assumes a uniform alternating tree with no transpositions and the favorable ordering analyzed by Knuth and Moore. Real games have varying branching factors, repeated states, terminal nodes at different depths, and heuristic reductions, so the formula is a model rather than a runtime promise.

Good ordering tries moves likely to establish a cutoff first: the principal-variation move from the previous iteration, a transposition-table move, forcing captures or threats, and moves with strong historical cutoff statistics. Provided the ordering remains a permutation of all legal moves, it may be arbitrarily heuristic without harming full-depth alpha–beta correctness, because every skipped subtree is still justified by an alpha–beta inequality. It changes when the proof is found, not what constitutes a proof.

Finite horizons and evaluation #

Most interesting games cannot be searched to terminal states. A depth-limited search replaces terminal utility at the horizon with a heuristic evaluation $e(s)$:

$$V_d(s)= \begin{cases} u(s), & s\text{ is terminal},\\ e(s), & d=0,\\ \max V_{d-1}(\text{child}), & \text{Max to move},\\ \min V_{d-1}(\text{child}), & \text{Min to move}. \end{cases}$$

Alpha–beta still computes $V_d$ exactly for the declared evaluator and horizon. It does not make $V_d$ equal to the true game-theoretic value. That depends on search depth and evaluation quality.

The cutoff creates the horizon effect: a decisive event just beyond depth $d$ can be invisible, or a forced loss can be postponed past the horizon and appear avoided. Quiescence search mitigates this by continuing from tactically unstable horizon states through a restricted set of forcing actions until a quieter evaluation point is reached. The restriction and a depth or repetition guard are necessary—“search until quiet” is not a termination proof. Current Stockfish search code enters quiescence search after its main depth is exhausted.

Selective pruning and reductions must be classified separately:

• Alpha–beta cutoff: exact for the current tree and evaluation because a bound proves irrelevance.
• Domain proof: exact when a game-specific dominance, symmetry, or tablebase fact is valid.
• Heuristic pruning or reduction: may miss the fixed-depth minimax move; justified by empirical playing strength or resource constraints, not by the alpha–beta theorem.

Calling all three “pruning” hides which decisions preserve exactness.

Iterative deepening and search windows #

Iterative deepening searches depths $1,2,3,\ldots$ rather than starting with the deepest target. Repeating shallower work seems wasteful, but it produces three practical benefits:

1. the last completed iteration supplies a legal move if the time budget expires;
2. its principal variation gives excellent move ordering for the next depth; and
3. its search results seed the transposition table.

Under interruption, an engine should retain the last fully completed iteration. Values from an abandoned iteration may be partial bounds rather than a coherent root decision.

An aspiration window starts the next iteration with a narrow interval around the previous score instead of $(-\infty,+\infty)$. A narrow window produces earlier cutoffs. If the true score is no greater than $\alpha$ (fail-low) or at least $\beta$ (fail-high), the engine widens the window and searches again. This is a performance optimization: accepting the failed-window result as exact would be a correctness error. Stockfish's iterative-deepening loop uses previous principal variations, aspiration windows, and re-searches after fail-low or fail-high outcomes.

The game is usually a graph, not a tree #

Different move sequences can reach the same state—a transposition. A transposition table turns repeated tree search into graph search by caching results under a position key. A useful record contains at least:

For an original window $(\alpha_0,\beta)$, a fail-soft result is conventionally classified as:

• upper bound if the result is $\le\alpha_0$ (fail-low);
• lower bound if the result is $\ge\beta$ (fail-high);
• exact only if it lies strictly inside the window and the node was fully resolved under the search's rules.

A lower bound can justify a beta cutoff; an upper bound can justify an alpha cutoff. Treating either as an exact value corrupts ancestor choices. Production search code consequently stores both depth and a bound flag, as the Stockfish source demonstrates.

The table's reuse contract must account for every fact that changes legal moves or terminal status: side to move, special move rights, and history used by repetition or draw rules. Those facts may be encoded in the key or handled by a separate check that restricts when a cached result is reusable. Two identical-looking boards can have different values if one is an immediate repetition draw and the other is not. Hash collisions also require a deliberate correctness strategy; silently trusting an insufficient fingerprint can turn a cache optimization into illegal pruning.

Cycles require terminal handling independent of the recursive tree shape. Repetition, move-count rules, and no-progress draws must be recognized before recursive expansion, or the search may loop or assign the wrong utility.

When minimax is the wrong model #

Monte Carlo tree search (MCTS) is not alpha–beta with random ordering. It allocates samples adaptively and estimates action values rather than proving that omitted siblings cannot matter. AlphaZero, for example, combined learned policy and value networks with MCTS in self-play; its primary paper is evidence for that architecture, not a reason to describe its search as minimax pruning.

Failure modes and diagnostics #

Small exhaustive games are exceptionally valuable tests. Generate every state of tic-tac-toe or another finite game, compare alpha–beta with plain minimax, randomize move order, verify known terminal utilities, and assert that table-enabled and table-disabled searches agree. These tests exercise correctness invariants, while profiling on representative positions evaluates performance.

A compact reasoning checklist #

Before trusting a game search, make the following contracts explicit:

1. What information constitutes a state, including history-dependent rules?
2. From whose perspective is every terminal, evaluation, cached, and returned score measured?
3. Which assumptions make max/min alternation the correct game model?
4. Which cutoffs are proved exact for the declared horizon, and which are heuristic?
5. Does every transposition entry record depth and exact/lower/upper semantics?
6. What happens at terminal states, depth exhaustion, no-legal-move states, repetition, and timeout?
7. Can a small full minimax oracle reproduce every alpha–beta root result regardless of move order?

Minimax supplies the semantics of optimal adversarial choice. Alpha–beta supplies a proof-efficient evaluation of those semantics. Evaluation functions, move ordering, iterative deepening, tables, and selective search then decide how much useful game knowledge can be brought to bear before the computation budget expires.