path: root/src/player.rs

use std::{collections::HashMap, time::{Duration, Instant}};

use ratatui::{buffer::Buffer, crossterm::event::KeyEvent, layout::Rect, widgets::{Paragraph, Widget, Wrap}};

use crate::board::{inverse_symmetry, is_jump, repetitions, transform_move, GameBoard, Move, Pos, Turn};

/// Input the game coordinator passes on to the player whose turn it is.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Input
{
	/// A click on a board point.
	Click(Pos),
	Key(KeyEvent),
}

/// Points for the coordinator to highlight on the board.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Highlights
{
	pub selected: Option<Pos>,
	pub targets: Vec<Pos>,
}

/// A side in the game. The coordinator calls `pick_move` once per loop while it's this player's
/// turn, and passes on input with `handle_input`; whichever returns a move first plays it.
pub trait Player
{
	fn name(&self) -> String;

	/// Called before each draw while it's this player's turn, with the position to play.
	fn update(&mut self, _board: GameBoard, _turn: Turn) {}

	/// Computer players search here and return Some. Interactive players return None and
	/// wait for `handle_input`. `previous` is the game's boards before this one, oldest first,
	/// for spotting repetitions.
	fn pick_move(&mut self, _board: GameBoard, _turn: Turn, _previous: &[GameBoard]) -> Option<Move> { None }

	/// A click on a board point, or a key press, while it's this player's turn.
	fn handle_input(&mut self, _input: Input, _board: GameBoard, _turn: Turn) -> Option<Move> { None }

	/// Points for the coordinator to highlight on the board.
	fn highlights(&self) -> Highlights { Highlights::default() }

	/// The game was reverted: drop any half-made selection, and anything said about the last move.
	fn reset(&mut self) {}

	/// Draw into the player-output panel while it's this player's turn. By default this shows the player's name.
	fn render(&self, area: Rect, buf: &mut Buffer)
	{
		Paragraph::new(self.name()).render(area, buf);
	}

	/// Draw some end-of-turn comments on the move this player just made, shown beside the other
	/// player's panel during their turn. By default this shows nothing.
	fn render_last_turn(&self, _area: Rect, _buf: &mut Buffer) {}
}

/// Every player is a ratatui widget through `Player::render`.
/// (A blanket `impl<P: Player> Widget for &P` would break the orphan rule.)
impl Widget for &dyn Player
{
	fn render(self, area: Rect, buf: &mut Buffer)
	{
		Player::render(self, area, buf);
	}
}

pub type ScoreType = f32;

/// What a `MinimaxPlayer`'s last `pick_move` found.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct SearchReport
{
	pub mv: Move,
	/// The deepest search that finished, in plies counting the move itself.
	pub depth: usize,
	/// The score of `mv` at `depth`; positive favours tigers, and ±`WIN` is a forced win.
	pub score: ScoreType,
}

/// What a search has proved about a board's true score: it lies in `lower..=upper`.
/// An alpha-beta cutoff only proves one side, so the other is left infinite.
/// `best` is the move that gave the score, tried first when the position is searched again deeper.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct CacheEntry
{
	pub lower: ScoreType,
	pub upper: ScoreType,
	pub best: Option<Move>,
}

/// Score cache for a `MinimaxPlayer`. No defaults, so an implementor must supply all of it.
/// `minimax` looks boards up by `GameBoard::canonical`, so symmetric boards share an entry. Entries are keyed by the side to move and the remaining search depth as well as the board,
/// since the same board can be reached with either side to move, or at different depths.
pub trait ScoreCache
{
	fn lookup(&mut self, board: &GameBoard, turn: Turn, depth: usize) -> Option<CacheEntry>;
	fn insert(&mut self, board: &GameBoard, turn: Turn, depth: usize, entry: CacheEntry);
	fn clear(&mut self);
}

impl ScoreCache for HashMap<(GameBoard, Turn, usize), CacheEntry>
{
    fn lookup(&mut self, board: &GameBoard, turn: Turn, depth: usize) -> Option<CacheEntry> {
        self.get(&(*board, turn, depth)).copied()
    }

    fn insert(&mut self, board: &GameBoard, turn: Turn, depth: usize, entry: CacheEntry) {
        self.insert((*board, turn, depth), entry);
    }

    fn clear(&mut self) {
        self.clear();
    }
}

/// 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,
	/// Positions scored as a draw because they repeat an earlier one.
	pub repetitions: 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;
	/// The score of a position that repeats one on `path`.
	const DRAW: f32 = 0.0;

	/// Scores outside `alpha..beta` are only bounds: at most `alpha`, or at least `beta`.
	/// `path` is the boards before this one, in the game and then in the search, oldest first.
	/// Returns None if `deadline` passed before the search finished.
	#[allow(clippy::too_many_arguments)]
	fn minimax(&mut self, board: GameBoard, turn: Turn, depth: usize,
			   mut alpha: ScoreType, mut beta: ScoreType, deadline: Option<Instant>, path: &mut Vec<GameBoard>) -> Option<ScoreType> {
		// A side that can repeat a position once can repeat it until the game is drawn, so the
		// first repetition already scores as a draw. The cache doesn't know the path, so an entry
		// that came from a repetition can be slightly wrong for the same board reached another way.
		if repetitions(path, &board) > 0
		{
			count!(repetitions);
			return Some(Self::DRAW);
		}
		// Symmetric boards are equally good, so they share an entry, under the canonical board.
		// Entries' best moves are stored as played on that board, and turned back for this one.
		let (canon, sym) = if self.cache().is_some() { board.canonical() } else { (board, 0) };
		let back = |m: Move| transform_move(m, inverse_symmetry(sym));
		let known = self.cache().and_then(|c| { count!(cache_probes); c.lookup(&canon, 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);
			beta = beta.min(k.upper);
			hint = k.best.map(back);
		}
		// 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| { count!(cache_probes); c.lookup(&canon, turn, depth - 1) }).and_then(|e| e.best).map(back);
		}
		let (score, best) = self.minimax_uncached(board, turn, depth, alpha, beta, hint, deadline, path)?;
		if let Some(c) = self.cache()
		{
			let best = best.map(|m| transform_move(m, sym));
			// On a fail-low every move was only bounded, so none is known to be best
			let mut entry = if score <= alpha
			{
				CacheEntry { lower: f32::NEG_INFINITY, upper: score, best: None }
			}
			else if score >= beta
			{
				CacheEntry { lower: score, upper: f32::INFINITY, best }
			}
			else
			{
				CacheEntry { lower: score, upper: score, best }
			};
			if let Some(k) = known
			{
				entry.lower = entry.lower.max(k.lower);
				entry.upper = entry.upper.min(k.upper);
				entry.best = entry.best.or(k.best);
			}
			c.insert(&canon, turn, depth, entry);
		}
		Some(score)
	}

	/// The score and the move that gave it (None at a leaf), trying `hint` first if it is legal.
	/// Returns None if `deadline` passed before the search finished.
	#[allow(clippy::too_many_arguments)]
	fn minimax_uncached(&mut self, board: GameBoard, turn: Turn, depth: usize,
						mut alpha: ScoreType, mut beta: ScoreType,
						hint: Option<Move>, deadline: Option<Instant>, path: &mut Vec<GameBoard>) -> 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,
			};
			return Some((score, None));
		}
		if depth == 0
		{
			count!(leaves);
			return Some((self.evaluate(&board, turn), None));
		}
		if deadline.is_some_and(|d| Instant::now() >= d)
		{
			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);
		}
		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 (_i, m) in moves.into_iter().enumerate()
		{
			path.push(board);
			let score = self.minimax(board.after_move_unchecked(m), next, depth - 1, alpha, beta, deadline, path);
			path.pop();
			let score = score?;
			let better = match best
			{
				None => true,
				Some((best_score, _)) => match turn
				{
					Turn::Tiger => score > best_score,  // Maximising player
					Turn::Sheep => score < best_score,  // Minimising player
				},
			};
			if better
			{
				best = Some((score, m));
				match turn
				{
					Turn::Tiger => alpha = alpha.max(score),
					Turn::Sheep => beta = beta.min(score),
				}
				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;
				}
			}
		}
		let (score, m) = best.expect("check_win is false, so there is a legal move");
		Some((score, Some(m)))
	}

	/// Override to return a cache to enable caching; the default is no cache.
	fn cache(&mut self) -> Option<&mut dyn ScoreCache>
	{
		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, with `turn` to move next
	fn evaluate(&mut self, board: &GameBoard, turn: Turn) -> ScoreType;

	/// The most plies `pick_move` searches, counting its own move. Normally the time limit stops it first.
	fn depth(&self) -> usize { MAX_DEPTH }

	/// How long `pick_move` may spend searching.
	fn time_limit(&self) -> Duration { Duration::from_secs(1) }

	fn name(&self) -> String { "Computer".to_string() }

	/// Override with `last_search` to keep each search's report for the last-turn panel.
	/// By default it is dropped.
	fn set_last_search(&mut self, _report: Option<SearchReport>) {}

	fn last_search(&self) -> Option<SearchReport> { None }
}

impl<P: MinimaxPlayer> Player for P
{
	fn name(&self) -> String { MinimaxPlayer::name(self) }

	/// Iterative deepening: searches depth 1, 2, … until time runs out, each depth trying the
	/// previous one's best moves first, and plays the best move from the deepest finished search.
	fn pick_move(&mut self, board: GameBoard, turn: Turn, previous: &[GameBoard]) -> Option<Move> {
		let start = Instant::now();
		let time_limit = self.time_limit();
		let deadline = start + time_limit;
		// Entries would stay valid across moves (the key includes depth), but clear to bound memory
		if let Some(c) = self.cache()
		{
			c.clear();
		}
		if let Some(k) = self.killers()
		{
			k.clear();
		}
		let mut path = previous.to_vec();
		let mut best = None;
		let mut report = None;
		for depth in 1..=self.depth().max(1)
		{
			// Depth 1 ignores the deadline, so there is always a move to play
			let dl = (depth > 1).then_some(deadline);
			// Out of time: drop the partial search and keep the last finished one's move
			let Some((score, m)) = self.minimax_uncached(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, best, dl, &mut path)
			else
			{
				break;
			};
			best = m;
			report = m.map(|mv| SearchReport { mv, depth, score });
			// A forced win or loss won't change with more depth,
			// and past half the budget the next depth probably won't finish
			if score.abs() >= Self::WIN || start.elapsed() > time_limit / 2
			{
				break;
			}
		}
		self.set_last_search(report);
		Some(best.expect("pick_move called with no legal moves"))
    }

	fn reset(&mut self)
	{
		self.set_last_search(None);
	}

	fn render(&self, area: Rect, buf: &mut Buffer)
	{
		Paragraph::new(format!("{}\n\nThinking…", MinimaxPlayer::name(self))).render(area, buf);
	}

	fn render_last_turn(&self, area: Rect, buf: &mut Buffer)
	{
		let Some(r) = self.last_search() else { return };
		let score = if r.score >= Self::WIN
		{
			"forced win for tigers".to_string()
		}
		else if r.score <= -Self::WIN
		{
			"forced win for sheep".to_string()
		}
		else
		{
			format!("{} (+ favours tigers)", significant(r.score, 5))
		};
		Paragraph::new(format!("Played {}\nSearched to depth {}\nScore: {score}", r.mv, r.depth))
			.wrap(Wrap { trim: true }).render(area, buf);
	}
    
}

/// `x` to `digits` significant figures, with its sign: 1234.5678 to 5 is "+1234.6", 0.012345678
/// is "+0.012346", and 1234567 is "+1234600".
fn significant(x: f32, digits: usize) -> String
{
	if x == 0.0
	{
		return format!("{:.*}", digits.saturating_sub(1), 0.0);
	}
	// The power of ten of the first significant digit
	let magnitude = (x.abs() as f64).log10().floor() as i32;
	let decimals = digits as i32 - 1 - magnitude;
	if decimals >= 0
	{
		// Rounding can carry into a new digit (9.99999 to 10.000), which needs one decimal fewer
		let rounded = format!("{:+.*}", decimals as usize, x);
		let carried = rounded.trim_start_matches(['+', '-']).trim_start_matches(['0', '.']).chars().filter(char::is_ascii_digit).count() > digits;
		if carried && decimals > 0 { format!("{:+.*}", decimals as usize - 1, x) } else { rounded }
	}
	else
	{
		let unit = 10f64.powi(-decimals);
		format!("{:+.0}", (x as f64 / unit).round() * unit)
	}
}

#[cfg(test)]
mod tests
{
	use super::*;
	use crate::board::PieceType;

	#[test]
	fn significant_keeps_five_figures()
	{
		assert_eq!(significant(1234.5678, 5), "+1234.6");
		assert_eq!(significant(-212.0, 5), "-212.00");
		assert_eq!(significant(0.012345678, 5), "+0.012346");
		assert_eq!(significant(-0.5, 5), "-0.50000");
		assert_eq!(significant(1234567.0, 5), "+1234600");
		assert_eq!(significant(9.999999, 5), "+10.000");
		assert_eq!(significant(0.0, 5), "0.0000");
	}

	/// A minimax player with a cheap evaluation that still varies a lot between positions.
	struct TestPlayer
	{
		depth: usize,
		time_limit: Duration,
		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, 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, 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
		}
	}

	impl MinimaxPlayer for TestPlayer
	{
		fn evaluate(&mut self, board: &GameBoard, _turn: Turn) -> ScoreType
		{
			let dead = 20 - board.sheep_count() - board.sheep_left();
			100.0 * dead as f32 + board.get_moves(Turn::Tiger).len() as f32
				- board.get_moves(Turn::Sheep).len() as f32 / 2.0
		}

		fn cache(&mut self) -> Option<&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 }

		fn time_limit(&self) -> Duration { self.time_limit }
	}

	/// Plain minimax with no pruning or cache, to check the real search against.
	fn reference(player: &mut TestPlayer, board: GameBoard, turn: Turn, depth: usize) -> ScoreType
	{
		reference_from(player, board, turn, depth, &mut Vec::new())
	}

	/// `reference` with `path` the boards before this one, like `minimax`'s.
	fn reference_from(player: &mut TestPlayer, board: GameBoard, turn: Turn, depth: usize, path: &mut Vec<GameBoard>) -> ScoreType
	{
		if repetitions(path, &board) > 0
		{
			return TestPlayer::DRAW;
		}
		if board.check_win(turn)
		{
			return match turn { Turn::Tiger => -TestPlayer::WIN, Turn::Sheep => TestPlayer::WIN };
		}
		if depth == 0
		{
			return player.evaluate(&board, turn);
		}
		path.push(board);
		let scores: Vec<ScoreType> = board.get_moves(turn).into_iter()
			.map(|m| reference_from(player, board.after_move_unchecked(m), turn.next_turn(), depth - 1, path))
			.collect();
		path.pop();
		match turn
		{
			Turn::Tiger => scores.into_iter().fold(f32::NEG_INFINITY, f32::max),
			Turn::Sheep => scores.into_iter().fold(f32::INFINITY, f32::min),
		}
	}

	/// Positions reached by playing `plies` pseudo-random moves from the start, or None if the game ended.
	fn position(plies: usize, seed: u64) -> Option<(GameBoard, Turn)>
	{
		let mut board = GameBoard::default();
		let mut turn = Turn::Sheep;
		let mut rng = seed;
		for _ in 0..plies
		{
			if board.check_win(turn)
			{
				return None;
			}
			let moves = board.get_moves(turn);
			rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
			board.make_move_unchecked(moves[(rng >> 33) as usize % moves.len()]);
			turn = turn.next_turn();
		}
		(!board.check_win(turn)).then_some((board, turn))
	}

	fn test_positions() -> Vec<(GameBoard, Turn)>
	{
		[0, 1, 5, 12, 25, 41, 50, 60].iter()
			.flat_map(|&plies| (1..4).filter_map(move |seed| position(plies, seed)))
			.collect()
	}

	#[test]
	fn alpha_beta_matches_plain_minimax()
	{
		for (board, turn) in test_positions()
		{
			for depth in 1..=3
			{
				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, &mut Vec::new()).unwrap();
				assert_eq!(score, expected, "depth {depth}, {turn:?} to move");
			}
		}
	}

	#[test]
	fn cached_alpha_beta_matches_plain_minimax()
	{
		for (board, turn) in test_positions()
		{
			for depth in 1..=3
			{
				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, &mut Vec::new()).unwrap();
						assert_eq!(score, expected, "depth {depth}, {turn:?} to move, {kind:?}, killers {killers}");
					}
				}
			}
		}
	}

	#[test]
	fn any_hint_gives_the_same_score()
	{
		for (board, turn) in test_positions()
		{
			let mut player = TestPlayer::new(3, CacheKind::None);
			let expected = reference(&mut player, board, turn, 3);
			for hint in board.get_moves(turn)
			{
				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, &mut Vec::new()).unwrap();
					assert_eq!(score, expected, "{turn:?} to move, hint {hint:?}, {kind:?}");
				}
			}
		}
	}

	#[test]
	fn aborted_search_is_not_cached()
	{
		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), &mut Vec::new()), 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, CacheKind::TinyTable);
		player.time_limit = Duration::from_millis(50);
		let board = GameBoard::default();
		let start = Instant::now();
		let m = player.pick_move(board, Turn::Sheep, &[]).unwrap();
		assert!(start.elapsed() < Duration::from_millis(500), "took {:?}", start.elapsed());
		assert_eq!(board.check_move(m), Ok(()));
	}

	#[test]
	fn pick_move_picks_a_best_move()
	{
		for (board, turn) in test_positions()
		{
			for kind in ALL_CACHES
			{
				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})");
				}
			}
		}
	}

	/// A movement-phase position with `turn` to move and at least one sheep dead, so the
	/// evaluation is well above the draw score, and at least two moves.
	fn sheep_down_position(turn: Turn) -> (GameBoard, Turn)
	{
		(41..80).flat_map(|plies| (1..20).filter_map(move |seed| position(plies, seed)))
			.find(|&(board, t)| t == turn && board.sheep_left() == 0 && board.sheep_count() < 20
				&& board.get_moves(t).len() >= 2)
			.expect("a position with a sheep down")
	}

	/// A history in which the board after `m` came up before, with the same side to move:
	/// that board, then `board`, then that board again.
	fn history_repeating(board: GameBoard, m: Move) -> Vec<GameBoard>
	{
		let after = board.after_move_unchecked(m);
		vec![after, board, after]
	}

	#[test]
	fn search_scores_a_repeated_position_as_a_draw()
	{
		let (board, turn) = sheep_down_position(Turn::Tiger);
		let m = board.get_moves(turn)[0];
		let mut path = history_repeating(board, m);
		path.push(board);
		let mut player = TestPlayer::new(3, CacheKind::None);
		assert_eq!(player.minimax(board.after_move_unchecked(m), turn.next_turn(), 3,
			f32::NEG_INFINITY, f32::INFINITY, None, &mut path), Some(TestPlayer::DRAW));
		assert_eq!(path.len(), 4, "the search leaves the path as it found it");
	}

	#[test]
	fn tiger_ahead_avoids_a_repetition()
	{
		let (board, turn) = sheep_down_position(Turn::Tiger);
		for kind in ALL_CACHES
		{
			let m = TestPlayer::new(3, kind).pick_move(board, turn, &[]).unwrap();
			assert!(reference(&mut TestPlayer::new(3, kind), board.after_move_unchecked(m), turn.next_turn(), 2) > TestPlayer::DRAW);
			let previous = history_repeating(board, m);
			let again = TestPlayer::new(3, kind).pick_move(board, turn, &previous).unwrap();
			assert_ne!(again, m, "{kind:?}");
		}
	}

	#[test]
	fn sheep_behind_takes_a_repetition()
	{
		let (board, turn) = sheep_down_position(Turn::Sheep);
		for kind in ALL_CACHES
		{
			let best = TestPlayer::new(3, kind).pick_move(board, turn, &[]).unwrap();
			assert!(reference(&mut TestPlayer::new(3, kind), board.after_move_unchecked(best), turn.next_turn(), 2) > TestPlayer::DRAW);
			let m = *board.get_moves(turn).iter().find(|&&m| m != best).unwrap();
			let previous = history_repeating(board, m);
			assert_eq!(TestPlayer::new(3, kind).pick_move(board, turn, &previous), Some(m), "{kind:?}");
		}
	}

	#[test]
	fn tiger_takes_the_winning_kill()
	{
		// 16 sheep placed, 4 of them then removed as if killed, so one more kill wins.
		// (1, 0) is left next to the tiger at (0, 0) with (2, 0) empty behind it.
		let mut board = GameBoard::default();
		let mut placed = Vec::new();
		for y in 0..5
		{
			for x in 0..5
			{
				if placed.len() < 16 && (x, y) != (2, 0) && matches!(board.get((x, y)), PieceType::Empty)
				{
					board.make_move(Move::PlaceSheep { pos: (x, y) }).unwrap();
					placed.push((x, y));
				}
			}
		}
		for &pos in &placed[12..]
		{
			board.set(pos, PieceType::Empty);
		}
		assert_eq!(board.sheep_count() + board.sheep_left(), 16);

		for kind in ALL_CACHES
		{
			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]);
	}
}