Zobrist hashing

Deep dive

How it works

In: the current key plus the facts removed and added by a change · Out: the new 64-bit key · State: the key table (793 u64 for chess), the key history for repeat detection · Cost: O(1), 3-8 XORs per move; O(pieces) for a full recompute.

1. At startup fill piece[12][64], castle[16], ep_file[8], black from a fixed-seed PRNG. Fixed seed = reproducible hashes across runs (needed for opening books and debugging).
2. castle[r] for a rights mask r (4 bits: WK, WQ, BK, BQ) is the XOR of the single-right keys, with castle[0] = 0, so changing rights is h ^= castle[old] ^ castle[new].
3. Hash the en-passant file only if a pawn of the side to move can actually capture there (Polyglot rule). Otherwise two identical positions differ in hash just because a double push happened, which breaks repetition detection and halves TT hits after double pushes.
4. Make move: XOR out old ep key, move the piece (XOR from, XOR to), XOR out any captured piece, handle rook on castling and pawn on en-passant capture, update rights, toggle black, XOR in the new ep key.
5. Null move: toggle black, drop the ep key.
6. Repetition: keep the key history; look back 4, 6, 8 … plies (same side to move), no further than the half-move clock, because a capture or pawn move is irreversible.

Code

pub const EMPTY: u8 = 12; // pieces 0..12 = color * 6 + kind
pub const PAWN: u8 = 0;
pub const KING: u8 = 5;

pub struct Keys { pub piece: [[u64; 64]; 12], pub castle: [u64; 16], pub ep_file: [u64; 8], pub black: u64 }

fn splitmix64(s: &mut u64) -> u64 {
    *s = s.wrapping_add(0x9E37_79B9_7F4A_7C15);
    let mut z = *s;
    z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    z ^ (z >> 31)
}

impl Keys {
    pub fn new(mut seed: u64) -> Keys {
        let mut k = Keys { piece: [[0; 64]; 12], castle: [0; 16], ep_file: [0; 8], black: 0 };
        k.piece.iter_mut().flatten().for_each(|x| *x = splitmix64(&mut seed));
        k.ep_file.iter_mut().for_each(|x| *x = splitmix64(&mut seed));
        k.black = splitmix64(&mut seed);
        let single: [u64; 4] = std::array::from_fn(|_| splitmix64(&mut seed));
        for r in 0..16 {
            k.castle[r] = (0..4).filter(|b| r >> b & 1 == 1).fold(0, |h, b| h ^ single[b]);
        }
        k
    }
}

/// Rights bits: 1 = white O-O, 2 = white O-O-O, 4 = black O-O, 8 = black O-O-O.
fn castle_mask(sq: u8) -> u8 {
    match sq { 0 => !2, 4 => !3, 7 => !1, 56 => !8, 60 => !12, 63 => !4, _ => 0xF }
}

#[derive(Clone, Copy)]
pub struct Pos { pub board: [u8; 64], pub black: bool, pub castle: u8, pub ep: Option<u8>, pub key: u64 }

#[derive(Clone, Copy)]
pub struct Move { pub from: u8, pub to: u8, pub promo: Option<u8> }

impl Pos {
    fn set(&mut self, k: &Keys, sq: u8, pc: u8) {
        let old = self.board[sq as usize];
        if old != EMPTY { self.key ^= k.piece[old as usize][sq as usize]; }
        if pc != EMPTY { self.key ^= k.piece[pc as usize][sq as usize]; }
        self.board[sq as usize] = pc;
    }

    /// Ep key counts only if the side to move has a pawn that could capture.
    fn ep_key(&self, k: &Keys) -> u64 {
        let Some(ep) = self.ep else { return 0 };
        let (pawn_sq, our_pawn) = if self.black { (ep + 8, 6 + PAWN) } else { (ep - 8, PAWN) };
        let f = ep % 8;
        let left = f > 0 && self.board[(pawn_sq - 1) as usize] == our_pawn;
        let right = f < 7 && self.board[(pawn_sq + 1) as usize] == our_pawn;
        if left || right { k.ep_file[f as usize] } else { 0 }
    }

    pub fn full_key(&self, k: &Keys) -> u64 {
        let mut h = 0;
        for (sq, &pc) in self.board.iter().enumerate() {
            if pc != EMPTY { h ^= k.piece[pc as usize][sq]; }
        }
        if self.black { h ^= k.black; }
        h ^ k.castle[self.castle as usize] ^ self.ep_key(k)
    }

    pub fn make(&mut self, k: &Keys, m: Move) {
        let (from, to) = (m.from, m.to);
        let pc = self.board[from as usize];
        let kind = pc % 6;
        self.key ^= self.ep_key(k);
        if kind == PAWN && Some(to) == self.ep && from % 8 != to % 8 {
            self.set(k, if self.black { to + 8 } else { to - 8 }, EMPTY); // en-passant victim
        }
        self.set(k, from, EMPTY);
        self.set(k, to, m.promo.unwrap_or(pc)); // also XORs out a captured piece
        if kind == KING && from.abs_diff(to) == 2 {
            let (rf, rt) = if to > from { (from + 3, from + 1) } else { (from - 4, from - 1) };
            let rook = self.board[rf as usize];
            self.set(k, rf, EMPTY);
            self.set(k, rt, rook);
        }
        let rights = self.castle & castle_mask(from) & castle_mask(to);
        self.key ^= k.castle[self.castle as usize] ^ k.castle[rights as usize];
        self.castle = rights;
        self.ep = if kind == PAWN && from.abs_diff(to) == 16 { Some((from + to) / 2) } else { None };
        self.black = !self.black;
        self.key ^= k.black ^ self.ep_key(k);
        debug_assert_eq!(self.key, self.full_key(k));
    }

    pub fn make_null(&mut self, k: &Keys) {
        self.key ^= self.ep_key(k) ^ k.black;
        self.ep = None;
        self.black = !self.black;
    }
}

/// `history[n-d]` is the key d plies ago; only same-side positions since the last irreversible move.
pub fn is_repetition(history: &[u64], key: u64, halfmove_clock: usize) -> bool {
    let n = history.len();
    (4..=halfmove_clock.min(n)).step_by(2).any(|d| history[n - d] == key)
}

Complexity and constants

• Keys: 12·64 + 16 + 8 + 1 = 793 u64 ≈ 6.2 KiB, L1-resident.
• Incremental update: order of 1-3 ns per move; recomputing from scratch is about 32 table loads.
• Collision math: with b verification bits and k slots compared per probe, a probe for a position not in the table falsely matches with probability ≈ k / 2^b. Stockfish stores 16 bits and compares up to 3 entries: about 1 in 22,000 such probes. That is why the stored move is always checked for legality before use.
• Birthday bound for full 64-bit keys: among n distinct positions, P(any equal pair) ≈ 1 − e^(−n²/2⁶⁵), about 0.39 at n = 2³². Per-probe risk (above) is what matters for search.

Efficiency

• Cost: an incremental update is 3-8 XORs from an L1-resident 6.2 KiB key table, order of 1-3 ns; a full recompute is about 32 table loads. Bound: the later cache miss on the transposition-table probe, not the hash.
• Levers:
  • incremental XOR per change — O(changed facts) instead of O(state) — few changes per step
  • save the old key on make instead of re-XORing on unmake — one store — search stacks
  • prefetch the table bucket as soon as the key is known — hides the miss — hash-table lookups
  • extra incremental keys (pawn, material) — cache lookups on sub-structures — evaluation caches
  • fixed-seed PRNG keys — reproducible hashes for books and debugging — persistent keys
• Naive → standard → state of the art:
  • re-hash the whole board with a general hash · O(state) per node
  • Zobrist XOR, 64-bit · O(changes) per node
  • Zobrist plus prefetch of the table line, sub-structure keys · same O(changes), miss overlapped

Implementation notes

• Copy-make vs unmake. Copying a ≈ 80-byte position is often as fast as undoing; either way save the old key instead of re-XORing on unmake.
• Extra keys. Engines keep a pawn key (pawns + kings) for a pawn-structure cache and a material key (piece counts) for endgame lookup, updated in the same XORs.
• Prefetch. As soon as the new key is known (before generating moves), prefetch the TT bucket: _mm_prefetch / core::arch::aarch64::_prefetch. Stockfish prefetches the child's TT bucket as part of making the move.
• Key quality. Any decent 64-bit PRNG works; avoid low-entropy keys such as sequential numbers or a weak LCG's low bits, which create linear dependencies between keys.
• Go and other games. 2 colors × 361 points; also hash the ko point. Superko checks hash history the same way.
• Polyglot compatibility. If you read .bin opening books, you must use the published Polyglot Random64[781] table and its key layout, not your own keys.

Pitfalls

• Hashing the en-passant square whenever one exists: identical positions get different keys, repetitions are missed.
• Forgetting to update castling rights when a rook is captured on its home square (the castle_mask(to) term above).
• Not toggling side-to-move on a null move: the null-move child hits TT entries of the wrong side.
• Repetition check scanning past the last capture/pawn move, or including the odd plies.
• Trusting a TT move without a legality check: a collision then plays an illegal move or corrupts the board.
• Using 32-bit keys: with millions of nodes per second, false matches happen many times per second.

Variants and alternatives

In production

• Games: every major chess engine (Stockfish, Leela Chess Zero, Komodo, Ethereal), Polyglot and most opening book formats, go programs (GNU Go, KataGo) for superko and transpositions, shogi engines.
• Bioinformatics: ntHash computes the hash of each k-mer of a sequence from the previous one in O(1) (Mohamadi et al. 2016).
• Text search: the Rabin-Karp rolling hash updates a window hash per character (Karp and Rabin 1987).
• Cryptography: incremental hashing that updates a digest after a local change in O(change) (Bellare and Micciancio 1997).

Implementations

Sources

• Albert L. Zobrist, A New Hashing Method with Application for Game Playing, Technical Report 88, University of Wisconsin, 1970.
• Robert Hyatt, Anthony Cozzie, The Effect of Hash Signature Collisions in a Chess Program, ICGA Journal 28(3), 2005.
• Mihai Pătraşcu, Mikkel Thorup, The Power of Simple Tabulation Hashing, Journal of the ACM 59(3), 2012. paper
• Hamid Mohamadi, Justin Chu, Benjamin P. Vandervalk, Inanc Birol, ntHash: recursive nucleotide hashing, Bioinformatics 32(22), 2016. paper · code
• Richard M. Karp, Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM J. Research and Development 31(2), 1987. paper
• Mihir Bellare, Daniele Micciancio, A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Cost, EUROCRYPT 1997. paper
• Chess Programming Wiki, entries Zobrist Hashing and Repetitions (chessprogramming.org).