Transposition Tables, in depth: the depth and bound probe contract, measured replacement policies, false matches, mate scores and sizing

What the table stores and why

Search the empty tic-tac-toe board with full minimax and it visits 549,946 nodes, because every move order is walked separately. Plain alpha-beta with the natural move order cuts that to 20,866. Adding an unbounded transposition table, a Python dict in effect, cuts it again to 5,473. The root value is 0, a draw, in every run. The table helped because the game graph has far fewer distinct positions than paths: every position with four marks on the board is reachable by several orders of the same moves.

A TT entry is a summary of a finished search of one position. To be useful it must record enough to know when that summary applies to a new request. The usual fields are:

The bound flag is the part people get wrong. Alpha-beta does not compute exact values outside its window. If a node fails high, all you know is that the true value is at least the returned score; if it fails low, only that it is at most the score. Storing either as if it were exact silently corrupts later searches with different windows.

The probe contract: depth and bounds

The probe contract has two gates. First, the entry must be for this position (key match) and must come from a search at least as deep as the one requested. Second, the stored score must settle the current window. An exact score always does. A lower bound settles it only if it is already at or above beta, because then the node fails high whatever the true value is. An upper bound settles it only if it is at or below alpha. Anything else is a hit that cannot cut, and the search continues, still trying the stored move first.

EXACT, LOWER, UPPER = 0, 1, 2

def negamax(pos, depth, alpha, beta, ply):
    alpha_orig = alpha
    e = tt.probe(pos.key)                    # None unless the full key matches
    if e is not None and e.depth >= depth:   # gate 1: deep enough
        v = score_from_tt(e.score, ply)      # mate scores: see below
        if e.flag == EXACT:
            return v
        if e.flag == LOWER and v >= beta:    # gate 2: the bound settles the window
            return v
        if e.flag == UPPER and v <= alpha:
            return v
    if depth == 0 or pos.terminal():
        return evaluate(pos, ply)
    moves = order(pos.legal_moves(), first=e.move if e else None)
    best, best_move = -INF, None
    for m in moves:
        pos.make(m)
        v = -negamax(pos, depth - 1, -beta, -alpha, ply + 1)
        pos.unmake(m)
        if v > best:
            best, best_move = v, m
        alpha = max(alpha, v)
        if alpha >= beta:
            break                            # fail high: best is a lower bound
    if best <= alpha_orig:
        flag = UPPER                         # fail low: no move raised alpha
    elif best >= beta:
        flag = LOWER
    else:
        flag = EXACT
    tt.store(pos.key, depth, score_to_tt(best, ply), flag, best_move)
    return best

Two details matter. The flag is chosen against the original alpha, saved before the move loop raised it; comparing against the raised alpha marks every exact score as an upper bound and throws away information. And some engines skip TT cutoffs at principal-variation nodes, so the reported best line is always fully searched rather than truncated at a table hit.

In the tic-tac-toe experiment every search runs to the end of the game, so a stored entry for a position always has the same remaining depth as any later request for it. The depth gate therefore always passes there, which is why the toy can omit it. In any depth-limited search it is mandatory.

Worked example: measured replacement policies

The measured program is the negamax above with depth fixed to the number of empty squares, a win scored as 10 - ply for the side that made it, the natural square order 0 to 8, and the TT move tried first. Tables are arrays of 2^bits slots indexed by the low bits of the 64-bit key. Three replacement policies were compared: always overwrites the slot; depth keeps the existing entry unless the new one has at least as much remaining depth; two has a depth-preferred slot plus an always-replace slot per index, and a store that loses the first goes to the second.

A tiny table already removes almost 30% of the work, because most transpositions are near the leaves and recur quickly. Depth-preferred replacement alone was the worst policy here: once a slot holds a deep entry, frequently repeated shallow positions can never be cached. The two-tier scheme keeps the expensive entry and still caches recent shallow work.

Treat the ranking of always against depth-preferred as a property of this toy, which searches once to the end with no iterative deepening. In an engine that re-searches the same tree at increasing depth, deep entries from the previous iteration are much more valuable and the age field becomes essential. The two-tier result is the one that generalises, which is why bucketed designs dominate in practice.

False matches: what an unverified slot does

What happens if you trust the slot index and skip the key comparison? The same searcher was run with verification turned off, so any entry in the slot was accepted. The search became dramatically faster and completely wrong. With 16 slots it visited 95 nodes and reported the root as 3, a forced win for the first player; with 64 slots, 234 nodes and a value of 2; with 256 slots, 701 nodes and a value of 3. The true value is 0.

Searching the nine first moves separately, whose correct values are all 0, with 1,024 unverified slots gave -2, -1, 0, -1, 0, 2, 0, 0, 1. Two rules follow. Store and compare enough key bits to make a false match rare, and never let a TT move reach the board without checking it is legal in the current position, because with the 16 or 32 verification bits real engines store, a false match will eventually happen in a long game. A false score costs a little quality; an illegal move from a false match can crash the program.

Mate scores and the graph history interaction

Engines score a forced mate as a large constant minus the distance to mate, so that a mate in 3 is preferred to a mate in 7. Distance is naturally counted from the root, and that is the trap: the same position reached at ply 5 in one line and at ply 11 in another is the same distance from mate, but a different distance from the root. If the root-relative score is stored and reused at another ply, the engine reports wrong mate distances and can shuffle pieces without making progress. The fix is to store mate scores relative to the node and convert on the way in and out:

MATE = 32000
MATE_BOUND = MATE - 1000          # anything beyond this is a mate score

def score_to_tt(v, ply):          # root-relative -> node-relative
    if v >= MATE_BOUND:  return v + ply
    if v <= -MATE_BOUND: return v - ply
    return v

def score_from_tt(v, ply):        # node-relative -> root-relative
    if v >= MATE_BOUND:  return v - ply
    if v <= -MATE_BOUND: return v + ply
    return v

Tic-tac-toe hides this bug, because a position with k marks always occurs at ply k; the toy stores root-relative scores and still gets correct answers. Chess, Go and most other games do not have that property.

The deeper problem is the graph history interaction. A TT assumes a position's value depends only on the position, but in chess it also depends on the path: repetition draws and the fifty-move rule look at history. A score stored from a line where the position was a repetition draw is reused in a line where it is not, or the other way round. No cheap complete fix exists. Practical engines include the side to move, castling rights and en-passant square in the key, detect repetitions before probing, avoid storing draw-by-repetition scores as exact where they can, and accept the small residual error.

Sizing, layout and sharing

Size the table in entries, not megabytes: compare nodes per second times search time with the entry count. Too small and useful entries are evicted before reuse; too large and probes miss the CPU cache and TLB on every node, which shows up as fewer nodes per second. Huge pages help large tables.

Because the probe is a random memory access on almost every node, layout matters more than the policy details:

• Buckets per cache line. Pack several small entries into one 64-byte line and scan them all on a probe; one memory access then gives the replacement policy several candidates. Storing only 16 or 32 verification bits per entry is common, because the index already supplies the low bits.
• Prefetch. Compute the child's key before making the move and issue a prefetch for its bucket, so the miss overlaps with move generation.
• Index mapping. Low-bit masking requires a power-of-two size. Mapping with the high half of a 64-by-64-bit product (key times bucket count) allows any size and uses the well-mixed high bits.
• Aging. Store a small generation counter that increments per root search, and prefer to evict entries from old generations; clearing a multi-gigabyte table between moves is too slow.
• Sharing between threads. Parallel engines usually share one table across all search threads; the lockless validation scheme is described in the Zobrist article. Torn or racy entries must fail verification, not crash the search.

The table is a cache, not a dictionary: losing an entry costs only time, but returning wrong data costs correctness. That asymmetry is why collisions are resolved by overwriting rather than chaining.

Failure modes

• Bound stored as exact. Symptom: evaluations that change with aspiration windows and occasional blunders after re-searches. Choose the flag against the original alpha.
• Missing depth check. Shallow results answer deep requests and the engine plays at the strength of its weakest iteration.
• Unverified or truncated keys. As measured above, accepting anything in the slot produces confident nonsense; keep verification bits and check move legality.
• Root-relative mate scores. Wrong mate distances and failure to convert won endgames.
• Incomplete key. Leaving side to move, castling or en-passant rights out of the key makes different positions share entries.
• Stale entries hogging the table. Without aging, deep entries from previous moves block new ones forever.
• Non-reproducible tests. Test with one thread and a cleared table to get deterministic node counts.

Trade-offs

Every TT design trades memory traffic, hit rate and correctness margin. More verification bits mean fewer false matches but fewer entries per cache line. Depth-preferred replacement protects expensive results but starves recent shallow ones; two-tier buckets are the usual compromise. A shared table gives threads each other's results almost for free but makes searches non-deterministic. Outside games, the same idea appears in negamax-style solvers, puzzle search and dynamic programming over state graphs: anywhere a search revisits a state, a bounded, overwrite-on-collision cache with verification beats both no cache and an unbounded dictionary.

What to do next

1. Reproduce the measurement: write the tic-tac-toe negamax above, confirm 20,866 nodes without a table and 5,473 with an unbounded one, and keep the counts as a regression test.
2. Add the depth gate, the three-way bound flag computed from the saved alpha, and the mate-score conversion functions, then unit-test each with hand-built entries.
3. Turn verification off once in a test build and confirm your test suite notices; if it does not, your tests are too weak.
4. Switch to two-entry or cache-line buckets with an age field and compare node counts and nodes per second at fixed depth on a set of test positions.
5. Measure hit rate, cutoff rate and how often the TT move is the best move; the last number tells you how much ordering the table is buying.
6. Read the Zobrist hashing article before sharing the table between threads.