Explain Chess Engine Transposition Table

Alpha-beta search revisits identical board states through transpositions. Without a cache, that wasted work can multiply node counts. The transposition table (TT) is a fixed-size hash map: keyed by Zobrist hash, storing depth, score, bound type, and best move from the last time that position was searched deeply enough.

Concept

What Is a Transposition?

Path A

1. e4 e5
2. Nf3 Nc6
3. Bb5 a6

⇄

Path B

1. e4 e5
2. Bb5 Nc6
3. Nf3 a6

Same position after move 6 — one Zobrist key, one TT slot

64-bitZobrist key indexes TT

key % NTypical bucket index

16–24 BCompact entry size

64–512 MBCommon TT allocation

Key

Zobrist Hashing

Board state

→

XOR piece keys
+ EP + castling
+ side to move

→

zobristKey
updated on make/unmake

→

index = key % size

// Incremental update on makeMove (no full rehash)
key ^= zobrist[piece][square];
key ^= zobristSide;
// Also toggle en-passant & castling-right keys when they change

Structure

What's Stored in One TT Entry

Typical TT entry (packed into ~16 bytes)

key16–32 bit tag
(full or partial hash)

depthSearch depth stored
(e.g. 14 plies)

scoreCentipawns or
mate distance

flagEXACT · ALPHA · BETA

moveBest move found
(for ordering)

ageGeneration counter
(optional replace)

Flags

EXACT, ALPHA, and BETA Bounds

EXACT

Score is the true minimax value at this depth — all moves were searched and the result lies inside the window.

Use: return score immediately if stored depth ≥ current depth

ALPHA

Fail-low bound — position score is at most stored value (no move raised alpha high enough).

Use: cutoff if stored score ≤ alpha

BETA

Fail-high bound — position score is at least stored value (a move caused a beta cutoff).

Use: cutoff if stored score ≥ beta

Runtime

TT Lookup During Search

Probe bucket

index = zobristKey % ttSize — often 1–4 slots per bucket (cluster) to reduce collisions.

Verify key tag

Partial key match? If collision, treat as miss — never trust wrong position data.

Check depth

Stored depth must be ≥ current remaining depth (or QSearch rules) or entry is too shallow.

Apply flag

EXACT → return score. ALPHA/BETA → cutoff if bounds allow. Always try TT move first for ordering.

Store on exit

After searching node, write score + flag + best move if deeper than existing entry (depth-preferred replace).

TTEntry* e = probe(key);
if (e && e->depth >= depth) {
  if (e->flag == EXACT) return e->score;
  if (e->flag == ALPHA  && e->score <= alpha) return alpha;
  if (e->flag == BETA   && e->score >= beta)  return beta;
}
// ... search moves ...
store(key, depth, score, flag, bestMove);

Deep dive

Implementation Details

♔

Mate scores & ply

Mate scores depend on distance to mate. Store MATE - ply on write, add ply back on read so the same mate works at different depths in the tree.

↻

Replacement policies

Depth-preferred: always replace if new depth ≥ old (most common). Always replace: simpler but weaker. Age/generation: prefer entries from current iterative-deepening pass. Clusters keep multiple entries per hash slot.

Iterative deepening synergy

Each depth pass fills TT with deeper entries. Shallow results bootstrap move ordering for deeper searches — TT hit rate climbs each iteration. Clear TT on ucinewgame, not every move.

♻

Repetition detection

Separate from TT but uses the same Zobrist key stack: if a key repeats three times, declare draw. TT stores search scores; repetition stack stores game history keys.

⚠

Collisions & bugs

Hash collisions (different positions, same index/tag) cause rare wrong scores if key tag is too short. Use enough key bits. Never store TT results without verifying tag match.

Reference

TT vs Other Engine Memory

Structure	Stores	Purpose
Transposition table	Depth, score, flag, move	Avoid re-searching subtrees
Killer moves	2 quiet moves per ply	Move ordering only
History table	Quiet move scores	Move ordering only
Repetition stack	Zobrist keys along PV	Draw by threefold
Pawn hash (optional)	Pawn structure eval	Eval cache, not search

Why TT size matters

Larger TT → fewer collisions, more deep entries retained → higher hit rate → fewer nodes. Diminishing returns above ~256–512 MB for most engines. UCI option Hash lets users allocate MB at runtime.

Clear TT on new game; keep between moves in same game
Store TT move first in move ordering every node
Pack entries small — millions of slots fit in RAM
TT does not replace correct move generation or eval

Explore the engine series

TT powers search cutoffs — see how it fits with alpha-beta and the full engine stack.

Search Algorithm Engine Anatomy Chess Engines

Related: Search Algorithm · Move Generation · All Blogs