Transposition table

Deep dive

How it works

In: a 64-bit state key, depth, window · Out: a cutoff score, a best move to try first, or a miss · State: the table (buckets of 4 entries) and a generation counter · Cost: O(1) per probe or store, one cache line.

1. Index. bucket = (key as u128 * n_buckets as u128) >> 64: uses high key bits, any table size, no modulo.
2. Probe. Read the 4 entries of the bucket; an entry matches if stored_xor ^ data == key. Convert mate scores from node-relative to ply-relative.
3. Use. If depth_stored ≥ depth and (Exact, or Lower with score ≥ β, or Upper with score ≤ α), return the score (at non-PV nodes). Otherwise use the move for ordering and the stored eval instead of recomputing it.
4. Store at the end of the node with bound Lower (fail high: score ≥ β), Upper (fail low: no move beat α) or Exact.
5. Replace. Same key → overwrite unless the old entry is much deeper and the new one isn't Exact; keep the old move if the new one is empty. Otherwise evict the entry with the lowest depth − 8·age, where age = generations since it was written. A new generation starts each search (each move).
6. Lockless. Writers store key ^ data and data as two independent 64-bit words. A reader that sees a torn pair (word 1 from one write, word 2 from another) recomputes a wrong key and treats it as a miss.

64-byte bucket:  [kx0 d0][kx1 d1][kx2 d2][kx3 d3]      kx = key ^ d
data (u64):  | gen 6 | bound 2 | depth 8 | eval 16 | score 16 | move 16 |
              63   58  57   56   55   48   47  32    31   16    15     0

Code

use std::sync::atomic::{AtomicU64, Ordering::Relaxed};

pub const MATE: i32 = 31_000;
pub const MAX_PLY: i32 = 128;
const DEPTH_OFFSET: i32 = 8; // stored depth = depth + 8, so quiescence depths down to -8 fit in u8

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Bound { None = 0, Upper = 1, Lower = 2, Exact = 3 }

#[derive(Clone, Copy, Debug)]
pub struct Hit { pub mv: u16, pub score: i32, pub eval: i32, pub depth: i32, pub bound: Bound }

#[repr(C, align(64))]
struct Bucket([AtomicU64; 8]); // 4 × (key ^ data, data)

pub struct Tt { buckets: Box<[Bucket]>, gen: u8 }

fn to_tt(s: i32, ply: i32) -> i32 {
    if s > MATE - MAX_PLY { s + ply } else if s < MAX_PLY - MATE { s - ply } else { s }
}
fn from_tt(s: i32, ply: i32) -> i32 {
    if s > MATE - MAX_PLY { s - ply } else if s < MAX_PLY - MATE { s + ply } else { s }
}

fn pack(mv: u16, score: i32, eval: i32, depth: i32, bound: Bound, gen: u8) -> u64 {
    mv as u64
        | (score as i16 as u16 as u64) << 16
        | (eval as i16 as u16 as u64) << 32
        | ((depth + DEPTH_OFFSET).clamp(0, 255) as u64) << 48
        | (bound as u64) << 56
        | ((gen & 63) as u64) << 58
}
fn depth_of(d: u64) -> i32 { (d >> 48 & 0xFF) as i32 - DEPTH_OFFSET }
fn gen_of(d: u64) -> u8 { (d >> 58) as u8 }

impl Tt {
    pub fn new(mib: usize) -> Tt {
        let n = (mib << 20) / 64;
        Tt { buckets: (0..n).map(|_| Bucket(Default::default())).collect(), gen: 0 }
    }
    pub fn new_search(&mut self) { self.gen = (self.gen + 1) & 63; }

    #[inline]
    fn bucket(&self, key: u64) -> &Bucket {
        &self.buckets[((key as u128 * self.buckets.len() as u128) >> 64) as usize]
    }

    pub fn probe(&self, key: u64, ply: i32) -> Option<Hit> {
        let b = self.bucket(key);
        for i in 0..4 {
            let data = b.0[2 * i + 1].load(Relaxed);
            if data != 0 && b.0[2 * i].load(Relaxed) ^ data == key {
                let bound = match data >> 56 & 3 { 1 => Bound::Upper, 2 => Bound::Lower, 3 => Bound::Exact, _ => Bound::None };
                return Some(Hit {
                    mv: data as u16,
                    score: from_tt((data >> 16) as u16 as i16 as i32, ply),
                    eval: (data >> 32) as u16 as i16 as i32,
                    depth: depth_of(data),
                    bound,
                });
            }
        }
        None
    }

    pub fn store(&self, key: u64, ply: i32, mut mv: u16, score: i32, eval: i32, depth: i32, bound: Bound) {
        let b = self.bucket(key);
        let (mut slot, mut worst) = (0, i32::MAX);
        for i in 0..4 {
            let data = b.0[2 * i + 1].load(Relaxed);
            if b.0[2 * i].load(Relaxed) ^ data == key && data != 0 {
                if mv == 0 { mv = data as u16; } // keep the old best move
                let fresh = gen_of(data) == self.gen;
                if bound != Bound::Exact && fresh && depth + 4 < depth_of(data) { return; }
                slot = i;
                break;
            }
            let age = (self.gen.wrapping_sub(gen_of(data)) & 63) as i32;
            let value = depth_of(data) - 8 * age; // empty slots have depth -8: evicted first
            if value < worst { worst = value; slot = i; }
        }
        let data = pack(mv, to_tt(score, ply), eval, depth, bound, self.gen);
        b.0[2 * slot].store(key ^ data, Relaxed);
        b.0[2 * slot + 1].store(data, Relaxed);
    }

    /// UCI "hashfull" in permille, sampled from the first 250 buckets.
    pub fn hashfull(&self) -> usize {
        self.buckets.iter().take(250)
            .flat_map(|b| (0..4).map(move |i| b.0[2 * i + 1].load(Relaxed)))
            .filter(|&d| d != 0 && gen_of(d) == self.gen).count()
    }
}

pub fn tt_cutoff(h: &Hit, depth: i32, alpha: i32, beta: i32) -> bool {
    h.depth >= depth
        && match h.bound {
            Bound::Exact => true,
            Bound::Lower => h.score >= beta,
            Bound::Upper => h.score <= alpha,
            Bound::None => false,
        }
}

Complexity and constants

• 16 B/entry → 65,536 entries per MiB; a 1 GiB table holds 2²⁶ ≈ 67 M entries.
• Probe cost is dominated by the cache miss: DRAM order of 80-100 ns plus a TLB miss on 4 KiB pages for large tables. With 2 MiB pages one TLB entry covers 32,768 buckets.
• Falsely matching a stored position needs a 64-bit key match: per probe ≈ 4·2⁻⁶⁴, negligible. Engines with 16-bit verification (Stockfish) accept about 3·2⁻¹⁶ per probe and always check move legality.
• Sizing: an engine at N nodes/s for T seconds writes up to N·T entries (minus quiescence nodes if those aren't stored). Beyond a few times that, larger tables bring diminishing returns.

Efficiency

• Cost: a probe or store touches one 64-byte bucket: one DRAM miss, order of 80-100 ns, unless prefetched; 16 B per entry, 65,536 entries per MiB. Bound: memory latency.
• Levers:
  • prefetch the bucket as soon as the child key is known — overlaps the miss with move generation — every probe
  • 2 MiB huge pages — one TLB entry covers 32,768 buckets — tables of hundreds of MiB and up
  • buckets of 4 entries with depth-and-age replacement — keeps the useful entries — full tables
  • lockless key ⊕ data stores — no lock traffic between threads — Lazy SMP
  • 16-bit key verification (Stockfish) — more entries per line, about 3·2⁻¹⁶ false hits per probe — memory-bound searches
• Naive → standard → state of the art:
  • no table · every transposition and iteration searched again
  • locked table, always-replace · correct but contended
  • lockless buckets, prefetch, huge pages, generation aging · one cache miss per node

Implementation notes

• Prefetch the bucket as soon as the child's key is known (before move generation), so the miss overlaps useful work.
• Huge pages. Linux: allocate 2 MiB-aligned memory and madvise(MADV_HUGEPAGE); Windows needs the "Lock pages in memory" privilege for large pages. Measurable speedups for tables of hundreds of MiB and up.
• Zeroing. (0..n).map(...).collect() touches every page once; for multi-GiB tables use alloc_zeroed (lazily zeroed pages from the OS) or clear with several threads.
• Relaxed atomics compile to plain loads and stores on x86-64 and ARM64; they exist so the racy access is defined behaviour in Rust/C++. The XOR check, not memory ordering, provides consistency.
• What to store in quiescence. Many engines store qsearch results at depth 0 or −1; they are cheap to recompute but give cutoffs for repeated capture sequences.
• Clear between games, not between moves; generations handle aging within a game.
• PV nodes. Don't cut at PV nodes (or only with Exact bounds and enough depth); it shortens the displayed PV and interacts badly with repetition detection.

Pitfalls

• Storing mate scores root-relative: a mate found via a transposition at another ply reports the wrong distance, can even claim mate in a drawn line.
• Trusting a TT move without a pseudo-legality check: crash or corrupted board on a key collision.
• Overwriting a deep entry with a shallow qsearch result for the same key (the depth+4 guard above).
• key % size with power-of-two sizes uses low key bits that may also be used for verification, wasting entropy; the multiply-shift index uses the high bits.
• Graph-history interaction: a position scored as a draw by repetition is stored and reused where it is not a repetition. Usually tolerated; reduce by not storing draw scores at shallow depth.
• Treating an empty entry (data == 0) as a match for key 0.

Variants and alternatives

In production

• Games: Stockfish (tt.cpp: clusters, 16-bit keys, generation aging, mul_hi64 indexing, large pages), Crafty (lockless XOR hashing), Ethereal, Berserk; Leela Chess Zero uses a separate NN-evaluation cache keyed by position hash.
• Puzzle solving: IDA* with a transposition table (Reinefeld and Marsland 1994).
• Model checking: SPIN's bitstate hashing stores visited states as bits in a lossy table (Holzmann 1998); hash compaction keeps only a short signature per state (Stern and Dill 1995).

Implementations

Sources

• Dennis M. Breuker, Jos W.H.M. Uiterwijk, H. Jaap van den Herik, Replacement Schemes for Transposition Tables, ICCA Journal 17(4), 1994.
• Robert Hyatt, Timothy Mann, A Lock-less Transposition Table Implementation for Parallel Search Chess Engines, ICGA Journal 25(1), 2002.
• Albert L. Zobrist, A New Hashing Method with Application for Game Playing, Technical Report 88, University of Wisconsin, 1970.
• Stockfish source, src/tt.h and src/tt.cpp.
• Alexander Reinefeld, T. Anthony Marsland, Enhanced Iterative-Deepening Search, IEEE TPAMI 16(7), 1994. paper
• Gerard J. Holzmann, An Analysis of Bitstate Hashing, Formal Methods in System Design 13, 1998. paper
• Ulrich Stern, David L. Dill, Improved Probabilistic Verification by Hash Compaction, CHARME 1995. paper