Transposition tables exploit a fact plain minimax and alpha-beta both ignore: different move orders can land on the exact same board. O plays cell 3, then X plays cell 4 — or X plays cell 4 first, then O plays cell 3 — two different paths through the game tree, one identical resulting position, one identical score no matter which path got there. Minimax and its alpha-beta variant re-derive that score from scratch every single time recursion reaches it, because neither remembers anything about a position once it's been fully explored and unwound. A transposition table is a cache: the first time a position is fully evaluated, its score is stored under a key built from the board itself; the next time recursion reaches that same board — by any route — the stored score comes back immediately, with no further search below it. It's the same idea as top-down memoization applied to a DP table's subproblems, turned loose on a game tree's positions instead.
Same fixed board as Minimax, O to move, needing a few plies of search before the right answer becomes visible. Pick plain minimax (re-derives every position from scratch, no memory between branches) or minimax + transposition table (caches every fully-evaluated board by its own contents and returns instantly on a repeat), then press Step or Run. A cache hit is marked with a dotted border and logged explicitly — notice that a hit can fire partway down the tree, and when it does it skips everything that would otherwise have been searched underneath it, not just the one node itself.
Caching by board contents alone is only safe if the board fully determines everything the score
depends on. It does here: this game's turns strictly alternate and nobody ever passes, so counting
the X's against the O's on a board pins down whose move it is, and counting marks placed since the
fixed START board pins down the recursion depth — both quantities score()
needs come along for free from the board alone. That makes board.map(c => c || '.').join('')
a complete, lossless substitute for a richer key like (board, depth, turn): nothing about
the position is left out, so nothing gets confused with anything else.
The savings are real and checked directly against the reference implementation below, not just
claimed. On this page's own small board, plain minimax visits 57 nodes (the same
count Minimax's own page cites for its plain mode); minimax with
a transposition table freshly evaluates only 33 of them, catching the other
16 as cache hits that return instantly instead of re-opening whatever sits beneath
them. Scaled up — computed directly rather than run live in the browser demo, the same way Minimax's
own Complexity section separates its empty-board citation from what its interactive demo actually
runs — searching tic-tac-toe from a completely empty board makes the gap dramatic: plain minimax
visits 549,946 nodes to confirm the well-known result that perfect play draws (score
0); a transposition table needs to freshly evaluate only 5,478 distinct
positions, with the other 10,690 encounters returned from cache — under 1% of the
uncached node count gets computed even once.
function minimax(board, depth, maximizing) {
const w = winner(board);
if (w) return score(w, depth);
if (isFull(board)) return 0; // draw
const mark = maximizing ? 'X' : 'O';
let best = maximizing ? -Infinity : Infinity;
for (const cell of emptyCells(board)) {
board[cell] = mark;
const value = minimax(board, depth + 1, !maximizing);
board[cell] = null; // undo — try the next cell
best = maximizing ? Math.max(best, value) : Math.min(best, value);
}
return best;
}
function minimaxTT(board, depth, maximizing, table) {
const key = board.map(c => c || '.').join('');
if (table.has(key)) return table.get(key); // seen this exact position before — reuse it
const w = winner(board);
if (w || isFull(board)) {
const value = w ? score(w, depth) : 0;
table.set(key, value);
return value;
}
const mark = maximizing ? 'X' : 'O';
let best = maximizing ? -Infinity : Infinity;
for (const cell of emptyCells(board)) {
board[cell] = mark;
const value = minimaxTT(board, depth + 1, !maximizing, table);
board[cell] = null;
best = maximizing ? Math.max(best, value) : Math.min(best, value);
}
table.set(key, best); // store before returning — the next visitor to this board reuses it
return best;
}The cache key has to capture everything the score depends on — here that's the board
alone, but only because of this game's specific rules. Strict alternation and no passes let
tic-tac-toe's board contents alone pin down both whose move it is and the recursion depth, so keying
purely on the board is a complete substitute for keying on (board, depth, turn)
explicitly — nothing is lost. That collapses the moment a game allows a pass, allows reaching the same
arrangement of pieces at two different depths (many games do), or scores a position differently
depending on some piece of state the board itself doesn't show (a more complex turn rule, captured
material, a repetition count for detecting draws). Any of those needs to ride along in the key too, or
two genuinely different positions collapse into one cache entry and the wrong one's score gets reused
for both.
Caching a value computed under alpha-beta pruning and reusing it elsewhere in the tree is
not automatically safe — checked directly, it returns the wrong answer. Alpha-beta's whole
mechanism is cutting a branch short the moment it proves that branch can't affect the final choice; the
value it returns at that cut point is only a bound on the position's true score — "at least
this much" or "at most this much" — not necessarily the exact value plain minimax would find by
searching every child. Store that bound in the cache the same way a plain-minimax lookup would, and a
later, differently-windowed search elsewhere in the tree can read it back as if it were exact. Running
the exact combination — alpha-beta pruning plus a transposition table that stores raw returned scores
with no record of which were exact and which were only bounds — on the empty board returns O's score
as 1. The true value, confirmed twice above (plain minimax, and minimax with a
pruning-free transposition table) is 0: perfect play from an empty tic-tac-toe board is a
draw. Real engines fix this by storing a flag alongside every cached value — exact, lower-bound
("fail-high"), or upper-bound ("fail-low") — and only trusting a bound when the current search window
actually needs that direction of bound. That bookkeeping is a second, separate piece of work; it's why
this page's own demo pairs the transposition table with plain minimax rather than alpha-beta.
Time: plain minimax's O(b^d) worst case comes from re-deriving every
path through the tree, even paths that revisit a position already fully solved. A transposition table
doesn't change what a single fresh evaluation costs, but it collapses the total work toward the number
of distinct positions reachable rather than the number of paths to them — checked above at
33 fresh evaluations plus 16 cache hits against plain minimax's
57 on this page's small board, and 5,478 fresh evaluations plus
10,690 hits against 549,946 from an empty one. Space:
O(distinct positions reached) for the table itself — a real, new cost none of this site's
other Game Trees pages pay. Plain minimax and alpha-beta both hold only O(d), one line of
play at a time, because they discard every position the moment they're done with it; a transposition
table's entire value proposition is refusing to discard that, and it costs memory proportional to how
many distinct positions it ends up remembering — 5,478 entries for the full empty-board search of a
game this small.
This is the site's fourth Game Trees entry, alongside
Minimax with Alpha-Beta Pruning,
Monte Carlo Tree Search, and
Expectimax — the other three all answer "what score does
this position have," by exhaustive search, by random sampling, or by averaging over chance. A
transposition table doesn't answer that question at all; it's orthogonal to all three, a way of never
answering the same question twice. Pairing it with alpha-beta pruning the way real engines do needs
one more idea this page's Pitfalls section names but doesn't build: tagging every cached value as
exact or as only a bound. A fifth entry,
Principal Variation Search, is where that
exact-or-bound distinction actually comes from: its null-window scout searches are a search
strategy built specifically to return a bound instead of an exact value whenever a full search
isn't needed, the same fact this page's own Pitfalls section runs into from the caching side
instead. A sixth, Iterative Deepening, needs
exactly the kind of hint a transposition table provides — a strong first guess at the best move —
but generates it from its own previous, shallower pass instead of a hashed cache: the same idea,
free to compute instead of paid for in memory. A seventh entry,
Zobrist Hashing, is this page's own closest
companion rather than another sibling to compare against: it's the specific technique behind the
board.map(c => c || '.').join('') key this page's own reference implementation builds
from scratch on every single call, replacing that with a running hash updated by one XOR per move
made or undone. Checked on that page: the naive key touches all 9 cells on every node regardless of
whether it's a hit, 513 touches total on this page's own board against Zobrist's 112 — the tradeoff
being a hash that can, at a narrow enough width, collide two different positions, which this page's
own board-string key never can. A ninth entry, MTD(f), is
where the exact-or-bound tagging named above actually gets built rather than just flagged as
missing — it can't function without it, since its entire driver loop depends on telling an exact
value apart from a bound at every single lookup. See
Choosing a Game Tree Search Algorithm
for how all ten compare side by side, and which of them this page's own cache is actually worth pairing with.