Alpha-Beta Pruning, in depth: the fail-soft bound contract, the minimal tree, measured move ordering, PVS and MTD(f)

The contract: what alpha-beta returns

Call the search with a window (alpha, beta) and let v be the returned value and V the true negamax value of the node. A correct alpha-beta guarantees three things:

• If alpha < v < beta, then v = V exactly.
• If v ≤ alpha (a fail low), then V ≤ v: the result is an upper bound.
• If v ≥ beta (a fail high), then V ≥ v: the result is a lower bound.

Everything else in alpha-beta is bookkeeping around this contract. The window represents what the caller already knows: it does not care about the exact value of a node unless it lies strictly between alpha and beta. A node whose value would fall outside can stop as soon as it has proved that much.

There are two flavours. Fail-hard clamps the return value into [alpha, beta], so a fail low always returns exactly alpha. Fail-soft returns the best value it actually found, which can lie beyond the window. Both satisfy the contract, but fail-soft gives a tighter bound for free, which is worth having once results are stored in a transposition table or reused by the null-window searches below. Here is the fail-soft negamax form used for every measurement:

import math

def alphabeta(node, depth, alpha, beta):
    """Fail-soft negamax. Returns v with: v <= alpha -> V <= v; v >= beta -> V >= v; else V == v."""
    if depth == 0 or node.is_terminal():
        return node.evaluate()          # score from the side to move's point of view
    best = -math.inf
    for child in node.ordered_children():
        v = -alphabeta(child, depth - 1, -beta, -alpha)
        if v > best:
            best = v
        if v > alpha:
            alpha = v
        if alpha >= beta:               # proved V >= beta: the parent will never allow this
            break
    return best

Note the window flip (-beta, -alpha): a child's lower bound is its parent's upper bound with the sign changed. Note also that evaluate() must score from the side to move. A version that scores from one fixed player's point of view and forgets to flip the sign at odd depths will pass every test you write at even depth and then fail at odd depth, which is exactly why the test below uses mixed depths.

The minimal tree and node types

How few leaves can any algorithm read and still prove the root value? Knuth and Moore answered this in 1975. To prove V = v you need two proofs. One shows the maximiser can get at least v: at each of the maximiser's nodes one good move suffices, but at each opponent node every reply must be covered. The other shows the opponent can hold it to at most v, with the roles swapped. Each proof is a strategy tree with b^⌈d/2⌉ or b^⌊d/2⌋ leaves, and the two share exactly one leaf, the end of the principal variation. So the minimal tree has

b^⌈d/2⌉ + b^⌊d/2⌋ − 1 leaves. For b = 6, d = 6 that is 216 + 216 - 1 = 431, against 46,656 for full minimax: under one percent.

The proof also classifies nodes into three types, which engine authors still use. PV nodes (type 1) lie on the principal variation, need an exact value, and search every child. CUT nodes (type 2) are refuted by one good move: if that move is searched first, the node stops after one child. ALL nodes (type 3) are positions where every move fails, so every child must be searched. The children of a CUT node are ALL nodes and vice versa, and the children of a PV node after the first are CUT nodes.

The node types have practical uses. At an expected CUT node, spend effort on getting the first move right (hash move, captures, killers), because a good first move ends the node. At an expected ALL node, move order barely matters because every child is searched anyway, so cheap ordering is fine, and it is the natural place to split work between threads in parallel search.

Measured: how move order sets the cost

The table shows leaf evaluations on the 20 random trees. Best first sorts each node's children by their true minimax value, which only an oracle can do. Worst first sorts them in reverse. Every run returned the same root value as full negamax, as asserted in the harness.

Three lessons. First, with perfect order, alpha-beta reaches the minimal tree exactly, with no slack. Second, random order on these trees reads about 13 times the minimal tree, so ordering is where nearly all the remaining speed lives. Third, principal variation search was slightly worse than plain alpha-beta under random order and had a much wider spread. PVS bets that the first move is best; when that bet fails, it pays for a re-search. It only wins when the ordering is good, which is why engines use it alongside iterative deepening and a transposition table that supply good first moves.

Null windows: PVS and MTD(f)

A null window (beta - 1, beta) for integer scores contains no value strictly inside it, so the search can only fail low or fail high. By the contract, the result answers a yes-or-no question: is V ≥ beta? Such probes cut far more than full-window searches, because every node can stop at the first proof either way. Two algorithms are built from them.

Principal variation search (also called NegaScout) searches the first child with the full window and probes every later child with a null window around alpha, re-searching only if the probe says the child is better:

for i, child in enumerate(ordered_children):
    if i == 0:
        v = -search(child, depth - 1, -beta, -alpha)
    else:
        v = -search(child, depth - 1, -alpha - 1, -alpha)   # is it better than alpha?
        if alpha < v < beta:                                # yes: get its exact value
            v = -search(child, depth - 1, -beta, -v)

MTD(f), published by Plaat and colleagues in 1996, drops the full window entirely. It starts from a guess f and repeatedly calls a null-window alpha-beta, using each fail-soft result to tighten a lower or upper bound until they meet. It relies on a table that stores both a lower and an upper bound per node, because every pass revisits the same tree:

def mtdf(root, depth, f):
    g, lower, upper = f, -math.inf, math.inf
    while lower < upper:
        beta = g + 1 if g == lower else g
        g = alphabeta_with_memory(root, depth, beta - 1, beta)
        if g < beta:
            upper = g          # failed low: V <= g
        else:
            lower = g          # failed high: V >= g
    return g

The quality of the first guess decides the cost. With the table cleared for each tree, leaf evaluations (counting re-evaluations on later passes) and passes averaged:

Even with a poor guess, MTD(f) read fewer leaves than one full-window alpha-beta in natural order (5,531), but it made 40 to 50 passes, each with its own overhead in table lookups. With integer scores, each pass moves a bound by at least one point, so fine-grained evaluations make bad guesses expensive. In practice the guess is the previous iteration's score from iterative deepening, which is usually close. MTD(f) is also fragile: it depends on the table keeping its bounds between passes, so table replacement and search instability hurt it more than they hurt PVS.

Testing an implementation and failure modes

Alpha-beta bugs rarely crash. They return a slightly wrong value in some positions, and the engine plays a little worse. The contract makes these bugs testable. Generate random trees, pick random nodes, depths and windows, and check the three cases against plain negamax:

for t in range(3000):
    rng = random.Random(t)
    node = random_node(rng)                  # mixed root parities catch sign bugs
    a = rng.randint(-120, 100); b = a + rng.randint(1, 60)
    v, true = alphabeta(node, 3, a, b), negamax(node, 3)
    assert (true <= v) if v <= a else (true >= v) if v >= b else (true == v)

The fail-soft search above passed 3,000 such cases with zero violations. Run the same test after every change to ordering, pruning or the table. Bugs that the test catches and production engines have shipped include:

• Storing a bound as exact. A transposition table entry must record whether the value is exact, a lower bound (fail high) or an upper bound (fail low). Using a bound as an exact score corrupts the parent.
• Unsound pruning sold as alpha-beta. Null-move pruning, late move reductions and futility pruning are speculative: they can change the result. Test them separately from the exact core, and expect them to change the root value sometimes.
• Path-dependent scores in the table. Mate-in-n scores and repetition draws depend on the path, not only the position. Convert mate scores to distance from the current node before storing and back when probing.
• Search instability. With a table and reductions, a re-search with a wider window can fail in the opposite direction from the probe. Handle it by accepting the probe's bound or by re-searching with a full window; never loop forever.
• Aspiration windows with fail-hard. When a narrow root window fails, fail-hard returns only the window edge, giving no hint how far to widen it. Fail-soft tells you.

Operational guidance and trade-offs

Use plain alpha-beta with good ordering as the baseline. Add PVS once iterative deepening and a table make first moves reliable, and measure: the table above shows it losing when ordering is poor. Treat MTD(f) as an experiment for engines with coarse evaluation and a robust table, not as a default.

Instrument every search with counters: nodes, leaf evaluations, the fraction of cut-offs that happened on the first move, and re-search counts. A first-move cut-off rate of around 90 percent or more means ordering is good; falling rates after a change mean ordering got worse even if strength tests are noisy. Compare leaf counts with the minimal-tree formula for your effective branching factor to see how much room remains.

Parallel alpha-beta is hard because the cut-offs depend on serial order. Classic schemes such as Young Brothers Wait search the first child of a node before searching its siblings in parallel, so that the window is established first. Many modern chess engines instead run independent searches on several threads that share one transposition table (often called lazy SMP), letting the table spread information. Either way, expect speed-up well below the thread count.

Finally, know when to stop. Alpha-beta needs a reasonably accurate static evaluation and moves that can be ordered. With huge branching factors and weak evaluations, Monte Carlo tree search usually does better, and games with chance need expectation nodes rather than pure minimax.

What to do next

1. Implement the fail-soft search above and the contract test, including odd and even depths and random windows; make it pass before adding anything else.
2. Add counters for leaf evaluations and first-move cut-off rate, and compare your leaf count with b^⌈d/2⌉ + b^⌊d/2⌋ - 1.
3. Add a transposition table that stores the bound type, keyed by Zobrist hashes, and rerun the contract test.
4. Add PVS and measure it against plain alpha-beta under your real move ordering; keep it only if it reads fewer nodes.
5. Read the minimax deep dive for what the value you are computing means, and the bitboard article for fast move generation, which raises the depth you can afford.