Game Tree Search, in depth: minimax, negamax and alpha-beta traced by hand, with move ordering, transposition tables and iterative deepening measured

Minimax and negamax

Call the player to move at the root MAX and the opponent MIN. Scores are always from MAX's point of view. At a terminal position the score is the game result, for example +1 for a MAX win, 0 for a draw and -1 for a loss. At a MAX node the value is the largest child value; at a MIN node it is the smallest. The value at the root is what MAX can guarantee against any opponent play, and the best move is the child that achieves it.

Minimax is a depth-first search, the same recursion as in depth-first search with a max or min at each return. It uses memory proportional to depth, but time proportional to b^d for branching factor b and depth d. Tic-tac-toe is small enough to search completely: from the empty board the full tree has 549,946 nodes (255,168 complete games), which a plain recursive search visits in well under a second in C and a few seconds in Python. Chess has around 35 legal moves in a typical position, so even 6 plies is about 1.8 billion leaves. Real games need both pruning and a cut-off depth with a heuristic evaluation.

Negamax is the usual way to write it. Because max(a, b) = -min(-a, -b), you can score every position from the point of view of the side to move and negate on the way up. One function replaces two, and the pruning logic below only has to be written once.

Alpha-beta pruning, traced

Alpha-beta keeps two numbers during the search. Alpha is the best score the side to move is already guaranteed somewhere along the current path; beta is the best score the opponent is already guaranteed. If a position's value is proven to be at least beta, the opponent will never allow it, so the remaining moves there need not be searched: a beta cut-off. The window (alpha, beta) narrows as the search learns more, and in negamax form it is passed to children as (-beta, -alpha).

The diagram traces the classic three-by-three example. The left MIN node reads leaves 3, 12 and 8 and returns 3, so the root now has alpha = 3. The middle MIN node reads its first leaf, 2. MIN can already force 2 or less there, which is worse for MAX than the 3 already in hand, so the remaining leaves 4 and 6 are skipped. The right MIN node reads 14, then 5, then 2, and returns 2. The root value is 3, exactly as plain minimax would say, after reading 7 leaves instead of 9.

How much alpha-beta saves depends on order. If the best move is always searched first, Knuth and Moore's 1975 analysis shows the number of leaves examined drops to about b^d/2, so in the same time the search goes roughly twice as deep. With the worst order it saves nothing. Real engines land between the two, and most of the engineering in this page is about getting closer to the best case.

A complete engine and what each part saves

The engine below is a complete negamax alpha-beta search for tic-tac-toe with a transposition table, hash-move ordering and iterative deepening. The board is a 9-character string of X, O and dots. The loss score is -(1 + empty squares): losing with more squares still empty means losing sooner, so it scores worse, and the engine prefers fast wins and slow losses. Because the number of empty squares is a property of the position, not of the path that reached it, the score can be stored safely in the table.

import math
from collections import namedtuple

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
CENTRE_FIRST = [4, 0, 2, 6, 8, 1, 3, 5, 7]          # static move ordering
INF = math.inf
EXACT, LOWER, UPPER = 0, 1, 2
Entry = namedtuple("Entry", "depth value flag move")

def other(p):
    return "O" if p == "X" else "X"

def won(b, p):
    return any(b[i] == b[j] == b[k] == p for i, j, k in LINES)

def evaluate(b, p):
    """Heuristic for the side to move: lines still open to p minus lines open to the opponent."""
    o = other(p)
    mine = sum(1 for l in LINES if all(b[i] != o for i in l))
    theirs = sum(1 for l in LINES if all(b[i] != p for i in l))
    return mine - theirs

def search(b, p, depth, alpha, beta, tt, stats):
    stats["nodes"] += 1
    empties = b.count(".")
    if won(b, other(p)):
        return -(1 + empties)            # opponent just won; sooner is worse
    if empties == 0:
        return 0
    if depth == 0:
        return evaluate(b, p)
    alpha0 = alpha
    e = tt.get((b, p))
    if e and e.depth >= depth:           # stored result is deep enough to reuse
        if e.flag == EXACT:
            return e.value
        if e.flag == LOWER:
            alpha = max(alpha, e.value)
        else:
            beta = min(beta, e.value)
        if alpha >= beta:
            return e.value
    moves = [m for m in CENTRE_FIRST if b[m] == "."]
    if e and e.move in moves:            # best move from an earlier search goes first
        moves.remove(e.move)
        moves.insert(0, e.move)
    best, best_move = -INF, moves[0]
    for m in moves:
        child = b[:m] + p + b[m + 1:]
        score = -search(child, other(p), depth - 1, -beta, -alpha, tt, stats)
        if score > best:
            best, best_move = score, m
        alpha = max(alpha, score)
        if alpha >= beta:
            stats["cutoffs"] += 1
            break                        # opponent will avoid this position
    flag = UPPER if best <= alpha0 else LOWER if best >= beta else EXACT
    tt[(b, p)] = Entry(depth, best, flag, best_move)
    return best

def best_move(b, p, max_depth=9):
    tt, stats = {}, {"nodes": 0, "cutoffs": 0}
    for depth in range(1, max_depth + 1):    # iterative deepening
        value = search(b, p, depth, -INF, INF, tt, stats)
    return tt[(b, p)].move, value, stats

print(best_move("." * 9, "X"))   # (4, 0, {...}): take the centre; perfect play draws

Measured node counts from the empty board, all returning the correct value of 0 (a draw):

The standard enhancements

Each line of that table is one of the standard enhancements.

Move ordering. Trying the centre and corners first, which are usually stronger, cut the search by more than half compared with numeric order. Chess engines order captures by the value of the captured piece, then killer moves (quiet moves that caused a cut-off at the same depth in a sibling), then moves ranked by a history table that counts how often each move caused cut-offs.

Transposition table. Different move orders reach the same position. Storing results in a hash table keyed by position avoids searching it twice; here that removed most of the remaining work. Real engines key the table with a 64-bit Zobrist hash, updated incrementally by XOR as moves are made, and use a fixed-size array with a replacement policy, as in any hash table under memory pressure. The table is the same idea as memoisation in dynamic programming, with one twist: after a cut-off the stored number is only a bound, which is why each entry carries a flag.

Iterative deepening. Search depth 1, then 2, then 3, and so on. In tic-tac-toe it costs more than one direct search, as the table shows, because the tree is tiny. In real games it earns its keep twice: the engine always has a finished answer when the clock runs out, and each iteration leaves best moves in the table that order the next, deeper iteration almost perfectly. Since the tree grows by a factor of b per ply, the earlier iterations together cost only a fraction of the last.

Quiescence search. A fixed depth cut-off creates the horizon effect: the search stops in the middle of an exchange and scores a position where a queen is hanging as if it were quiet. Quiescence search continues past the nominal depth with captures only (or other forcing moves) until the position is quiet, using the static evaluation as a lower bound the side to move can always accept.

Narrower windows. Principal variation search assumes the first move is best and searches the others with a zero-width window (alpha, alpha + 1) that only proves they are worse, re-searching on failure. Aspiration windows start the root search with a narrow window around the previous iteration's score.

Evaluation, and when to use something else

Once the search is cut off, play strength depends on the evaluation function. Classical evaluations are weighted sums of features (material, mobility, king safety, pawn structure) tuned against game results. Modern chess engines combine alpha-beta with a small neural network evaluated efficiently on the CPU, and AlphaZero-style programs replace alpha-beta with Monte Carlo tree search guided by a policy and value network.

Choose by game. Alpha-beta is strongest when a cheap evaluation is reasonably accurate and good moves are easy to order. Monte Carlo tree search does better when branching is huge and positions are hard to evaluate statically, as in Go. When chance is involved (dice, card draws), minimax is replaced by expectimax, which averages over chance nodes and loses most of alpha-beta's pruning.

Bugs and how to test for them

Test with positions whose answer you know: a forced win in one and in two, a forced loss, and a full solve of tic-tac-toe returning a draw. Then compare the move and value of the optimised search against plain minimax on many random positions; enhancements must change node counts, never results.

Trade-offs

Every enhancement trades simplicity for depth. A transposition table costs memory and introduces the bound bugs above. Aggressive pruning techniques beyond alpha-beta (null-move pruning, late move reductions) are not exact: they assume most moves are bad and can miss a quiet winning move, which is acceptable in a playing engine and not in a solver. Deeper search with a crude evaluation and shallower search with a slow, accurate one can reach the same strength; measure games won, not nodes per second. For a problem that is really a constraint search with no opponent, use backtracking instead.

What to do next

1. Run the tic-tac-toe engine above and confirm each line of the node-count table on your machine.
2. Swap the move order to 0-8 and watch the node count rise; then add a history table and watch it fall.
3. Port the engine to Connect Four, where full search is impractical, and write a window-counting evaluation.
4. Replace the dictionary key with an incrementally updated Zobrist hash and a fixed-size table.
5. Add a time limit to iterative deepening so the engine always returns its last completed answer.
6. Write the regression test that compares optimised search against plain minimax on random positions.