Tablebases, opening books and Chess960

Stage 18 · tag stage-18-tablebases · code in crates/engine/src/tablebase.rs, crates/syzygy and crates/chess/src/position.rs

The search and evaluation of the previous chapters are cb2026’s own judgement. This chapter adds knowledge from outside: perfect endgame play from tablebases. It also adds the last part of Chess960 support: the 960 starting positions themselves. And it adds opening books, for playing well-known opening moves without searching.

Endgame tablebases

With seven pieces or fewer on the board, chess is solved. Every such position has been searched to the end, backwards from every checkmate. The results are stored in tablebases. The Syzygy format, by Ronald de Man, is what nearly every engine uses. It comes in two kinds of file:

• WDL tables (win/draw/loss) answer “who wins?”. They are compact, and engines probe them during the search.
• DTZ tables (distance to zeroing) give the number of moves to the next capture or pawn move on the best path. That is what a won position needs to make progress under the fifty-move rule. Engines use them at the root to choose the move.

Syzygy results take the fifty-move rule into account, which adds two outcomes. A cursed win is a forced mate that takes too long: the fifty-move rule draws it first. A blessed loss is the same thing seen from the other side. cb2026 scores both as draws.

The 3- to 5-piece tables take about 1 GB; all 6-piece tables, about 150 GB. The repository doesn’t include them. scripts/download-syzygy.sh <directory> 3-4-5 fetches the 5-piece set, then setoption name SyzygyPath value <directory> (or set syzygy <directory> in the shell) loads it.

Who reads the files

The Syzygy format is an intricate compressed encoding, and a prober is thousands of lines of careful code with no strength to gain from writing it again. So this is the one place where cb2026 uses someone else’s chess code: the shakmaty-syzygy library (GPL-3.0, the prober behind Lichess’s tablebase server). The docs/PRD.md section “Tablebase probing” records that decision. cb2026 itself is MIT OR Apache-2.0, so the prober also sits behind a cargo feature, syzygy: a binary built with it is GPL-3.0 as a whole, and one built without it has no GPL code (README, “License”).

The search never sees it. The engine crate defines a small trait, and the separate cb2026-syzygy crate implements it:

/// When to probe.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct TablebaseParams {
    /// Probe in the search only with at least this much depth left (the UCI
    /// `SyzygyProbeDepth`; 1 probes at every node).
    pub probe_depth: u32,
    /// Probe only positions with at most this many pieces (`SyzygyProbeLimit`).
    pub probe_limit: u32,
}

impl Default for TablebaseParams {
    fn default() -> TablebaseParams {
        TablebaseParams {
            probe_depth: 1,
            probe_limit: 7,
        }
    }
}

The engine crate does no I/O, so it can’t open files itself. The program that embeds it (the cb2026 binary) hands it a loader function. Tests use a tiny in-memory “tablebase” instead, which says that king and queen against king is won, and that’s enough to test the search integration without any files.

Probing in the search

        // Endgame tablebases: right after a capture or pawn move, a covered position's result
        // is known exactly.
        if let Some((tb, tb_params)) = self.tablebase
            && ply > 0
            && depth >= tb_params.probe_depth
            && pos.halfmove_clock() == 0
            && tablebase::covers(tb, &tb_params, pos)
            && let Some(wdl) = tb.probe_wdl(pos)
        {
            self.tb_hits += 1;
            self.note(Note::Tablebase);
            let score = tablebase::score(wdl, ply);
            if self.techniques.tt {
                let stored = score_to_tt(score, ply);
                self.tt
                    .store(pos.hash(), None, stored, MAX_PLY, Bound::Exact, tt_pv);
            }
            return score;
        }

Three conditions decide when to probe:

• Few enough pieces. At most what the tables cover (and the SyzygyProbeLimit option).
• No castling rights. The tables don’t include them.
• Right after a capture or pawn move. A WDL result assumes the fifty-move counter has just been reset. Probing then also catches the moment the search crosses into tablebase territory, which is the useful moment.

A win scores TB_WIN − ply: above every evaluation and below every real mate, so the engine still prefers an actual checkmate, and a nearer tablebase win over a farther one. The result goes into the transposition table, and info ... tbhits counts the probes that answered.

At the root

        // In a tablebase position, keep only the move the tables recommend: it keeps the best
        // result and makes progress under the fifty-move rule. The search still runs (and
        // reports), but can only choose that move.
        if let Some(tb) = &self.tablebase
            && tablebase::covers(tb.as_ref(), &self.tablebase_params, position)
            && let Some((_, mv)) = tb.probe_root(position)
            && root_moves.contains(&mv)
        {
            root_moves = vec![mv];
        }

When the game itself is in the tables, the DTZ tables pick the move. Searching wouldn’t help: a search sees “won” everywhere and has no reason to make progress, so it can shuffle until the fifty-move rule draws the game. The tables’ move always keeps the best result and heads for the next zeroing move.

Chess960

Chess960 (Fischer Random Chess) shuffles the back rank: the bishops on opposite colours, the king somewhere between the rooks, the black pieces mirroring the white ones. That gives 960 possible starting positions. cb2026 handled Chess960 castling from stage 2 (castling is “king takes own rook”, and the rights are stored as rook files) and Shredder-FEN from stage 1. What was missing was the starting positions themselves.

They are numbered 0 to 959 (Reinhard Scharnagl’s numbering; number 518 is the standard position), and the number decodes into a back rank one piece at a time:

    /// Chess960 starting position number `n` (0–959, Scharnagl's numbering; 518 is the standard
    /// starting position), or `None` if `n` is out of range.
    ///
    /// The back rank is built from `n` in mixed-radix steps: the light-squared bishop (4
    /// choices), the dark-squared bishop (4), the queen on one of the 6 empty squares, the two
    /// knights on 2 of the 5 left (10 ways), and the rooks and king, in that order, on the last
    /// three, so the king always stands between its rooks.
    pub fn chess960(n: u32) -> Option<Position> {
        if n >= 960 {
            return None;
        }
        let mut rank = [None; 8];
        let mut n = n as usize;
        rank[2 * (n % 4) + 1] = Some('B');
        n /= 4;
        rank[2 * (n % 4)] = Some('B');
        n /= 4;
        let empty = |rank: &[Option<char>; 8]| -> Vec<usize> {
            (0..8).filter(|&i| rank[i].is_none()).collect()
        };
        rank[empty(&rank)[n % 6]] = Some('Q');
        n /= 6;
        const KNIGHTS: [(usize, usize); 10] = [
            (0, 1),
            (0, 2),
            (0, 3),
            (0, 4),
            (1, 2),
            (1, 3),
            (1, 4),
            (2, 3),
            (2, 4),
            (3, 4),
        ];
        let (first, second) = KNIGHTS[n];
        let free = empty(&rank);
        rank[free[first]] = Some('N');
        rank[free[second]] = Some('N');
        for (square, piece) in empty(&rank).into_iter().zip(['R', 'K', 'R']) {
            rank[square] = Some(piece);
        }
        let white: String = rank
            .iter()
            .map(|p| p.expect("every square filled"))
            .collect();
        // Shredder-FEN castling: the files of the rooks.
        let rook_files: Vec<char> = (0..8)
            .filter(|&i| rank[i] == Some('R'))
            .map(|i| (b'A' + i as u8) as char)
            .collect();
        let castling: String = rook_files
            .iter()
            .rev()
            .copied()
            .chain(rook_files.iter().rev().map(|c| c.to_ascii_lowercase()))
            .collect();
        let fen = format!(
            "{}/pppppppp/8/8/8/8/PPPPPPPP/{white} w {castling} - 0 1",
            white.to_ascii_lowercase()
        );
        Position::from_fen(&fen).ok()
    }

A test builds all 960 and checks that they are distinct and legal, with the bishops on opposite colours and the king between the rooks.

• In the shell, new960 [n] starts from position n, or a random one.
• match --chess960 plays test matches from the 960 positions and sets UCI_Chess960 in both engines. A first run played Chess960 games with castling to completion, with no illegal moves.

Opening books

At the start of a game the search spends its time rediscovering well-known opening theory, and it plays the same move every time from the same position. An opening book maps positions to good moves, each with a weight. With OwnBook on, the engine looks the position up before searching and plays a book move at once, chosen at random in proportion to the weights:

        // The opening book: play its move at once (unless asked to analyse).
        if self.own_book
            && !limits.infinite
            && limits.search_moves.is_empty()
            && let Some(book) = &self.book
        {
            // The dice: the clock's nanoseconds, mixed with the position.
            let nanos = std::time::SystemTime::now()
                .duration_since(std::time::UNIX_EPOCH)
                .map_or(0, |d| d.subsec_nanos());
            let random = u64::from(nanos) ^ position.hash();
            if let Some(mv) = book.pick(position, random)
                && root_moves.contains(&mv)
            {
                return SearchResult {
                    best_move: Some(mv),
                    ..SearchResult::default()
                };
            }
        }

cb2026 reads the Polyglot format (.bin files), which nearly every engine and GUI supports. A book is a sorted list of 16-byte entries: position key, move, weight and some learning data the format reserves, all big-endian. Looking a position up is a binary search for its key:

    /// The book's moves for `pos`, heaviest first (illegal ones, from a corrupt book or a key
    /// collision, are skipped).
    pub fn moves(&self, pos: &Position) -> Vec<BookMove> {
        let key = polyglot_key(pos);
        let start = self.entries.partition_point(|e| e.0 < key);
        let mut moves: Vec<BookMove> = self.entries[start..]
            .iter()
            .take_while(|e| e.0 == key)
            .filter_map(|&(_, raw, weight)| decode_move(pos, raw).map(|mv| BookMove { mv, weight }))
            .collect();
        moves.sort_by_key(|m| std::cmp::Reverse(m.weight));
        moves
    }

The key is a Zobrist hash (chapter 4), with one difference that matters: the random numbers are fixed by the format. Any program can then compute the same key for the same position and read any book. The 781 numbers (768 for pieces on squares, 4 for castling rights, 8 for en passant files, 1 for the side to move) were published with Fabien Letouzey’s PolyGlot program. cb2026 takes them from the format’s published description and checks them against its test hashes:

/// The Polyglot key of `pos`: the XOR of the format's random numbers for every piece on its
/// square, each castling right, the en passant file (only when a pawn could actually capture
/// there) and White to move.
pub fn polyglot_key(pos: &Position) -> u64 {
    let mut key = 0;
    for square in pos.occupied() {
        let piece = pos.piece_at(square).expect("an occupied square");
        // The format's piece kinds: black pawn, white pawn, black knight, white knight, ...
        let kind = 2 * piece.piece_type.index() + usize::from(piece.color == Color::White);
        key ^= POLYGLOT_KEYS[64 * kind + square.index()];
    }
    let rights = [
        (Color::White, CastlingSide::KingSide),
        (Color::White, CastlingSide::QueenSide),
        (Color::Black, CastlingSide::KingSide),
        (Color::Black, CastlingSide::QueenSide),
    ];
    for (i, (color, side)) in rights.into_iter().enumerate() {
        if pos.castling().has(color, side) {
            key ^= POLYGLOT_KEYS[768 + i];
        }
    }
    // cb2026 only records an en passant square when an enemy pawn can capture there, which is
    // exactly the Polyglot rule.
    if let Some(square) = pos.en_passant() {
        key ^= POLYGLOT_KEYS[772 + square.file().index()];
    }
    if pos.side_to_move() == Color::White {
        key ^= POLYGLOT_KEYS[780];
    }
    key
}

One detail is easy to get wrong: the en passant file only counts when a pawn of the side to move can actually make the capture. cb2026’s positions already record en passant squares that way (chapter 4), for the same reason: equal positions must hash equally.

Polyglot encodes castling as “king takes rook” (e1h1), the same convention cb2026 uses internally, so castling moves need no special treatment.

The book is off by default. Tests need to see the engine’s own moves, a book would make every test game start alike, and GUIs and tournament managers usually supply their own books. In the shell:

> set book /path/to/book.bin
Opening book with 6 entries.
> book
Book moves:
  e4       weight    50  (50%)
  d4       weight    30  (30%)
  Nf3      weight    20  (20%)
The engine ignores the book (set ownbook on to use it).

The repository has no book, but the v1.0.0 release comes with one: September 2026’s, made from Lichess’s games as below (cb2026-lichess-2026-09.bin). Any Polyglot book works with cb2026, and it can make its own.

Making a book from people’s games

Lichess publishes every rated game played on it, a month to a file, under the Creative Commons CC0 licence: about 90 million games and 30 GB a month. The make-book tool turns games like these into a Polyglot book. It reads them from standard input, so the month is decompressed on the way in and never stored:

scripts/lichess-book.sh 2026-09 ~/books/lichess-2026-09.bin

It keeps the games where both players are rated 2200 or more, at blitz or slower, with no bots. Lichess’s files include engines playing each other on BOT accounts, at ratings well above any person’s: in the first 150,000 games of September 2026, bots played most of the games between two players rated 2600 or more. Of the whole month, 1.7% of the games passed: 1,499,615 of 89,616,462. For each position in their first 20 plies, the tool counts the move played and what it scored for the side that played it. Positions are found by their Polyglot key, so moves reached by different move orders add up:

    /// Counts the first `plies` plies of `game`, which ended `result` ("1-0", "0-1" or
    /// "1/2-1/2").
    pub fn add_game(&mut self, game: &PgnGame, result: &str, plies: usize) {
        // Points for White and for Black: 2 for a win, 1 for a draw, 0 for a loss.
        let points = match result {
            "1-0" => [2, 0],
            "0-1" => [0, 2],
            _ => [1, 1],
        };
        let mut pos = game.start.clone();
        for &mv in game.moves.iter().take(plies) {
            let stats = self
                .moves
                .entry((polyglot_key(&pos), encode_move(mv)))
                .or_default();
            match points[pos.side_to_move().index()] {
                2 => stats.wins += 1,
                1 => stats.draws += 1,
                _ => stats.losses += 1,
            }
            pos.make_move(mv);
        }
        self.games_used += 1;
    }

A move goes into the book when at least 20 games played it and it scored at least 35%. Its weight is its points, two for a win and one for a draw, as in PolyGlot’s own make-book. The engine then plays popular moves that do well most often, and a move nobody wins with not at all:

    /// The book: the moves played in at least `min_games` games that scored at least
    /// `min_score` and won some points, each weighted by its points (scaled down where a
    /// position's points don't fit the format's 16 bits).
    pub fn book(&self, settings: &BookSettings) -> OpeningBook {
        let mut by_position: HashMap<u64, Vec<(u16, u32)>> = HashMap::new();
        for (&(key, mv), stats) in &self.moves {
            if stats.games() >= settings.min_games
                && stats.score() >= settings.min_score
                && stats.points() > 0
            {
                by_position
                    .entry(key)
                    .or_default()
                    .push((mv, stats.points()));
            }
        }
        let mut entries = Vec::new();
        for (key, moves) in by_position {
            let most = moves.iter().map(|&(_, points)| points).max().unwrap_or(0);
            let scale = f64::from(u16::MAX) / f64::from(most.max(u32::from(u16::MAX)));
            for (mv, points) in moves {
                let weight = (f64::from(points) * scale).round().max(1.0) as u16;
                entries.push((key, mv, weight));
            }
        }
        OpeningBook::from_entries(entries)
    }

The minimum number of games matters more than it looks. A blitz game is usually decided long after the opening, so one game says almost nothing about its first moves. Twenty games of the same move begin to.

September 2026’s book took 58 minutes to make, nearly all of it downloading the 29 GB file. Of the 8,036,080 different moves the tool counted, in all the positions it saw, 97,432 passed, a book of 1.6 MB: most of the rest were played in fewer than 20 games. From the starting position the engine plays 1.e4 47% of the time, 1.d4 33%, 1.Nf3 9% and 1.c4 6%; 1.b3, 1.g3 and 1.f4 about 1% each; and 13 more moves, 1.Na3 among them, less than half a percent each. Those passed the test, played often enough and scoring well enough, and their small weight keeps them rare.

Pitfalls

• Probing too often. Every probe reads from disk (or the operating system’s file cache). SyzygyProbeDepth stops probes near the leaves, where they cost more than they save.
• Shuffling in won endings. A search that knows “won” but not “how” can draw a won game under the fifty-move rule. That’s why the root uses the DTZ tables.
• Castling rights. A position with castling rights is never in the tables, even with few pieces.
• Chess960 notation. With UCI_Chess960 on, castling is sent as king-takes-rook (e1h1), and GUIs expect it. cb2026 accepts both notations on input.

What it’s worth

Further reading

• Chess Programming Wiki: Syzygy Bases, Endgame Tablebases, Chess960, Opening Book, PolyGlot.
• syzygy-tables.info, to look up any tablebase position.