Transposition Tables' own reference
implementation builds its cache key the same way on every single call:
board.map(c => c || '.').join(''), touching all nine cells whether or not the
position turns out to be a cache hit. Nine cells is nothing to worry about — but the same idea on
a 64-square chess board, rebuilt from scratch at every one of millions of nodes a real engine
visits per second, is real, measurable work spent on something that only ever changes by one piece
moving. Zobrist hashing fixes this by making the key incremental: instead
of re-reading the whole board every time, it maintains one running hash that gets updated by exactly
the part of the board that changed, and nothing else.
Same fixed board as Minimax and Transposition Tables, O to move, searched by plain minimax with no cache — this page isn't about skipping repeated work, it's about how cheaply the key for that work can be maintained either way. Press Step or Run and watch two running totals: how many cells the naive string key has touched so far, against how many cells Zobrist's running hash has touched so far, for the exact same search.
Before any search starts, generate one random number for every (square, mark) pair that could
ever appear on the board — for tic-tac-toe, 9 squares × 2 marks = 18 numbers, drawn once and reused
for the entire search, never regenerated per position. The hash of a position is just the XOR of
every random number belonging to a (square, mark) pair that's actually occupied on that board.
Placing a mark XORs its number in; removing that same mark XORs the identical number in again —
and because XOR is its own inverse (a ^ b ^ b === a for any a and
b), that second XOR exactly undoes the first, with no record needed of what the hash
used to be. That's a direct mirror of the board mutation minimax's own reference implementation
already does — board[cell] = mark to try a move, board[cell] = null to
undo it — just applied to the hash instead of the board array, and paid for as one machine word
operation instead of a full array touch either way.
The naive key has no equivalent shortcut: board.map(...).join('') has to read every
cell to produce a valid string, because a JavaScript string has no way to say "identical to the last
one I built, except position 4." Checked directly against the reference implementation below, over
this page's own small board (57 nodes, matching Minimax's own
citation): the naive key touches 513 cells total (9 per node, unconditionally) against
Zobrist's 112 (1 XOR per move made or undone) — a 4.6× reduction.
Scaled up — computed directly, not run live in the browser demo above, the same way
Transposition Tables' own Complexity section cites
its empty-board figures separately from what its small interactive demo actually runs — searching
tic-tac-toe from a completely empty board costs the naive key 4,949,514 touches
against Zobrist's 1,099,890, the same 4.5× ratio holding at scale:
nine touches per node against two touches per edge (one XOR in, one XOR out), and a tree has almost
exactly as many edges as nodes.
// drawn once, before any search starts — 9 squares × 2 marks, never regenerated per position
function makeZobristTable() {
const table = [];
for (let cell = 0; cell < 9; cell++) {
table[cell] = { X: randomUint32(), O: randomUint32() };
}
return table;
}
function minimaxZobrist(board, depth, maximizing, table, hash) {
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;
hash ^= table[cell][mark]; // XOR in — make the move
const value = minimaxZobrist(board, depth + 1, !maximizing, table, hash);
hash ^= table[cell][mark]; // XOR out — undo it, same operation
board[cell] = null;
best = maximizing ? Math.max(best, value) : Math.min(best, value);
}
return best;
}Nothing here decides a score any differently than
Minimax's own plain recursion — hash is threaded
through purely so that, at any point in the search, it holds a valid key for whatever's on the board
right now, ready to hand to a transposition table's get/set the moment one
is added on top.
Unlike the board-string key, which cannot collide by construction — it's a lossless
encoding of the board itself — a Zobrist hash can. It's a fixed-width digest of a much larger
space, so two genuinely different positions can land on the identical hash purely by chance, and a
transposition table that trusts the hash alone will silently return one position's cached score for
the other. Checked directly, not just asserted: running this page's own reference search from an empty
board (5,478 distinct reachable positions, the same count
Transposition Tables' page cites) with a
deliberately narrow hash width finds real collisions, and finds them well before the width "runs out"
of obvious room. At 8 bits (256 possible values) 5,222 of the 5,478 positions collide
with an earlier one — guaranteed by pigeonhole alone, since there are far more positions than buckets.
At 16 bits (65,536 values) it's 142 collisions, including a genuine, named pair: the
positions OXX....OO and O.XOXO.X. — no cell in common between their two
X's, no cell in common between their two O's, plainly different boards — hash to the identical value.
At 20 bits (1,048,576 values, headroom that looks generous against only 5,478 positions) it's still
45 collisions. Only at 24 bits and wider (16,777,216+ values) do all ten independently
seeded runs tried come back with zero. Real engines don't take a chance on where that line sits for a
game with billions of reachable positions instead of thousands — they use 64-bit keys, not 32, precisely
because a narrower one collides sooner than intuition expects.
Time: O(1) to update the hash on a move or its undo — one XOR — against
O(n) to rebuild a from-scratch key, where n is the board size (9 here, 64
squares plus side-to-move and castling/en-passant state for chess). Neither changes what
Minimax's own search costs — O(b^d) either way, the
same 57 nodes on this page's board and 549,946 from an empty one, since Zobrist hashing only ever
changes how cheaply a key gets maintained, never what gets searched or in what order.
Space: O(squares × distinct pieces) for the random table itself — 18
numbers here, drawn once and held for the whole search, dwarfed by whatever the transposition table
built on top of these keys ends up costing (O(distinct positions), per
Transposition Tables' own Complexity section).
This is the site's seventh Game Trees entry, and like Transposition Tables it doesn't answer "what should I play right now" at all — it answers a narrower question underneath that one, "how do I cheaply name the position I'm looking at right now." The two pages are companions, not competitors: Transposition Tables names the caching idea and its own reference implementation pays the full from-scratch cost of the key on every lookup, exactly the cost this page's own Pitfalls and Complexity sections measure directly; Zobrist hashing is the specific technique that makes that cost incremental instead, at the price of trading a collision-proof key for one that merely collides rarely, and only if its width is wide enough. Neither Minimax, Monte Carlo Tree Search, nor Expectimax need a position key at all — none of them remember a position once they're done with it — and Principal Variation Search and Iterative Deepening only need one to the extent they're paired with a transposition table in the first place, exactly the pairing Transposition Tables' own closing paragraph names. See Choosing a Game Tree Search Algorithm for how all ten compare side by side.