Zobrist Hashing, in depth: incremental XOR keys, chess state features, collision arithmetic, lockless transposition tables and repetition detection

The construction

Describe a position as a set of binary features: "white knight on f3", "black to move", "white may castle kingside". Chess has 12 piece kinds on 64 squares, so 768 piece-square features, plus a handful of state features. At program start, draw an independent random 64-bit integer Z[f] for every feature f. The hash of a position is the XOR of Z[f] over all features present.

Two properties of XOR make this work. It is associative and commutative, so the order in which features were added does not matter; transposed move orders produce identical keys. And every value is its own inverse (x XOR a XOR a = x), so adding and removing a feature are the same operation. A move that takes a piece from square s to square t changes the key by XORing Z[piece][s] and Z[piece][t]; a capture also XORs out the captured piece; the side-to-move key flips on every move. Updating costs a few XORs regardless of board size, compared with re-hashing 64 squares.

Incremental update and undo in code

The implementation below is complete for a simplified board: pieces on squares plus side to move. Note that keys come from a seeded generator, so a run is reproducible and keys can be shared between your own tools (reading a Polyglot opening book instead requires that format's published constants); they must not come from a weak generator such as a small linear congruential one, whose low bits are correlated.

import random

PIECES = "PNBRQKpnbrqk"           # 12 kinds
rng = random.Random(20261006)     # fixed seed: reproducible keys
Z = [[rng.getrandbits(64) for _ in range(64)] for _ in PIECES]
Z_BLACK_TO_MOVE = rng.getrandbits(64)

def full_hash(board, black_to_move):
    # board: dict square -> piece letter; used for setup and for testing
    h = 0
    for sq, pc in board.items():
        h ^= Z[PIECES.index(pc)][sq]
    if black_to_move:
        h ^= Z_BLACK_TO_MOVE
    return h

class Position:
    def __init__(self, board, black_to_move=False):
        self.board, self.btm = dict(board), black_to_move
        self.h = full_hash(self.board, self.btm)
        self.history = []                      # keys of earlier positions

    def make(self, frm, to):
        pc = self.board.pop(frm)
        cap = self.board.get(to)
        self.history.append(self.h)
        self.h ^= Z[PIECES.index(pc)][frm] ^ Z[PIECES.index(pc)][to]
        if cap:
            self.h ^= Z[PIECES.index(cap)][to]
        self.board[to] = pc
        self.btm = not self.btm
        self.h ^= Z_BLACK_TO_MOVE
        return cap                             # undo information

    def unmake(self, frm, to, cap):
        pc = self.board.pop(to)
        self.board[frm] = pc
        if cap:
            self.board[to] = cap
        self.btm = not self.btm
        self.h = self.history.pop()            # or re-apply the same XORs

Two habits catch most bugs. In debug builds, assert after every make and unmake that self.h == full_hash(self.board, self.btm); an incremental update that forgets a feature is otherwise silent and only shows up as mysteriously wrong search results. And restore the key on unmake from a stack, as above, or by repeating the XORs; both work, and the stack is also the history list you need for repetition detection.

A hand trace

To see the mechanics, shrink the keys to 4 bits and use a two-feature toy. Suppose Z[white knight][g1] = 1011, Z[white knight][f3] = 0110 and Z[black to move] = 1100. With only the knight on g1 and white to move, h = 1011.

The incremental result matches the from-scratch hash, and repeating the XORs restores the start. With 4-bit keys collisions would be constant; the reason real engines use 64 bits is the subject of the collision section.

Chess state beyond piece placement

A position for search purposes is not just piece placement. Two boards with identical pieces are different positions if castling rights or en passant possibilities differ, because the legal moves differ. The widely used Polyglot opening-book format fixes a standard layout of 781 random numbers: 768 piece-square keys, 4 castling-right keys, 8 en passant file keys and 1 side-to-move key. Two details from that format are worth copying even if you never read a Polyglot book.

First, castling rights are four independent features, XORed out when a king or rook moves or a rook is captured. Updating them by XORing out the old rights and XORing in the new rights handles every case. Second, Polyglot includes the en passant file key only when a pawn of the side to move stands next to the pawn that just advanced two squares, not merely whenever a double push happened; its specification says explicitly that whether the capture would be legal (the capturing pawn might be pinned) does not matter. The rules of chess are stricter: for repetition, positions are the same only if the same moves are legal. Hashing the en passant file unconditionally gives positions with identical legal moves different keys, wasting table hits and breaking repetition detection; for exact semantics test legality, and compute the adjacency variant only for Polyglot lookups.

Collisions: index versus key

Two different collision events must be kept apart. An index collision happens when two positions map to the same table slot, h mod 2^k. With a table of 2 to the 20 entries this happens constantly and is harmless, provided each entry stores enough of the key to tell positions apart. A key collision happens when two different positions have the same stored bits; then the search uses a score from the wrong position, silently.

If keys behave like uniform random 64-bit values, the birthday bound gives the chance that any two of n distinct positions share a full key as 1 minus e to the power of minus n squared over 2 to the 65. A long analysis touching n = 2 to the 32 (about 4.3 billion) distinct positions gets an exponent of one half, so about a 40 percent chance that some pair collides somewhere. That sounds alarming but the relevant quantity is smaller: a wrong hit needs the colliding position to be in the table at the moment of the probe. The per-probe false-hit rate is about 2 to the minus b, where b is the number of key bits that are verified beyond the index bits.

Here is a worked case. A compact engine uses a 2 to the 20 entry table and stores only a 16-bit check value per entry. A probe of an occupied slot holding a different position returns a false hit with probability 1 in 65,536. At 10 million probes per second, mostly landing on occupied slots, that is on the order of 150 false hits per second. Storing 32 check bits cuts it to about one every seven minutes; verifying the full 64 bits (44 bits beyond the 20 index bits) makes it about one per three weeks of continuous search. Research by Hyatt and Cozzie in 2005 found that alpha-beta search tolerates surprisingly high collision rates before move choice changes, which is why 16-bit checks survive in practice, but a correctness-sensitive solver should verify every bit and also check that the stored best move is legal before playing it.

What the theory says

In hashing theory, Zobrist hashing is simple tabulation hashing: split a key into characters, look each up in a random table, XOR the results. Simple tabulation is 3-independent but not 4-independent. Take a shared set of features P and four features a, b, c, d, and form the positions P+a+c, P+a+d, P+b+c and P+b+d. The XOR of their four keys is always zero, so any three of the keys determine the fourth exactly; truly independent hashes would leave the fourth unpredictable. This structure does not make ordinary collisions likely, but it means guarantees that need 4-wise independence do not apply automatically. Pătraşcu and Thorup showed in 2011 that simple tabulation still gives strong guarantees for linear probing, cuckoo hashing and similar uses, which matches decades of practical experience in game engines. For an engineer the practical rule is short: use a good generator, use 64-bit keys, and never hand-pick key values.

Transposition table entries

A transposition table entry typically holds the verification bits of the key, the search depth, a score, a bound type (exact, lower or upper, from alpha-beta), the best move and an age stamp. A sketch in C:

typedef struct {
    uint64_t key;      /* full key, or key ^ data for lockless sharing */
    uint64_t data;     /* packed: move:16 score:16 depth:8 bound:2 age:6 */
} TTEntry;

TTEntry *tt;           /* 2^k entries */
uint64_t mask;         /* (1ULL << k) - 1 */

int tt_probe(uint64_t h, uint64_t *out) {
    TTEntry *e = &tt[h & mask];
    uint64_t k = e->key, d = e->data;
    if ((k ^ d) != h) return 0;          /* empty, other position, or torn write */
    *out = d;
    return 1;
}

void tt_store(uint64_t h, uint64_t d) {
    TTEntry *e = &tt[h & mask];
    /* replacement policy: prefer deeper or newer entries (omitted) */
    e->key = h ^ d;
    e->data = d;
}

The key ^ data trick, published by Hyatt and Mann, lets several search threads share one table without locks. If two threads write the same slot concurrently and a reader sees the key word from one write and the data word from the other, the XOR no longer equals the probing hash, and the torn entry is rejected as a miss. Replacement policy is the other big lever: two-bucket schemes keep one depth-preferred and one always-replace entry per slot, and the age field lets entries from previous searches be overwritten first. The general structure is the same open-addressing problem covered in hash tables, except that losing an entry is acceptable and wrong data is not.

Repetition detection and uses outside chess

The history stack of keys from the code above gives repetition detection almost for free. A position can only repeat since the last irreversible move (a pawn move or a capture, which also resets the fifty-move counter), and only with the same side to move, so the search scans back over every second key up to that point and compares. A match inside the search tree is usually scored as a draw immediately. Because the keys are exact only up to collision, engines that adjudicate real games confirm a claimed threefold repetition by comparing full board state, not just keys.

Outside chess the same scheme appears in Go programs, where it detects positional superko by storing keys of all earlier board states, in puzzle and planning solvers that need a visited set over states reachable by many paths, and in any system that maintains a fingerprint of a changing set: add or remove an element by XORing its random value. If the state is a multiset, XOR fails, because adding an element twice cancels; use addition modulo 2 to the 64 instead, which is still incremental and invertible. For fingerprints of sequences where order matters, a polynomial rolling hash such as the one in polynomial hashing is the right tool.

Failure modes

• Forgotten features. Not hashing side to move, castling rights or the en passant file makes different positions share keys systematically, not randomly. Debug-assert against a full recomputation.
• Bad randomness. Keys from a weak generator, or from a small set of hand-written constants, produce correlated keys and real collision rates far above the birthday estimate.
• Using the low bits twice. If the table index is the low k bits and the check value is also taken from the low bits, the check adds nothing. Take the index from one end and the check from the other.
• Trusting a hit blindly. A stored best move from a colliding entry may be illegal in the current position. Validate it before making it, or a rare collision becomes a crash.
• Multisets with XOR. Duplicated elements cancel. Use modular addition.
• Adversarial inputs. Zobrist keys are not a cryptographic hash. An attacker who learns your keys can build collisions; keep keys secret if anything security-relevant depends on them.

What to do next

1. Implement the Python position above, add the debug assertion, and fuzz it with random make and unmake sequences for a million moves.
2. Add castling and en passant features, hashing the en passant file only when a capture is legal, and test that repetition detection treats an uncapturable double push as no en passant at all.
3. Build a transposition table with a 16-bit check, count false hits by also storing full keys in a debug build, and compare with the 2 to the minus 16 estimate.
4. Switch to full-key verification and the key XOR data layout, then run the search with two threads.
5. Add repetition detection from the key history and test it on a known threefold sequence.
6. If you maintain a set fingerprint elsewhere, check whether it can contain duplicates and switch to modular addition if so.