The transposition table

Stage 8 · tag stage-08-tt · code in crates/engine/src/tt.rs and search.rs

1. e4 e5 2. Nf3 and 1. Nf3 e5 2. e4 reach the same position by different routes. Chess is full of these transpositions, and a plain alpha-beta search treats each route as a new position and searches it again. Iterative deepening makes it worse: depth 7 repeats all of depth 6’s work. The transposition table (TT) remembers what the search found in every position it visited, so it can reuse the result or at least start from the best move.

What gets stored

The TT is one large array of entries indexed by the position’s Zobrist key (chapter 4):

/// What a stored score means.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Bound {
    /// The exact score.
    Exact,
    /// A lower bound: the real score is at least this (the search failed high).
    Lower,
    /// An upper bound: the real score is at most this (the search failed low).
    Upper,
}

/// One stored result.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Entry {
    /// The position's Zobrist key.
    pub key: u64,
    /// The best move found, if any (a fail-low node may have none).
    pub best_move: Option<Move>,
    /// The score, with mates relative to this position (see [`score_to_tt`]).
    pub score: i32,
    /// The depth the position was searched to.
    pub depth: u8,
    /// What kind of score it is.
    pub bound: Bound,
    /// The search that stored it, for replacement.
    pub generation: u8,
    /// Whether the position is or has been on the principal variation (the search's `tt_pv`
    /// flag, after Stockfish's).
    pub pv: bool,
}

Two parts of an entry are useful in different ways:

• The best move. Even when the stored result is too shallow to reuse, its best move is probably still best, and searching it first gives alpha-beta its early cutoffs (chapter 5). With iterative deepening, depth d leaves a best move behind for almost every position depth d + 1 visits. Most of the TT’s value comes from this.
• The score, if it was searched at least as deep as the search now needs. Then the position needn’t be searched at all: a TT cutoff.

Bounds

Alpha-beta rarely learns a position’s exact score. When a move fails high (≥ beta), the search stops early: it only knows the score is at least that. When every move fails low, it only knows the score is at most alpha. So each entry records which kind of score it holds, and a later search uses it only when it settles the question that search is asking:

Here is the probe at the top of negamax, then the store at the end:

        // Transposition table: a deep enough result may settle this position at once, and in
        // any case its best move is searched first.
        // (Not in a singular extension's search: the entry is about the node with every move.)
        let mut tt_move = None;
        let mut tt_entry = None;
        if self.techniques.tt
            && excluded.is_none()
            && let Some(entry) = self.tt.probe(pos.hash())
        {
            self.note(Note::TtHit);
            tt_entry = Some(entry);
            tt_move = entry.best_move.filter(|mv| moves.contains(mv));
            if u32::from(entry.depth) >= depth {
                let score = score_from_tt(entry.score, ply);
                let usable = match entry.bound {
                    Bound::Exact => true,
                    Bound::Lower => score >= beta,
                    Bound::Upper => score <= alpha,
                };
                if usable {
                    self.note(Note::TtCutoff);
                    pv.extend(tt_move);
                    return score;
                }
            }
        }

        // (Not in a singular extension's search: its result leaves the best move out.)
        if self.techniques.tt && !self.aborted && excluded.is_none() {
            // After a fail low every move was refuted, so none of them is known to be best.
            let move_to_store = if bound == Bound::Upper {
                None
            } else {
                best_move
            };
            let score = score_to_tt(best, ply);
            self.tt
                .store(pos.hash(), move_to_store, score, depth, bound, tt_pv);
        }

(The excluded conditions came later, with singular extensions in chapter 14.1.)

The stored move is checked against the legal moves before it is used. A wrong move could come from two different positions sharing a key, which is very rare with 64-bit keys but not impossible.

Mate scores

A mate score counts plies from the root: MATE − 7 means mate in 7 plies from where the search started. But the TT stores positions, and the same position can turn up at ply 3 in one line and ply 5 in another. So mate scores are stored relative to the position itself (“mated in 2 plies from here”) and converted back when read. Forget this, and the engine reports wrong mate distances or shuffles its pieces instead of mating.

Indexing and replacement

The table has a fixed size, set with the UCI Hash option (16 MB by default) or set hash in the shell. A key picks a slot with one multiplication instead of a division:

let index = ((key as u128 * len as u128) >> 64) as usize;

This treats the key as a fraction between 0 and 1 and scales it to the table size, which works for any size. The trick is from Daniel Lemire, “A fast alternative to the modulo reduction” (2016).

Slots fill up fast, so the table needs a replacement strategy for when a new result maps to an occupied slot:

    /// Stores a search result for the position with `key`, and whether the position is or has
    /// been on the principal variation (`pv`).
    pub fn store(
        &self,
        key: u64,
        best_move: Option<Move>,
        score: i32,
        depth: u32,
        bound: Bound,
        pv: bool,
    ) {
        let generation = self.generation.load(Ordering::Relaxed);
        let depth = depth.min(u8::MAX as u32) as u8;
        let slot = self.slot_to_store(key, generation);
        let old = slot.entry();
        let replace = match old {
            None => true,
            Some(old) => old.key == key || old.generation != generation || depth >= old.depth,
        };
        if replace {
            // A fail-low result has no best move; keep the one already known for this position.
            let best_move = best_move.or_else(|| {
                old.filter(|old| old.key == key)
                    .and_then(|old| old.best_move)
            });
            slot.write(key, pack(best_move, score, depth, bound, generation, pv));
        }
    }

    /// Where a result for `key` goes: the slot that already holds the position, else an empty
    /// one, else the one whose entry is worth least (see [`worth`]). With buckets off there is
    /// only one candidate.
    fn slot_to_store(&self, key: u64, generation: u8) -> &Slot {
        let slots = self.slots_for(key);
        slots
            .iter()
            .find(|slot| slot.entry_for(key).is_some())
            .unwrap_or_else(|| {
                // `min_by_key` returns the first of equals, so the first empty slot.
                slots
                    .iter()
                    .min_by_key(|slot| slot.entry().map_or(i32::MIN, |e| worth(e, generation)))
                    .expect("a key always has at least one slot")
            })
    }

cb2026 replaces an entry if it is for the same position, from an earlier search, or searched no deeper than the new result. Deep results cost the most to recompute, so they’re kept until they go stale. Stronger engines give each key a bucket of several slots and weigh age against depth; chapter 8.1 adds both, which is why the code above picks a slot first. The Chess Programming Wiki lists the options.

What it saves

Each pair below has the same move and score, with and without the table (set tt off), at depth 6:

The table also lasts from one move to the next. When the engine moves and the opponent replies, the new position was already searched two plies deep in the last search, so the next search starts with good moves for most positions it visits. ucinewgame clears it.

GUIs show how full the table is: info ... hashfull 312 means 31.2%, estimated from the first thousand slots.

Pitfalls

• Storing garbage. A search stopped by the clock returns made-up scores. Nothing is stored once the search has been stopped.
• Graph history interaction. The TT doesn’t know how a position was reached. A position that is a draw by repetition on one path might be stored as a draw and reused on a path where it isn’t. Every engine accepts this small inaccuracy.
• Truncated principal variations. A TT cutoff ends the line at that position, so the PV can come out shorter than the depth. Later stages can rebuild it from the table.
• Minimax comparisons. The TT’s bounds come from alpha-beta, so the minimax comparison test switches it off.

What it’s worth

Further reading

• Chess Programming Wiki: Transposition Table, Replacement Strategies, Graph History Interaction.
• Albert Zobrist, “A New Hashing Method with Application for Game Playing” (1970): the hashing behind the table.
• Daniel Lemire, “A fast alternative to the modulo reduction” (2016).