Zobrist hashing and talking to GUIs (UCI)

Stage 4 · tag stage-04-uci · code in crates/chess, crates/engine, crates/protocol

By the end of this stage cb2026 is a real, if hopeless, chess engine. A GUI can load it, send it positions and get a legal move back: for now a random one. Three pieces make that possible. Hash keys let us recognise positions, algebraic notation lets people read moves, and the UCI protocol lets GUIs talk to the engine.

Zobrist hashing

The search will meet the same position again and again, reached by different move orders, and the repetition rule needs to spot recurring positions. Comparing whole positions is slow, so each position gets a 64-bit fingerprint.

Zobrist hashing gives every feature a fixed random 64-bit number:

one per (piece, square);
one for “Black to move”;
one per castling right;
one per en passant file.

The key is the XOR of the numbers for the features present:

/// The key for `piece` standing on `square`.
pub fn piece_square(piece: Piece, square: Square) -> u64 {
    let piece_index = piece.color.index() * 6 + piece.piece_type.index();
    KEYS[piece_index * 64 + square.index()]
}

/// The key XORed in when Black is to move.
pub fn black_to_move() -> u64 {
    KEYS[SIDE_INDEX]
}

/// The combined key for a set of castling rights.
pub fn castling(rights: CastlingRights) -> u64 {
    let mut key = 0;
    for color in Color::ALL {
        for side in CastlingSide::ALL {
            if rights.has(color, side) {
                key ^= KEYS[CASTLING_INDEX + color.index() * 2 + side.index()];
            }
        }
    }
    key
}

/// The key for an en passant square on `file`.
pub fn en_passant(file: File) -> u64 {
    KEYS[EN_PASSANT_INDEX + file.index()]
}

Because x ^ k ^ k == x, the key updates incrementally. Moving a knight from g1 to f3 is key ^= N_g1 ^ N_f3, a couple of instructions. cb2026 updates the key inside the same functions that move pieces, so it can never fall out of step. A test walks the move tree from every perft position and checks, at every node, that the incremental key equals one computed from scratch.

Different positions can share a key, but with 64 random bits it’s rare enough that engines accept the risk. The transposition table in stage 8 also double-checks the moves it gets back.

The shell’s zobrist command lists every part of the current key.

Algebraic notation

UCI speaks in g1f3, but people write Nf3. Standard algebraic notation (SAN) names the piece and destination:

captures add x (Bxe5);
promotions add =Q;
castling is O-O or O-O-O;
check and mate add + or #.

When two pieces of the same kind could reach the square, SAN adds the starting file (Nbd7), else the rank (R1e2), else both.

    /// Writes `mv`, which must be legal here, in SAN.
    ///
    /// ```
    /// use cb2026_chess::Position;
    ///
    /// let pos = Position::startpos();
    /// let mv = pos.parse_uci_move("g1f3").unwrap();
    /// assert_eq!(pos.to_san(mv), "Nf3");
    /// ```
    pub fn to_san(&self, mv: Move) -> String {
        let mut san = self.san_without_check(mv);
        let mut after = self.clone();
        after.make_move(mv);
        if after.in_check() {
            san.push(if after.legal_moves().is_empty() {
                '#'
            } else {
                '+'
            });
        }
        san
    }

Reading SAN is deliberately forgiving: annotations are ignored, 0-0 works, and so do e8Q and over-specified moves like Ng1f3. The test is strict, though: every legal move in every perft position must survive writing and reading back.

The Engine API

The engine crate does no I/O, so the protocols and the shell drive it through one call:

    /// Chooses a move in `position`.
    ///
    /// `history` holds the hash keys of the earlier positions in the game. `stop` may be set by
    /// another thread to end the search early. `on_info` is called after each completed depth,
    /// and once more for a depth cut short if it found a move worth playing.
    ///
    /// The search uses **iterative deepening**: it searches to depth 1, then 2, then 3, and so
    /// on, until a limit says stop. Each depth starts with the best move of the one before,
    /// and when time runs out mid-depth the engine still has a complete answer to fall back on.
    pub fn search(
        &mut self,
        position: &Position,
        history: &[u64],
        limits: &Limits,
        stop: &AtomicBool,
        on_info: &mut dyn FnMut(&SearchInfo),
    ) -> SearchResult {
        self.search_following_root(position, history, limits, stop, on_info, None)
    }

    /// [`Engine::search`], also telling `on_root`, if given, where the main thread's root loop
    /// is as it goes: at each root move, whenever the search looks at the clock, and at once
    /// when the search goes back over something ([`root`]). The search is the same, node for
    /// node, followed or not.
    pub fn search_following_root(
        &mut self,
        position: &Position,
        history: &[u64],
        limits: &Limits,
        stop: &AtomicBool,
        on_info: &mut dyn FnMut(&SearchInfo),
        on_root: Option<&mut dyn FnMut(&RootInfo<'_>)>,
    ) -> SearchResult {
        let start = Instant::now();
        let mut root_moves: Vec<Move> = position
            .legal_moves()
            .iter()
            .copied()
            .filter(|mv| limits.search_moves.is_empty() || limits.search_moves.contains(mv))
            .collect();
        if root_moves.is_empty() {
            return SearchResult::default();
        }

        // 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()
                };
            }
        }
        if self.techniques.mvv_lva {
            ordering::order_moves(position, &mut root_moves);
        }
        self.tt.set_buckets(self.techniques.tt_buckets);
        // The previous search often left a best move for this position.
        self.tt.new_search();
        self.ordering.new_search();
        if self.techniques.tt
            && let Some(mv) = self.tt.probe(position.hash()).and_then(|e| e.best_move)
            && let Some(at) = root_moves.iter().position(|&m| m == mv)
        {
            root_moves[..=at].rotate_right(1);
        }

        // 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];
        }

        // A weaker level searches fewer nodes and several lines to choose from.
        let level = levels::settings_at(self.level());
        let mut level_limits = limits.clone();
        if let Some(nodes) = level.nodes {
            level_limits.nodes = Some(limits.nodes.map_or(nodes, |n| n.min(nodes)));
        }
        // Now and then, only as far ahead as a person would look (see `levels`), on one
        // thread. Never when analysing.
        let horizon = (!limits.infinite)
            .then(|| levels::horizon(&level, dice(position)))
            .flatten();
        if let Some(plies) = horizon {
            level_limits.depth = Some(plies);
        }
        let limits = &level_limits;
        let lines = self.multipv.max(level.candidates).max(1);
        // The levels were calibrated with the hand-crafted evaluation (chapter 19), so below
        // full strength the search keeps it: their ratings stay true. Calibrating them again
        // with a network is for later.
        let full_strength = self.level() >= f64::from(levels::FULL_STRENGTH);

        let budget = time::budget(limits, position.side_to_move(), &self.time);
        let unlimited = limits.depth.is_none()
            && limits.nodes.is_none()
            && limits.mate.is_none()
            && budget.hard.is_none()
            && !limits.infinite;
        let mut max_depth = limits
            .depth
            .unwrap_or(if unlimited { DEFAULT_DEPTH } else { MAX_PLY });
        if let Some(moves) = limits.mate {
            // A mate in N moves is 2N - 1 plies away.
            max_depth = max_depth.min(2 * moves);
        }
        let max_depth = max_depth.clamp(1, MAX_PLY);

        let deadline = budget.hard.map(|hard| start + hard);
        let root_fallback = root_moves.first().copied();
        // Lazy SMP (stage 17): helper threads search the same position, sharing only the
        // transposition table. They stop when the main thread is done.
        let helpers_stop = AtomicBool::new(false);
        let helper_nodes = AtomicU64::new(0);
        let Engine {
            params,
            techniques,
            search_params,
            tt,
            ordering,
            correction,
            threads,
            tablebase,
            tablebase_params,
            multipv,
            time,
            network,
            ..
        } = self;
        let tablebase = tablebase.as_deref();
        // The network, if the search is to evaluate with one.
        let network = network
            .as_deref()
            .filter(|_| techniques.nnue && full_strength);
        let self_multipv = (*multipv).max(1);
        let tablebase_params = *tablebase_params;
        let techniques = match horizon {
            Some(_) => Techniques::horizon(),
            None => *techniques,
        };
        let threads = if horizon.is_some() { 1 } else { *threads };
        let (params, search_params, tt) = (&*params, *search_params, &*tt);
        thread::scope(|scope| {
            let mut helper_threads = Vec::new();
            for helper in 1..threads {
                let root_moves = root_moves.clone();
                let (helpers_stop, helper_nodes) = (&helpers_stop, &helper_nodes);
                helper_threads.push(scope.spawn(move || {
                    let mut ordering = OrderingTables::default();
                    let mut correction = CorrectionHistory::default();
                    let mut searcher = Searcher::new(
                        params,
                        search_params,
                        tt,
                        &mut ordering,
                        techniques,
                        StopConditions {
                            stop: helpers_stop,
                            deadline,
                            max_nodes: None,
                        },
                        history,
                    );
                    searcher.count_nodes_in(helper_nodes);
                    searcher.use_correction(&mut correction);
                    if let Some(tb) = tablebase {
                        searcher.use_tablebase(tb, tablebase_params);
                    }
                    if let Some(net) = network {
                        searcher.use_network(net);
                    }
                    run_helper(&mut searcher, position, root_moves, max_depth, helper);
                    searcher.stats()
                }));
            }
            let mut searcher = Searcher::new(
                params,
                search_params,
                tt,
                ordering,
                techniques,
                StopConditions {
                    stop,
                    deadline,
                    max_nodes: limits.nodes,
                },
                history,
            );
            searcher.use_correction(correction);
            if let Some(tb) = tablebase {
                searcher.use_tablebase(tb, tablebase_params);
            }
            if let Some(net) = network {
                searcher.use_network(net);
            }
            if let Some(on_root) = on_root {
                let follower = RootFollower::new(on_root, start, &helper_nodes, self_multipv);
                searcher.follow_root(follower);
            }
            let result = main_search(
                &mut searcher,
                MainSearch {
                    position,
                    root_moves,
                    max_depth,
                    start,
                    budget,
                    time,
                    helper_nodes: &helper_nodes,
                    lines,
                    reported: self_multipv,
                },
                on_info,
            );
            helpers_stop.store(true, Ordering::Relaxed);
            let mut stats = searcher.stats();
            for helper in helper_threads {
                if let Ok(helper_stats) = helper.join() {
                    stats.add(&helper_stats);
                }
            }
            let Some(best) = result.first() else {
                return SearchResult {
                    best_move: root_fallback,
                    ponder_move: None,
                    stats,
                };
            };
            // At full strength, the best line; at a lower level, one of the candidates.
            let candidates: Vec<(Move, i32)> = result
                .iter()
                .filter_map(|line| line.best_move.map(|mv| (mv, line.score)))
                .collect();
            let chosen = levels::choose(&candidates, &level, dice(position)).or(best.best_move);
            let line = result
                .iter()
                .find(|line| line.best_move == chosen)
                .unwrap_or(best);
            let best_move = chosen.or(root_fallback);
            // The expected reply is the line's second move. A line cut short (by a
            // transposition table cutoff just below the root) may not have one; then the
            // table's best move for the position after ours is the next best guess.
            let ponder_move = line.pv.get(1).copied().or_else(|| {
                let mut after = position.clone();
                after.make_move(best_move?);
                tt.probe(after.hash())
                    .and_then(|entry| entry.best_move)
                    .filter(|mv| after.legal_moves().contains(mv))
            });
            SearchResult {
                best_move,
                ponder_move,
                stats,
            }
        })
    }

Limits says when to stop: a depth, a node count, a fixed time, the clock, or infinite.
The stop flag is an AtomicBool that another thread can set at any moment.
The info callback receives progress: depth, score, nodes and the best line. UCI prints it as info lines; the shell will show it as a live display.
history carries the hash keys of earlier positions for repetition detection.

For now the “search” picks a random legal move. That’s enough to test the whole path from a GUI and back; stage 5 replaces it with alpha-beta.

UCI

GUIs start the engine as a separate program and talk to it in lines of text on standard input and output. A session:

> uci
< id name cb2026 1.0.0
< id author the cb2026 authors
< option name UCI_Chess960 type check default false
< uciok
> isready
< readyok
> position startpos moves e2e4 e7e5
> go wtime 60000 btime 60000 winc 1000 binc 1000
< info depth 1 seldepth 1 score cp 0 nodes 29 time 0 pv g1f3
< bestmove g1f3

The GUI owns the game: before every search it sends the whole position, then go with the clocks. Two details matter for robustness:

The search runs on its own thread. The command loop keeps reading, so isready is answered at once and stop takes effect immediately, even mid-search.
go infinite waits for stop before printing bestmove, as the protocol requires, even if the engine has already decided.

Bad input is reported (info string ...) and never crashes the engine: an invalid FEN, an illegal move in position, an unknown command or option. The protocol tests in crates/protocol/src/uci.rs play scripted sessions covering all of this. That includes Chess960 castling notation (e1h1, “king takes rook”) and Windows line endings.

One binary, three modes. GUIs send uci as their first line, so cb2026 reads one line to decide whether to speak UCI, XBoard (stage 20) or open the shell.

Try it

In the shell:

> play black          # cb2026 plays Black
> e4                  # you move; it replies (randomly, for now)
> play both           # watch it play itself to the end of the game

In a GUI such as En Croissant, add target/release/cb2026 as a UCI engine and play it.

Or by hand:

$ cargo run --release
uci
position startpos moves e2e4
go

What it’s worth

A random mover is the zero point of the Elo scale. Every stage from here on is measured against the one before.

Building a Chess Engine in Rust