diff options
| -rw-r--r-- | CLAUDE.md | 25 | ||||
| -rw-r--r-- | Cargo.toml | 9 | ||||
| -rw-r--r-- | flake.nix | 2 | ||||
| -rw-r--r-- | plans.org | 34 | ||||
| -rw-r--r-- | src/bench.rs | 90 | ||||
| -rw-r--r-- | src/board.rs | 100 | ||||
| -rw-r--r-- | src/claude-player.rs | 17 | ||||
| -rw-r--r-- | src/game.rs | 20 | ||||
| -rw-r--r-- | src/main.rs | 12 | ||||
| -rw-r--r-- | src/player.rs | 398 |
10 files changed, 632 insertions, 75 deletions
@@ -17,19 +17,31 @@ The toolchain comes from a Nix flake (`flake.nix`, loaded via direnv `.envrc` ↠- Lint / format: `cargo clippy`, `cargo fmt` - Nix package build (what CI runs in `.github/workflows/build_nix.yml`): `nix build` +### Benchmarking and profiling the search + +- Bench: `cargo run --profile profiling -- bench [depth]` (default depth 6; 9 takes about 0.6 s) searches six fixed positions to a fixed depth without the TUI and prints the move, score and time for each. The positions come from `ClaudePlayer` playing itself to depth 4, so they are deterministic. An optimisation that only makes the search faster must leave every move and score unchanged. +- Counters: add `--features search-stats` to print nodes, nodes/s, cache hit/overwrite rates and the share of cutoffs on the first move. They are thread-local, bumped with the `count!` macro in `player.rs` (also used in `board.rs`), and compile to nothing without the feature. Run `cargo test` with and without the feature. +- The `profiling` Cargo profile is release plus debug info. The dev shell has `perf` and `samply`. As a non-root user, `perf record` needs `-m 16` (a small ring buffer) with `--call-graph dwarf`, otherwise mmap fails on the `perf_event_mlock_kb` limit: `perf record -e cycles:u -m 16 --call-graph dwarf target/profiling/tigers-and-sheep-rs bench 9`. +- Before comparing timings, check `/sys/devices/system/clocksource/clocksource0/current_clocksource`. On this machine the kernel has fallen back from `tsc` to `hpet`, which turns every `Instant::now()` (one per interior search node) into a syscall and nearly halves the speed. Results and history are in `plans.org`. + ## Architecture - `src/board.rs` — all game logic and its unit tests (`#[cfg(test)] mod tests` at the bottom). -- `src/player.rs` — the `Player` trait. Players are polled, not blocking: the coordinator calls `update(board, turn)` before each draw, `pick_move(board, turn) -> Option<Move>` once per loop (computer players search and return `Some`), and passes clicks/keys to `handle_input(Input, board, turn) -> Option<Move>`. `highlights()` gives points for the board to highlight, `reset()` is called on both players after a revert (drop any selection and last-move comments; it is *not* called after a normal move, so players clear their own selection when they return a move), `render(area, buf)` draws the current player's panel (default: its name), and `render_last_turn(area, buf)` draws end-of-turn comments on the move it just made (default: nothing). `impl Widget for &dyn Player` makes every player a ratatui widget. Also the private-ish `MinimaxPlayer` trait: implementors supply `evaluate` (positive favours tigers) and optionally `depth()`/`name()`, plus `set_last_search`/`last_search` to keep a `SearchReport` (move, depth reached, score) that the blanket impl's `render_last_turn` shows; a blanket impl makes every `MinimaxPlayer` a `Player`. -- `src/game.rs` — `GameHandler::play_game(sheep_player, tiger_player)` runs a ratatui TUI (mouse capture on) until the user quits, returning the winner if there was one. Layout: board | move history on top; below, the current player's panel (70%) | the previous player's last-turn panel (30%). Panes overlap by one cell (`Layout::spacing(-1)`) and are built with `panel()` (`MergeStrategy::Exact`) so shared borders join up. The bottom row is drawn first and keeps its titles on its bottom border, because its top border is the same line as the board's bottom border, which lists the keybinds (keep them in step with `handle_event`). History is `Vec<(Move, GameBoard)>` (board *after* each move); the side to move comes from its length's parity (sheep first). Clicking a history row calls `revert(i)`, which goes back to the board *before* move `i`. +- `src/player.rs` — the `Player` trait. Players are polled, not blocking: the coordinator calls `update(board, turn)` before each draw, `pick_move(board, turn) -> Option<Move>` once per loop (computer players search and return `Some`), and passes clicks/keys to `handle_input(Input, board, turn) -> Option<Move>`. `highlights()` gives points for the board to highlight, `reset()` is called on both players after a revert (drop any selection and last-move comments; it is *not* called after a normal move, so players clear their own selection when they return a move), `render(area, buf)` draws the current player's panel (default: its name), and `render_last_turn(area, buf)` draws end-of-turn comments on the move it just made (default: nothing). `impl Widget for &dyn Player` makes every player a ratatui widget. Also the private-ish `MinimaxPlayer` trait: implementors supply `evaluate` (positive favours tigers) and optionally `depth()` (at most `MAX_DEPTH` = 64)/`time_limit()`/`name()`, plus `set_last_search`/`last_search` to keep a `SearchReport` (move, depth reached, score) that the blanket impl's `render_last_turn` shows; a blanket impl makes every `MinimaxPlayer` a `Player`. + - Search: alpha-beta (`minimax` checks the cache, `minimax_uncached` searches) with iterative deepening in `pick_move` until half the time limit has passed. Moves are tried in this order: the cache's best move (the `hint`), then tiger jumps (`get_moves` lists them first), then killer moves, then the rest. This is done by rotating moves to the front, because a `sort_by_key` here cost more than it saved. + - `cache()` returns an optional `ScoreCache`, keyed by board, side to move and remaining depth, storing `CacheEntry` bounds. `TranspositionTable` is the fixed-size one (`new(bits)`: `1 << bits` slots of ~24 bytes, in two-slot buckets where one slot keeps the deepest entry; `clear()` bumps a generation number instead of wiping). The `HashMap` impl is kept as a simple reference for tests. + - `killers()` returns optional `Killers`: two quiet moves per remaining depth that last caused a cutoff. `pick_move` clears both the cache and the killers. + - Tests compare the search with plain minimax (`reference`) for every cache kind (`CacheKind::None`/`Map`/`TinyTable`, a table small enough to collide constantly) with and without killers. +- `src/game.rs` — `GameHandler::play_game(sheep_player, tiger_player)` runs a ratatui TUI (mouse capture on) until the user quits, returning the winner if there was one. Layout: board | move history on top; below, the current player's panel (70%) | the previous player's last-turn panel (30%). Panes overlap by one cell (`Layout::spacing(-1)`) and are built with `panel()` (`MergeStrategy::Exact`) so shared borders join up. The bottom row is drawn first and keeps its titles on its bottom border, because its top border is the same line as the board's bottom border, which lists the keybinds (keep them in step with `handle_event`). History is `Vec<(Move, GameBoard)>` (board *after* each move); the side to move comes from its length's parity (sheep first). Clicking a history row calls `revert(i)`, which goes back to the board *before* move `i`. The loop only waits for input (`event::read`) when `pick_move` returns `None`. After a computer's search, `pending_action` handles any input that came in meanwhile, so quit and revert still work in computer-vs-computer games. They take effect once the current search finishes. - `src/board-view.rs` (module `board_view`) — `BoardView` widget (board with rank/file labels and highlights) and `pos_at`, which maps a mouse cell to the nearest point. Both pick the scale from the area (`scale_to_fit`: the largest whole-number scale whose `size(scale)` fits), so the coordinator sizes `board_area` to exactly `size(scale)` and the two agree. Pieces grow with the scale (`reach`): `T` at 1, `[T]` at 2, a 3x3 box from 3, which `size`, `cell` and `pos_at` all allow for. The history pane is a fixed 20 columns; the board pane gets the rest. - `src/local-player.rs` (module `local_player`, pulled in via `#[path]` because of the hyphen) — `LocalPlayer`, a human using the mouse: click a point to place a sheep, or click a piece then one of its highlighted destinations. -- `src/claude-player.rs` — `ClaudePlayer`, the minimax computer player. -- `src/main.rs` — plays `LocalPlayer` (sheep) against `ClaudePlayer` (tigers) and prints the winner. +- `src/claude-player.rs` — `ClaudePlayer`, the minimax computer player: `time_limit` and `max_depth` are public fields, with a 2^20-slot `TranspositionTable` and killer moves. +- `src/bench.rs` — the `bench` mode (see above). +- `src/main.rs` — `bench [depth]` runs the benchmark; otherwise it plays a game in the TUI (the sheep player first, then the tigers) and prints the winner. Which players it uses changes: `LocalPlayer` or `ClaudePlayer` on either side. Notation (`pos_name`, `impl Display for Move` in board.rs): files `a`–`e` are x 0–4, ranks are `5 - y` (y = 0 is drawn at the top as rank 5). Moves are `sc3` (place), `sc3c2` (sheep move), `ta5b4` (tiger step), `ta5xc3` (tiger jump). -Win check: `check_win(turn)` is called with the side about to move, and true means the side that *just* moved has won. Tigers win once 5 sheep are dead (`sheep_count() + sheep_left() <= 15`); otherwise the side that just moved wins if the side to move has no legal moves. +Win check: `check_win(turn)` is called with the side about to move, and true means the side that *just* moved has won. Tigers win once 5 sheep are dead (`sheep_count() + sheep_left() <= 15`); otherwise the side that just moved wins if the side to move has no legal moves. That check uses `has_moves(turn)`, which tests the same bitmasks as `get_moves` (shared through `sheep_steps`/`tiger_targets`) without building a list. ### Board representation (`GameBoard`) @@ -38,7 +50,8 @@ The board is two `u32` bitmasks, `tiger_mask` and `sheep_mask`. This encoding is - Point `(x, y)` maps to index `x + y*5` (0..24), and its bit is `1 << idx`. So board bits occupy the **low 25 bits** (`BOARD_MASK`), with `(0,0)` at bit 0. - The **high 7 bits of `sheep_mask`** (from `SHEEP_COUNT_SHIFT = 25`) are not board points — they hold the count of sheep still in hand (starts at 20). `sheep_left()` reads it; `place_sheep` subtracts `ONE_SHEEP` (`1 << 25`) from `sheep_mask` directly. Killing a sheep does not change this count (it counts unplaced sheep, not living ones). - `Pos = (u8, u8)` is `(x, y)`; out-of-range coordinates panic in `bit_idx`. -- Default layout: tigers in the four corners, 20 sheep in hand. +- Default layout: tigers in the four corners, 20 sheep in hand. `GameBoard::EMPTY` has no pieces and none in hand. +- `key()` packs the whole board into one `u64` (used for the transposition table's hash). ### Rules as implemented @@ -9,3 +9,12 @@ path = "src/main.rs" [dependencies] ratatui = "0.30.2" + +[features] +# Count nodes, cache hits and cutoffs during the search, for `bench`. +search-stats = [] + +# A release build that keeps debug info, for profilers: `cargo build --profile profiling` +[profile.profiling] +inherits = "release" +debug = true @@ -30,6 +30,8 @@ pre-commit rustPackages.clippy rust-analyzer + samply + perf ]; RUST_SRC_PATH = rustPlatform.rustLibSrc; }; @@ -6,5 +6,37 @@ ** Move generation caching? ** DONE Iterative deepening - Use results of previous searches for move ordering -** Profile to see what needs optimization the most +** DONE Profile to see what needs optimization the most +- =cargo run --profile profiling -- bench 9= (add =--features search-stats= for counters) +- Profile: =perf record -e cycles:u -m 16 --call-graph dwarf target/profiling/tigers-and-sheep-rs bench 9= + (=-m 16= keeps the ring buffer under =perf_event_mlock_kb=, otherwise mmap fails) +- First profile, depth 9: 2056 ms, 2.05 M nodes, ~1.0 M nodes/s + | Where | Share | + |-------------------------------------------+--------------------------| + | Kernel: clock_gettime syscalls | 43% of wall time (sys) | + | SipHash for the cache HashMap | ~29% of user cycles | + | get_moves (2.0 calls/node, Vec each time) | ~22% of user cycles | + | minimax_uncached + inlined evaluate | ~29% of user cycles | + - The kernel time was not the HashMap's page faults, as first thought: the kernel had fallen back + from the TSC to the HPET clock source, so =Instant::now()= at every interior node was a real + syscall (=strace -c=: 99% of syscall time in clock_gettime). After a reboot it was back on TSC. + Check =/sys/devices/system/clocksource/clocksource0/current_clocksource= before comparing timings. +- Search: cache hit rate 29% (1.8 probes/node); 74% of cutoffs on the first move (63% in placement) +** DONE Speed-ups from the profile +All at depth 9 on the TSC clock source; scores and moves the same as the baseline at every step. +| Step | Time ms | Nodes | Nodes/s | 1st-move cutoffs | +|--------------------------------------------+---------+--------+---------+------------------| +| Baseline | 1205 | 2.05 M | 1.7 M | 72% | +| =has_moves= in =check_win= | 1045 | 2.05 M | 2.0 M | 72% | +| =TranspositionTable= (2^20 slots, 24 MB) | 650 | 2.07 M | 3.2 M | 72% | +| Jumps first, killer moves | 572 | 1.67 M | 2.9 M | 97% | +- Table: always-replace needed 2.82 M nodes at 2^20 slots (2.31 M even at 2^22), because the 1.5 M + leaf entries pushed out deeper ones. Two-slot buckets, one kept for the deepest entry, fixed it. +- Ordering: a =sort_by_key= cost ~26% of cycles and made it slower overall than no ordering; + =get_moves= now lists jumps first and the search rotates killers and the hint to the front instead. +- Killers on their own cut nodes 10% but made the opening search bigger (0.93 M -> 1.04 M nodes) +*** Next candidates +- Check the deadline every N nodes instead of at every node, so a slow clock source can't cost half the search +- =evaluate=: tiger moves and trapped tigers from bitmasks rather than =get_moves= + 25 =get()= calls +- Table lookups are now the top item (~28% of cycles), mostly cache misses into the 24 MB table * Draws diff --git a/src/bench.rs b/src/bench.rs new file mode 100644 index 0000000..ad6d63f --- /dev/null +++ b/src/bench.rs @@ -0,0 +1,90 @@ +use std::time::{Duration, Instant}; + +use crate::{board::{GameBoard, Turn}, claude_player::ClaudePlayer, player::{MinimaxPlayer, Player, SearchReport, SearchStats}}; + +/// Positions from each phase of the game, as (label, plies of random play from the start). +const POSITIONS: [(&str, usize); 6] = [ + ("opening", 0), + ("tiger reply", 1), + ("mid-placement", 20), + ("end of placement", 38), + ("early movement", 45), + ("movement", 60), +]; + +/// The position after `plies` moves of `ClaudePlayer` playing itself to depth 4, which is +/// deterministic and plays a lot more like a real game than random moves do. +fn find_position(plies: usize) -> (GameBoard, Turn) +{ + let mut player = ClaudePlayer::new(Duration::from_secs(1 << 20)); + player.max_depth = 4; + let mut board = GameBoard::default(); + let mut turn = Turn::Sheep; + for _ in 0..plies + { + assert!(!board.check_win(turn), "the self-play game ended before ply {plies}"); + board.make_move_unchecked(player.pick_move(board, turn).expect("a move")); + turn = turn.next_turn(); + } + (board, turn) +} + +/// Search each of `POSITIONS` to `depth` with a fresh `ClaudePlayer` and print what it found and how long it took. +/// The depth caps the search instead of the time limit, so runs do the same work and can be compared. +/// Build with `--features search-stats` to also print node counts (which slows the search a little). +pub fn run(depth: usize) +{ + println!("{:<17} {:<6} {:>5} {:>9} {:<8} {:>8}", "position", "turn", "depth", "time ms", "move", "score"); + let mut total_time = Duration::ZERO; + let mut total_stats = SearchStats::default(); + for (label, plies) in POSITIONS + { + let (board, turn) = find_position(plies); + let mut player = ClaudePlayer::new(Duration::from_secs(1 << 20)); + player.max_depth = depth; + SearchStats::take(); + let start = Instant::now(); + let m = player.pick_move(board, turn).expect("a move"); + let time = start.elapsed(); + let stats = SearchStats::take(); + total_time += time; + add(&mut total_stats, &stats); + + let SearchReport { mv, depth, score } = player.last_search().expect("a report"); + assert_eq!(mv, m); + println!("{label:<17} {:<6} {depth:>5} {:>9.1} {:<8} {score:>8.1}", + format!("{turn:?}"), time.as_secs_f64() * 1000.0, mv.to_string()); + print_stats(&stats, time); + } + println!("{:<17} {:<6} {:>5} {:>9.1}", "total", "", "", total_time.as_secs_f64() * 1000.0); + print_stats(&total_stats, total_time); +} + +fn add(total: &mut SearchStats, s: &SearchStats) +{ + total.nodes += s.nodes; + total.leaves += s.leaves; + total.terminal += s.terminal; + total.cache_probes += s.cache_probes; + total.cache_hits += s.cache_hits; + total.cache_returns += s.cache_returns; + total.cache_overwrites += s.cache_overwrites; + total.cutoffs += s.cutoffs; + total.first_move_cutoffs += s.first_move_cutoffs; + total.move_gens += s.move_gens; +} + +fn print_stats(s: &SearchStats, time: Duration) +{ + if !cfg!(feature = "search-stats") + { + return; + } + let pct = |a: u64, b: u64| if b == 0 { 0.0 } else { 100.0 * a as f64 / b as f64 }; + println!(" {} nodes ({:.2} M/s), {} leaves, {} terminal, {:.2} move gens/node", + s.nodes, s.nodes as f64 / time.as_secs_f64() / 1e6, s.leaves, s.terminal, + s.move_gens as f64 / s.nodes.max(1) as f64); + println!(" cache: {} probes, {:.1}% hit, {:.1}% of hits settle the score, {} overwrites; cutoffs: {}, {:.1}% on the first move", + s.cache_probes, pct(s.cache_hits, s.cache_probes), pct(s.cache_returns, s.cache_hits), s.cache_overwrites, + s.cutoffs, pct(s.first_move_cutoffs, s.cutoffs)); +} diff --git a/src/board.rs b/src/board.rs index 51a2593..1c21c3e 100644 --- a/src/board.rs +++ b/src/board.rs @@ -220,6 +220,9 @@ fn pos_of(idx: usize) -> Pos impl GameBoard { + /// No pieces on the board and none in hand. + pub const EMPTY: GameBoard = GameBoard { sheep_mask: 0, tiger_mask: 0 }; + fn bit_idx((x, y): Pos) -> usize { if x > 4 || y > 4 @@ -260,30 +263,78 @@ impl GameBoard } pub fn sheep_left(&self) -> u32 { self.sheep_mask >> SHEEP_COUNT_SHIFT } + /// The whole board, sheep in hand included, as one number: different boards give different keys. + pub fn key(&self) -> u64 { (self.sheep_mask as u64) << 32 | self.tiger_mask as u64 } pub fn sheep_count(&self) -> u32 { (self.sheep_mask & BOARD_MASK).count_ones() } - /// All legal moves for `turn`. Sheep place while any are in hand, then move. - pub fn get_moves(&self, turn: Turn) -> Vec<Move> + /// Empty board points. + fn empty(&self) -> u32 + { + !(self.tiger_mask | self.sheep_mask) & BOARD_MASK + } + + /// For each direction, the points a sheep can step to in that direction. + fn sheep_steps(&self) -> [u32; 8] + { + let sheep = self.sheep_mask & BOARD_MASK; + let empty = self.empty(); + let mut steps = [0; 8]; + for d in 0..8 + { + steps[d] = shift(sheep & STEP_SOURCES[d], DELTAS[d]) & empty; + } + steps + } + + /// For each direction, the points a tiger can step to and the points it can jump to. + fn tiger_targets(&self) -> ([u32; 8], [u32; 8]) { let tigers = self.tiger_mask; let sheep = self.sheep_mask & BOARD_MASK; - let empty = !(tigers | sheep) & BOARD_MASK; + let empty = self.empty(); + let mut steps = [0; 8]; + let mut jumps = [0; 8]; + for d in 0..8 + { + steps[d] = shift(tigers & STEP_SOURCES[d], DELTAS[d]) & empty; + let over = shift(tigers & JUMP_SOURCES[d], DELTAS[d]) & sheep; + jumps[d] = shift(over, DELTAS[d]) & empty; + } + (steps, jumps) + } + /// True if `turn` has a legal move: the same as `!get_moves(turn).is_empty()`, without building the list. + pub fn has_moves(&self, turn: Turn) -> bool + { + match turn + { + Turn::Sheep if self.sheep_left() > 0 => self.empty() != 0, + Turn::Sheep => self.sheep_steps().iter().any(|&m| m != 0), + Turn::Tiger => + { + let (steps, jumps) = self.tiger_targets(); + steps.iter().chain(jumps.iter()).fold(0, |acc, m| acc | m) != 0 + } + } + } + + /// All legal moves for `turn`. Sheep place while any are in hand, then move. + /// Tiger jumps come before steps, since the search tries kills first. + pub fn get_moves(&self, turn: Turn) -> Vec<Move> + { + crate::player::count!(move_gens); match turn { Turn::Sheep if self.sheep_left() > 0 => { + let empty = self.empty(); let mut moves = Vec::with_capacity(empty.count_ones() as usize); moves.extend(indices(empty).map(|idx| Move::PlaceSheep { pos: pos_of(idx) })); moves } Turn::Sheep => { - let mut steps = [0; 8]; - for d in 0..8 - { - steps[d] = shift(sheep & STEP_SOURCES[d], DELTAS[d]) & empty; - } + let steps = self.sheep_steps(); let mut moves = Vec::with_capacity(steps.iter().map(|m| m.count_ones() as usize).sum()); for d in 0..8 { @@ -297,26 +348,22 @@ impl GameBoard } Turn::Tiger => { - let mut steps = [0; 8]; - let mut jumps = [0; 8]; - for d in 0..8 - { - steps[d] = shift(tigers & STEP_SOURCES[d], DELTAS[d]) & empty; - let over = shift(tigers & JUMP_SOURCES[d], DELTAS[d]) & sheep; - jumps[d] = shift(over, DELTAS[d]) & empty; - } + let (steps, jumps) = self.tiger_targets(); let count = steps.iter().chain(jumps.iter()).map(|m| m.count_ones() as usize).sum(); let mut moves = Vec::with_capacity(count); for d in 0..8 { - for to in indices(steps[d]) + for to in indices(jumps[d]) { - let from = (to as isize - DELTAS[d]) as usize; + let from = (to as isize - 2 * DELTAS[d]) as usize; moves.push(Move::MoveTiger { from: pos_of(from), to: pos_of(to) }); } - for to in indices(jumps[d]) + } + for d in 0..8 + { + for to in indices(steps[d]) { - let from = (to as isize - 2 * DELTAS[d]) as usize; + let from = (to as isize - DELTAS[d]) as usize; moves.push(Move::MoveTiger { from: pos_of(from), to: pos_of(to) }); } } @@ -411,14 +458,7 @@ impl GameBoard /// The side that just moved has won. pub fn check_win(&self, turn: Turn) -> bool { - if self.sheep_count() + self.sheep_left() <= 15 - { - true - } - else - { - self.get_moves(turn).len() == 0 - } + self.sheep_count() + self.sheep_left() <= 15 || !self.has_moves(turn) } pub fn after_move_unchecked(&self, mv: Move) -> Self @@ -884,6 +924,10 @@ mod tests } assert_moves_match(&board, Turn::Tiger); assert_moves_match(&board, Turn::Sheep); + for turn in [Turn::Tiger, Turn::Sheep] + { + assert_eq!(board.has_moves(turn), !board.get_moves(turn).is_empty(), "{turn:?} on {board:?}"); + } } } diff --git a/src/claude-player.rs b/src/claude-player.rs index 92be85b..5cbd794 100644 --- a/src/claude-player.rs +++ b/src/claude-player.rs @@ -1,6 +1,6 @@ -use std::{collections::HashMap, time::Duration}; +use std::time::Duration; -use crate::{board::{is_jump, GameBoard, Move, PieceType, Turn}, player::{CacheEntry, MinimaxPlayer, SearchReport}}; +use crate::{board::{is_jump, GameBoard, Move, PieceType, Turn}, player::{Killers, MinimaxPlayer, SearchReport, TranspositionTable}}; /// Sheep that start the game: on the board plus in hand. const TOTAL_SHEEP: u32 = 20; @@ -9,7 +9,10 @@ const TOTAL_SHEEP: u32 = 20; pub struct ClaudePlayer { pub time_limit: Duration, - cache: HashMap<(GameBoard, Turn, usize), CacheEntry>, + /// The most plies to search, counting the move itself; normally `time_limit` stops the search first. + pub max_depth: usize, + cache: TranspositionTable, + killers: Killers, last_search: Option<SearchReport>, } @@ -17,7 +20,7 @@ impl Default for ClaudePlayer { fn default() -> Self { - Self { time_limit: Duration::from_secs(1), cache: HashMap::new(), last_search: None } + Self::new(Duration::from_secs(1)) } } @@ -25,7 +28,7 @@ impl ClaudePlayer { pub fn new(time_limit: Duration) -> Self { - Self { time_limit, cache: HashMap::new(), last_search: None } + Self { time_limit, max_depth: 64, cache: TranspositionTable::new(20), killers: Killers::default(), last_search: None } } } @@ -70,9 +73,13 @@ impl MinimaxPlayer for ClaudePlayer fn time_limit(&self) -> Duration { self.time_limit } + fn depth(&self) -> usize { self.max_depth } + fn cache(&mut self) -> Option<&mut dyn crate::player::ScoreCache> { Some(&mut self.cache) } + + fn killers(&mut self) -> Option<&mut Killers> { Some(&mut self.killers) } } #[cfg(test)] diff --git a/src/game.rs b/src/game.rs index fcfc243..11a77fd 100644 --- a/src/game.rs +++ b/src/game.rs @@ -1,4 +1,4 @@ -use std::io; +use std::{io, time::Duration}; use ratatui::{ crossterm::{event::{self, DisableMouseCapture, EnableMouseCapture, Event, KeyCode, KeyEventKind, KeyModifiers, MouseButton, MouseEventKind}, execute}, @@ -111,7 +111,9 @@ impl GameHandler let player = &mut *players[idx(turn)]; let action = match (!over).then(|| player.pick_move(board, turn)).flatten() { - Some(m) => Action::Play(m), + // Input that came in during the search goes first, so a quit or a revert isn't + // lost when both players are computers and nothing ever waits for input + Some(m) => self.pending_action(player, board, turn)?.unwrap_or(Action::Play(m)), None => self.handle_event(event::read()?, player, board, turn, over), }; @@ -129,6 +131,20 @@ impl GameHandler } } + /// Handle the events already waiting, without blocking, until one of them does something. + fn pending_action(&self, player: &mut dyn Player, board: GameBoard, turn: Turn) -> io::Result<Option<Action>> + { + while event::poll(Duration::ZERO)? + { + let action = self.handle_event(event::read()?, player, board, turn, false); + if !matches!(action, Action::None) + { + return Ok(Some(action)); + } + } + Ok(None) + } + fn handle_event(&self, ev: Event, player: &mut dyn Player, board: GameBoard, turn: Turn, over: bool) -> Action { match ev diff --git a/src/main.rs b/src/main.rs index 54fb28f..16467b0 100644 --- a/src/main.rs +++ b/src/main.rs @@ -11,10 +11,20 @@ mod board_view; mod local_player; #[path = "claude-player.rs"] mod claude_player; +mod bench; fn main() -> std::io::Result<()> { + // `bench [depth]` times the computer player's search without the TUI + let args: Vec<String> = std::env::args().collect(); + if args.get(1).is_some_and(|a| a == "bench") + { + let depth = args.get(2).map_or(6, |d| d.parse().expect("depth should be a number")); + bench::run(depth); + return Ok(()); + } let mut game = GameHandler::default(); - let winner = game.play_game(&mut ClaudePlayer::new(Duration::from_secs(2)), &mut LocalPlayer::default())?; + let winner = game.play_game(&mut ClaudePlayer::new(Duration::from_secs(2)), + &mut ClaudePlayer::new(Duration::from_secs(2)))?; if let Some(winner) = winner { println!("{winner:?} wins!"); diff --git a/src/player.rs b/src/player.rs index 3271593..7a19219 100644 --- a/src/player.rs +++ b/src/player.rs @@ -2,7 +2,7 @@ use std::{collections::HashMap, time::{Duration, Instant}}; use ratatui::{buffer::Buffer, crossterm::event::KeyEvent, layout::Rect, widgets::{Paragraph, Widget, Wrap}}; -use crate::board::{GameBoard, Move, Pos, Turn}; +use crate::board::{is_jump, GameBoard, Move, Pos, Turn}; /// Input the game coordinator passes on to the player whose turn it is. #[derive(Clone, Copy, Debug, PartialEq, Eq)] @@ -113,6 +113,203 @@ impl ScoreCache for HashMap<(GameBoard, Turn, usize), CacheEntry> } } +/// A fixed-size score cache. Each position hashes to a bucket of two slots: the first keeps +/// whichever entry was searched deepest, so the many shallow entries near the leaves can't push +/// it out, and the second takes everything else. +/// Slots keep their full key, so a collision loses an entry but never returns the wrong one. +/// It is allocated once, so unlike a `HashMap` it never grows or rehashes during a search. +pub struct TranspositionTable +{ + slots: Vec<Slot>, + /// Bits of the slot index, so there are `1 << bits` slots in `1 << (bits - 1)` buckets. + bits: u32, + /// Slots from an older generation count as empty, which makes `clear` cheap. + /// 0 is never current, so `EMPTY_SLOT`s start out empty. + generation: u8, +} + +#[derive(Clone, Copy)] +struct Slot +{ + board: GameBoard, + turn: Turn, + depth: u8, + generation: u8, + entry: CacheEntry, +} + +const EMPTY_SLOT: Slot = Slot +{ + board: GameBoard::EMPTY, + turn: Turn::Sheep, + depth: 0, + generation: 0, + entry: CacheEntry { lower: f32::NEG_INFINITY, upper: f32::INFINITY, best: None }, +}; + +impl Slot +{ + fn holds(&self, board: &GameBoard, turn: Turn, depth: usize, generation: u8) -> bool + { + self.generation == generation && self.board == *board && self.turn == turn && self.depth as usize == depth + } +} + +impl TranspositionTable +{ + /// A table of `1 << bits` slots (about 24 bytes each). + pub fn new(bits: u32) -> Self + { + assert!(bits >= 1, "the table needs at least one bucket of two slots"); + Self { slots: vec![EMPTY_SLOT; 1 << bits], bits, generation: 1 } + } + + /// The index of the first slot of the position's bucket. + fn bucket(&self, board: &GameBoard, turn: Turn, depth: usize) -> usize + { + let key = board.key() ^ (depth as u64) << 1 ^ matches!(turn, Turn::Sheep) as u64; + ((key.wrapping_mul(0x9E3779B97F4A7C15) >> (65 - self.bits)) as usize) << 1 + } +} + +impl ScoreCache for TranspositionTable +{ + fn lookup(&mut self, board: &GameBoard, turn: Turn, depth: usize) -> Option<CacheEntry> + { + let b = self.bucket(board, turn, depth); + self.slots[b..b + 2].iter().find(|s| s.holds(board, turn, depth, self.generation)).map(|s| s.entry) + } + + fn insert(&mut self, board: &GameBoard, turn: Turn, depth: usize, entry: CacheEntry) + { + let generation = self.generation; + let b = self.bucket(board, turn, depth); + let [deep, any] = &mut self.slots[b..b + 2] else { unreachable!() }; + let slot = if deep.holds(board, turn, depth, generation) || any.holds(board, turn, depth, generation) + { + // Update the position's own entry, wherever it is + if deep.holds(board, turn, depth, generation) { deep } else { any } + } + else if deep.generation != generation || depth >= deep.depth as usize + { + // The deep slot's entry moves down rather than being lost + *any = *deep; + deep + } + else + { + any + }; + #[cfg(feature = "search-stats")] + if slot.generation == generation && !slot.holds(board, turn, depth, generation) + { + count!(cache_overwrites); + } + let depth = u8::try_from(depth).expect("search depth fits in a u8"); + *slot = Slot { board: *board, turn, depth, generation, entry }; + } + + fn clear(&mut self) + { + self.generation = self.generation.wrapping_add(1); + // After 255 clears the oldest slots' generation would come round again, so empty them for real + if self.generation == 0 + { + self.slots.fill(EMPTY_SLOT); + self.generation = 1; + } + } +} + +/// The deepest search a `MinimaxPlayer` may do, in plies. +pub const MAX_DEPTH: usize = 64; + +/// Killer moves: for each remaining search depth, the last two quiet (non-jump) moves that cut a +/// search off there. Within one pass of iterative deepening a remaining depth is a ply from the +/// root, and a move that refuted one position at a ply often refutes its siblings too. +#[derive(Clone, Debug)] +pub struct Killers([[Option<Move>; 2]; MAX_DEPTH + 1]); + +impl Default for Killers +{ + fn default() -> Self { Self([[None; 2]; MAX_DEPTH + 1]) } +} + +impl Killers +{ + pub fn clear(&mut self) { *self = Self::default(); } + + fn get(&self, depth: usize) -> [Option<Move>; 2] + { + self.0.get(depth).copied().unwrap_or_default() + } + + fn add(&mut self, depth: usize, m: Move) + { + if let Some(k) = self.0.get_mut(depth) + { + if k[0] != Some(m) + { + *k = [Some(m), k[0]]; + } + } + } +} + +/// Counts of what the search did, for profiling. They are only counted with the `search-stats` +/// feature; without it `count!` compiles to nothing and `SearchStats::take` returns zeros. +#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)] +pub struct SearchStats +{ + /// Calls to `minimax_uncached`, i.e. positions searched rather than answered from the cache. + pub nodes: u64, + /// Positions scored with `evaluate`. + pub leaves: u64, + /// Positions where `check_win` ended the search. + pub terminal: u64, + pub cache_probes: u64, + pub cache_hits: u64, + /// Cache hits whose bounds settled the score without searching. + pub cache_returns: u64, + /// Cache entries lost because another position's entry took their slot. + pub cache_overwrites: u64, + /// Searches stopped early because alpha met beta. + pub cutoffs: u64, + /// Cutoffs on the first move tried; a high share means the moves are well ordered. + pub first_move_cutoffs: u64, + /// Calls to `GameBoard::get_moves`, from the search, `check_win` and `evaluate` alike. + pub move_gens: u64, +} + +#[cfg(feature = "search-stats")] +thread_local! +{ + pub(crate) static STATS: std::cell::RefCell<SearchStats> = std::cell::RefCell::new(SearchStats::default()); +} + +/// Add one to a `SearchStats` field, if the `search-stats` feature is on. +macro_rules! count +{ + ($field:ident) => + { + #[cfg(feature = "search-stats")] + crate::player::STATS.with_borrow_mut(|s| s.$field += 1); + }; +} +pub(crate) use count; + +impl SearchStats +{ + /// The counts so far on this thread, resetting them to zero. + pub fn take() -> Self + { + #[cfg(feature = "search-stats")] + return STATS.with_borrow_mut(std::mem::take); + #[cfg(not(feature = "search-stats"))] + Self::default() + } +} + pub trait MinimaxPlayer { const WIN: f32 = f32::INFINITY; @@ -121,16 +318,19 @@ pub trait MinimaxPlayer /// Returns None if `deadline` passed before the search finished. fn minimax(&mut self, board: GameBoard, turn: Turn, depth: usize, mut alpha: ScoreType, mut beta: ScoreType, deadline: Option<Instant>) -> Option<ScoreType> { - let known = self.cache().and_then(|c| c.lookup(&board, turn, depth)); + let known = self.cache().and_then(|c| { count!(cache_probes); c.lookup(&board, turn, depth) }); let mut hint = None; if let Some(k) = known { + count!(cache_hits); if k.lower >= beta { + count!(cache_returns); return Some(k.lower); } if k.upper <= alpha || k.lower == k.upper { + count!(cache_returns); return Some(k.upper); } alpha = alpha.max(k.lower); @@ -140,7 +340,7 @@ pub trait MinimaxPlayer // Otherwise try the best move from the previous, one-ply-shallower iteration first if hint.is_none() && depth > 0 { - hint = self.cache().and_then(|c| c.lookup(&board, turn, depth - 1)).and_then(|e| e.best); + hint = self.cache().and_then(|c| { count!(cache_probes); c.lookup(&board, turn, depth - 1) }).and_then(|e| e.best); } let (score, best) = self.minimax_uncached(board, turn, depth, alpha, beta, hint, deadline)?; if let Some(c) = self.cache() @@ -174,8 +374,10 @@ pub trait MinimaxPlayer fn minimax_uncached(&mut self, board: GameBoard, turn: Turn, depth: usize, mut alpha: ScoreType, mut beta: ScoreType, hint: Option<Move>, deadline: Option<Instant>) -> Option<(ScoreType, Option<Move>)> { + count!(nodes); if board.check_win(turn) { + count!(terminal); let score = match turn { Turn::Tiger => -Self::WIN, Turn::Sheep => Self::WIN, @@ -184,6 +386,7 @@ pub trait MinimaxPlayer } if depth == 0 { + count!(leaves); return Some((self.evaluate(&board), None)); } if deadline.is_some_and(|d| Instant::now() >= d) @@ -191,7 +394,21 @@ pub trait MinimaxPlayer return None; } + // Try the cache's best move first, then jumps (which `get_moves` lists first), then killer + // moves, then the rest in generated order. Rotating keeps that cheaper than sorting. let mut moves = board.get_moves(turn); + if let Some(killers) = self.killers().map(|k| k.get(depth)) + { + let quiet = moves.iter().take_while(|&&m| is_jump(m)).count(); + // The older killer goes first, so the newer one ends up in front of it + for k in killers.into_iter().rev().flatten() + { + if let Some(i) = moves[quiet..].iter().position(|&m| m == k) + { + moves[quiet..=quiet + i].rotate_right(1); + } + } + } if let Some(i) = hint.and_then(|h| moves.iter().position(|&m| m == h)) { moves[..=i].rotate_right(1); @@ -199,7 +416,7 @@ pub trait MinimaxPlayer let next = turn.next_turn(); // Keep the first move on ties, so a line of all-losing (-inf) moves still picks one let mut best: Option<(ScoreType, Move)> = None; - for m in moves + for (_i, m) in moves.into_iter().enumerate() { let score = self.minimax(board.after_move_unchecked(m), next, depth - 1, alpha, beta, deadline)?; let better = match best @@ -221,6 +438,19 @@ pub trait MinimaxPlayer } if alpha >= beta { + count!(cutoffs); + #[cfg(feature = "search-stats")] + if _i == 0 + { + count!(first_move_cutoffs); + } + if !is_jump(m) + { + if let Some(k) = self.killers() + { + k.add(depth, m); + } + } break; } } @@ -234,12 +464,18 @@ pub trait MinimaxPlayer { None } + + /// Override to return storage for killer moves, to try them earlier; the default is none. + fn killers(&mut self) -> Option<&mut Killers> + { + None + } /// More positive for tiger winning, less positive for sheep winning fn evaluate(&mut self, board: &GameBoard) -> ScoreType; /// The most plies `pick_move` searches, counting its own move. Normally the time limit stops it first. - fn depth(&self) -> usize { 64 } + fn depth(&self) -> usize { MAX_DEPTH } /// How long `pick_move` may spend searching. fn time_limit(&self) -> Duration { Duration::from_secs(1) } @@ -268,6 +504,10 @@ impl<P: MinimaxPlayer> Player for P { c.clear(); } + if let Some(k) = self.killers() + { + k.clear(); + } let mut best = None; let mut report = None; for depth in 1..=self.depth().max(1) @@ -335,15 +575,42 @@ mod tests { depth: usize, time_limit: Duration, - cache: Option<HashMap<(GameBoard, Turn, usize), CacheEntry>>, + cache: Option<Box<dyn ScoreCache>>, + killers: Option<Killers>, } + /// Which cache a `TestPlayer` searches with. + #[derive(Clone, Copy, Debug)] + enum CacheKind + { + None, + Map, + /// A table so small that slots are overwritten all the time. + TinyTable, + } + + const CACHED: [CacheKind; 2] = [CacheKind::Map, CacheKind::TinyTable]; + const ALL_CACHES: [CacheKind; 3] = [CacheKind::None, CacheKind::Map, CacheKind::TinyTable]; + impl TestPlayer { - fn new(depth: usize, cached: bool) -> Self + fn new(depth: usize, cache: CacheKind) -> Self { + let cache: Option<Box<dyn ScoreCache>> = match cache + { + CacheKind::None => None, + CacheKind::Map => Some(Box::new(HashMap::<(GameBoard, Turn, usize), CacheEntry>::new())), + CacheKind::TinyTable => Some(Box::new(TranspositionTable::new(3))), + }; // Long enough that only the depth cap stops a search, so results are deterministic - Self { depth, time_limit: Duration::from_secs(3600), cache: cached.then(HashMap::new) } + Self { depth, time_limit: Duration::from_secs(3600), cache, killers: None } + } + + /// Also order moves with killer moves if `on`. + fn with_killers(mut self, on: bool) -> Self + { + self.killers = on.then(Killers::default); + self } } @@ -358,7 +625,16 @@ mod tests fn cache(&mut self) -> Option<&mut dyn ScoreCache> { - self.cache.as_mut().map(|c| c as &mut dyn ScoreCache) + match &mut self.cache + { + Some(c) => Some(c.as_mut()), + None => None, + } + } + + fn killers(&mut self) -> Option<&mut Killers> + { + self.killers.as_mut() } fn depth(&self) -> usize { self.depth } @@ -420,7 +696,7 @@ mod tests { for depth in 1..=3 { - let mut player = TestPlayer::new(depth, false); + let mut player = TestPlayer::new(depth, CacheKind::None); let expected = reference(&mut player, board, turn, depth); let score = player.minimax(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, None).unwrap(); assert_eq!(score, expected, "depth {depth}, {turn:?} to move"); @@ -435,10 +711,16 @@ mod tests { for depth in 1..=3 { - let mut player = TestPlayer::new(depth, true); - let expected = reference(&mut player, board, turn, depth); - let score = player.minimax(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, None).unwrap(); - assert_eq!(score, expected, "depth {depth}, {turn:?} to move"); + for kind in CACHED + { + for killers in [false, true] + { + let mut player = TestPlayer::new(depth, kind).with_killers(killers); + let expected = reference(&mut player, board, turn, depth); + let score = player.minimax(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, None).unwrap(); + assert_eq!(score, expected, "depth {depth}, {turn:?} to move, {kind:?}, killers {killers}"); + } + } } } } @@ -448,13 +730,16 @@ mod tests { for (board, turn) in test_positions() { - let mut player = TestPlayer::new(3, true); + let mut player = TestPlayer::new(3, CacheKind::None); let expected = reference(&mut player, board, turn, 3); for hint in board.get_moves(turn) { - let mut player = TestPlayer::new(3, true); - let (score, _) = player.minimax_uncached(board, turn, 3, f32::NEG_INFINITY, f32::INFINITY, Some(hint), None).unwrap(); - assert_eq!(score, expected, "{turn:?} to move, hint {hint:?}"); + for kind in CACHED + { + let mut player = TestPlayer::new(3, kind).with_killers(true); + let (score, _) = player.minimax_uncached(board, turn, 3, f32::NEG_INFINITY, f32::INFINITY, Some(hint), None).unwrap(); + assert_eq!(score, expected, "{turn:?} to move, hint {hint:?}, {kind:?}"); + } } } } @@ -462,16 +747,20 @@ mod tests #[test] fn aborted_search_is_not_cached() { - let mut player = TestPlayer::new(3, true); - let past = Instant::now(); - assert_eq!(player.minimax(GameBoard::default(), Turn::Sheep, 3, f32::NEG_INFINITY, f32::INFINITY, Some(past)), None); - assert!(player.cache.unwrap().is_empty()); + for kind in CACHED + { + let mut player = TestPlayer::new(3, kind); + let past = Instant::now(); + assert_eq!(player.minimax(GameBoard::default(), Turn::Sheep, 3, f32::NEG_INFINITY, f32::INFINITY, Some(past)), None); + // The root gives up before searching any move, so its entry is the only one there could be + assert_eq!(player.cache.unwrap().lookup(&GameBoard::default(), Turn::Sheep, 3), None, "{kind:?}"); + } } #[test] fn pick_move_respects_time_limit() { - let mut player = TestPlayer::new(64, true); + let mut player = TestPlayer::new(64, CacheKind::TinyTable); player.time_limit = Duration::from_millis(50); let board = GameBoard::default(); let start = Instant::now(); @@ -485,13 +774,16 @@ mod tests { for (board, turn) in test_positions() { - for cached in [false, true] + for kind in ALL_CACHES { - let mut player = TestPlayer::new(4, cached); - let best = reference(&mut player, board, turn, 4); - let m = player.pick_move(board, turn).unwrap(); - let score = reference(&mut player, board.after_move_unchecked(m), turn.next_turn(), 3); - assert_eq!(score, best, "{turn:?} picked {m:?} (cached: {cached})"); + for killers in [false, true] + { + let mut player = TestPlayer::new(4, kind).with_killers(killers); + let best = reference(&mut player, board, turn, 4); + let m = player.pick_move(board, turn).unwrap(); + let score = reference(&mut player, board.after_move_unchecked(m), turn.next_turn(), 3); + assert_eq!(score, best, "{turn:?} picked {m:?} ({kind:?}, killers {killers})"); + } } } } @@ -520,10 +812,52 @@ mod tests } assert_eq!(board.sheep_count() + board.sheep_left(), 16); - for cached in [false, true] + for kind in ALL_CACHES { - let m = TestPlayer::new(3, cached).pick_move(board, Turn::Tiger).unwrap(); - assert!(board.after_move_unchecked(m).check_win(Turn::Sheep), "picked {m:?} (cached: {cached})"); + let m = TestPlayer::new(3, kind).pick_move(board, Turn::Tiger).unwrap(); + assert!(board.after_move_unchecked(m).check_win(Turn::Sheep), "picked {m:?} ({kind:?})"); } } + + #[test] + fn table_keeps_entries_apart_and_forgets_them_on_clear() + { + let entry = CacheEntry { lower: 1.0, upper: 2.0, best: None }; + let board = GameBoard::default(); + let mut table = TranspositionTable::new(3); + table.insert(&board, Turn::Sheep, 3, entry); + assert_eq!(table.lookup(&board, Turn::Sheep, 3), Some(entry)); + assert_eq!(table.lookup(&board, Turn::Tiger, 3), None); + assert_eq!(table.lookup(&board, Turn::Sheep, 2), None); + table.clear(); + assert_eq!(table.lookup(&board, Turn::Sheep, 3), None); + // Enough clears to wrap the generation round to the one the entry was stored in + table.insert(&board, Turn::Sheep, 3, entry); + for _ in 0..256 + { + table.clear(); + } + assert_eq!(table.lookup(&board, Turn::Sheep, 3), None); + } + + #[test] + fn killers_keep_the_last_two_different_moves() + { + let a = Move::PlaceSheep { pos: (0, 1) }; + let b = Move::PlaceSheep { pos: (0, 2) }; + let c = Move::PlaceSheep { pos: (0, 3) }; + let mut killers = Killers::default(); + killers.add(2, a); + killers.add(2, a); + assert_eq!(killers.get(2), [Some(a), None]); + killers.add(2, b); + killers.add(2, c); + assert_eq!(killers.get(2), [Some(c), Some(b)]); + assert_eq!(killers.get(1), [None, None]); + // Depths past the table are ignored rather than panicking + killers.add(MAX_DEPTH + 1, a); + assert_eq!(killers.get(MAX_DEPTH + 1), [None, None]); + killers.clear(); + assert_eq!(killers.get(2), [None, None]); + } } |