Zobrist hashing in chess
Zobrist
Definition
In chess computing, “Zobrist” refers to Zobrist hashing: a technique that assigns a compact, usually 64-bit (sometimes 128-bit), signature—called a Zobrist key—to a specific chess position. Invented by Albert L. Zobrist in 1969, it enables fast, incremental identification of positions so engines can recognize when they have seen the same position before, even if it was reached by a different move order (a transposition).
How it’s used in chess
- Transposition tables (TT): Engines index their TT entries by the Zobrist key to reuse evaluations, best moves, and search bounds across different move orders that reach the same position. This dramatically accelerates search.
- Repetition detection: Engines maintain a stack of Zobrist keys during the game to quickly check for threefold repetition. A matching key is a strong hint; engines typically verify with a precise move history to avoid any theoretical collision risk.
- Opening books and databases: Formats like Polyglot use a standardized Zobrist key (“Polyglot key”) so different engines and tools can refer to the same positions consistently.
- Endgame tablebases and caches: Position keys help index and retrieve exact or cached results quickly.
- Incremental make/unmake: Because of the XOR-based design, engines update the key in O(1) time when making or unmaking a move, without recomputing from scratch.
How it works (under the hood)
- Random bitstrings: Pre-generate a table of random numbers for each (piece type, color, square) combination—12 piece-color types × 64 squares = 768 numbers. Add random numbers for side-to-move, castling rights (typically one number per right: White O-O, White O-O-O, Black O-O, Black O-O-O), and en passant file (8 numbers, a–h).
- Compute a position’s key: Start at 0; XOR in the random number for every piece on its square; XOR the side-to-move number if it’s Black to move; XOR the numbers for the current castling rights; XOR the en passant file number when an EP capture is presently available (some engines only include it if a pawn could legally capture).
- Incremental update: When a move is made, XOR out the moving piece from its origin square and XOR it in on the destination square. If there’s a capture, XOR out the captured piece. Update castling and EP components as needed, then XOR the side-to-move bit to toggle turns. To unmake a move, the same XOR operations are applied again in reverse.
Examples
Transposition to the same position: These two move orders reach the same Queen’s Gambit Declined setup, so the Zobrist key is identical at the end of each sequence.
- Line A: 1. d4 Nf6 2. c4 e6 3. Nf3 d5 4. Nc3
- Line B: 1. d4 Nf6 2. Nf3 e6 3. c4 d5 4. Nc3
Both lead to the identical FEN (Black to move): rnbqkb1r/ppp2ppp/4pn2/3p4/2PP4/2N2N2/PP2PPPP/R1BQKB1R b KQkq - 1 4
Visualize Line A:
Visualize Line B:
Incremental update example (from the initial position, 1. e4):
- Start with the initial key (includes all starting pieces, White to move, full castling rights, no EP).
- XOR out the White pawn on e2.
- XOR in the White pawn on e4.
- Clear any EP info if previously set (none here).
- Castling rights unchanged.
- XOR the side-to-move bit (it’s now Black’s move).
Because XOR is its own inverse, unmaking 1... (any reply) and then unmaking 1. e4 restores the original key exactly.
Historical and strategic significance
Zobrist hashing was introduced in Albert L. Zobrist’s 1969 PhD thesis on pattern recognition and game-playing. It quickly became foundational in game AI (not just chess, but also Go and others). In chess, it underpins the efficient transposition handling that allows modern engines to prune vast portions of the search tree, reuse prior analysis, and scale to deep search depths—one reason today’s engines (e.g., Stockfish and many others) are so strong.
Interesting facts and notes
- Collision risk: With 64-bit keys, collisions are possible but extraordinarily rare in practice for typical engine workloads. Some systems use 128-bit keys or keep a secondary “check” value to reduce the already tiny risk further.
- Polyglot key: Many tools adopt a standardized, fixed set of random numbers so different programs can agree on the same key for a given position. This is the basis of Polyglot opening books.
- Determinism: Engines often use a fixed (compile-time) random table so that the same position always maps to the same key across runs and platforms.
- Legal EP convention: A common best practice is to include the en passant file in the key only when an EP capture is actually legal; this avoids false mismatches between positions that look similar but don’t offer an EP capture.
- Terminology: You’ll see “Zobrist key,” “hash key,” or just “zkey” used interchangeably by engine developers.