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/bench.rs | 90 ++++++++++++ src/board.rs | 100 +++++++++---- src/claude-player.rs | 17 ++- src/game.rs | 20 ++- src/main.rs | 12 +- src/player.rs | 398 ++++++++++++++++++++++++++++++++++++++++++++++----- 6 files changed, 569 insertions(+), 68 deletions(-) create mode 100644 src/bench.rs (limited to 'src') 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 + /// 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 + { + 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, } @@ -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> + { + 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 = 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, + /// 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