feat: Optimisation

Added benchmarking capabilities

6 files changed, 569 insertions, 68 deletions

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]);
+	}
 }