From 8b6323efba32da9e3651ce882c02a6e7a6671f23 Mon Sep 17 00:00:00 2001 From: Dylan Date: Fri, 23 Oct 2026 19:40:00 +1300 Subject: feat: Optimisation Added benchmarking capabilities --- src/player.rs | 398 +++++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 366 insertions(+), 32 deletions(-) (limited to 'src/player.rs') 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, + /// 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 + { + 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; 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; 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 = 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) -> Option { - 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, deadline: Option) -> Option<(ScoreType, Option)> { + 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 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>, + cache: Option>, + killers: Option, + } + + /// 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> = 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]); + } } -- cgit v1.3.1