diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/board.rs | 1149 | ||||
| -rw-r--r-- | src/claude-player.rs | 79 | ||||
| -rw-r--r-- | src/game.rs | 44 | ||||
| -rw-r--r-- | src/local-player.rs | 209 | ||||
| -rw-r--r-- | src/main.rs | 18 | ||||
| -rw-r--r-- | src/player.rs | 420 |
6 files changed, 1919 insertions, 0 deletions
diff --git a/src/board.rs b/src/board.rs new file mode 100644 index 0000000..500241f --- /dev/null +++ b/src/board.rs @@ -0,0 +1,1149 @@ +use std::{fmt::Display}; + +type Pos = (u8, u8); + +pub enum PieceType +{ + Tiger, + Sheep, + Empty +} + +impl Display for PieceType +{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::Tiger => write!(f, "T"), + Self::Sheep => write!(f, "S"), + Self::Empty => write!(f, " "), + } + } +} + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct GameBoard +{ + sheep_mask: u32, + tiger_mask: u32 +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub enum Turn +{ + Tiger, + Sheep +} +impl Turn +{ + pub fn next_turn(&self) -> Turn + { + match self + { + Turn::Tiger => Self::Sheep, + Turn::Sheep => Self::Tiger, + } + } +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)] +pub enum Move +{ + PlaceSheep{pos: Pos}, + MoveSheep{from: Pos, to: Pos}, + MoveTiger{from: Pos, to: Pos} +} + +/// Why `check_move` rejected a move. +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +pub enum MoveError +{ + NoSheepLeft, + PlaceOnOccupied, + SheepStillInHand, + NoSheepToMove, + SheepOntoOccupied, + SheepNotOneStep, + NoTigerToMove, + TigerOntoOccupied, + JumpOverNonSheep, + TigerNotOnLine +} + +impl Display for MoveError +{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let msg = match self { + Self::NoSheepLeft => "No sheep left!", + Self::PlaceOnOccupied => "Can't place a sheep on an occupied point!", + Self::SheepStillInHand => "Can't move sheep until all sheep are placed!", + Self::NoSheepToMove => "No sheep to move!", + Self::SheepOntoOccupied => "Can't move a sheep onto an occupied point!", + Self::SheepNotOneStep => "Sheep can only move one step along a line!", + Self::NoTigerToMove => "No tiger to move!", + Self::TigerOntoOccupied => "Can't move a tiger onto an occupied point!", + Self::JumpOverNonSheep => "Tigers can only jump over a sheep!", + Self::TigerNotOnLine => "Tigers can only step or jump along a line!", + }; + write!(f, "{msg}") + } +} + +impl std::error::Error for MoveError {} + +/// The 25 board bits (0 up to 24); the high 7 bits of `sheep_mask` are the sheep-in-hand count. +const BOARD_MASK: u32 = (1 << 25) - 1; +/// Bit offset of the sheep-in-hand count in `sheep_mask`. +const SHEEP_COUNT_SHIFT: u32 = 25; +/// One sheep in hand, as stored in `sheep_mask`. +const ONE_SHEEP: u32 = 1 << SHEEP_COUNT_SHIFT; + +/// The 8 line directions as (dx, dy). Indices 0..4 are orthogonal, 4..8 diagonal. +const DIRS: [(isize, isize); 8] = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]; + +/// Change in bit index for one step in each direction. +const DELTAS: [isize; 8] = { + let mut deltas = [0; 8]; + let mut d = 0; + while d < 8 + { + deltas[d] = DIRS[d].0 + DIRS[d].1 * 5; + d += 1; + } + deltas +}; + +/// Mask of the points from which moving `dist` points in direction (dx, dy) stays on the board and on a line. +const fn line_sources((dx, dy): (isize, isize), dist: isize) -> u32 +{ + let mut mask = 0; + let mut y = 0; + while y < 5 + { + let mut x = 0; + while x < 5 + { + let tx = x + dx * dist; + let ty = y + dy * dist; + let on_board = tx >= 0 && tx < 5 && ty >= 0 && ty < 5; + let on_line = dx == 0 || dy == 0 || (x + y) % 2 == 0; + if on_board && on_line + { + mask |= 1 << (x + y * 5); + } + x += 1; + } + y += 1; + } + mask +} + +const fn sources_table(dist: isize) -> [u32; 8] +{ + let mut table = [0; 8]; + let mut d = 0; + while d < 8 + { + table[d] = line_sources(DIRS[d], dist); + d += 1; + } + table +} + +/// For each direction, the points a piece can step from. +const STEP_SOURCES: [u32; 8] = sources_table(1); +/// For each direction, the points a tiger can jump from. +const JUMP_SOURCES: [u32; 8] = sources_table(2); + +/// Move every point in `mask` by `delta` bit indices (positive = towards higher index = higher bit). +#[inline(always)] +fn shift(mask: u32, delta: isize) -> u32 +{ + if delta >= 0 { mask << delta } else { mask >> -delta } +} + +/// Iterate the bit indices (0..25) of the points set in `mask`. +#[inline(always)] +fn indices(mut mask: u32) -> impl Iterator<Item = usize> +{ + std::iter::from_fn(move || { + if mask == 0 + { + return None; + } + let idx = mask.trailing_zeros() as usize; + mask &= mask - 1; + Some(idx) + }) +} + +#[inline(always)] +fn pos_of(idx: usize) -> Pos +{ + ((idx % 5) as u8, (idx / 5) as u8) +} + +impl GameBoard +{ + fn bit_idx((x, y): Pos) -> usize + { + if x > 4 || y > 4 + { + panic!("Board is only 5x5!") + } + (x + y * 5) as usize + } + + pub fn get(&self, pos: Pos) -> PieceType { + let bit_idx = GameBoard::bit_idx(pos); + let mask: u32 = 1 << bit_idx; + if (self.tiger_mask & mask) != 0 + { + PieceType::Tiger + } + else if (self.sheep_mask & mask) != 0 + { + PieceType::Sheep + } + else + { + PieceType::Empty + } + } + + pub fn set(&mut self, pos: Pos, piece: PieceType) -> () { + let bit_idx = GameBoard::bit_idx(pos); + let mask: u32 = 1 << bit_idx; + self.tiger_mask &= !mask; + self.sheep_mask &= !mask; + match piece + { + PieceType::Empty => (), + PieceType::Tiger => self.tiger_mask |= mask, + PieceType::Sheep => self.sheep_mask |= mask, + } + } + + pub fn sheep_left(&self) -> u32 { self.sheep_mask >> SHEEP_COUNT_SHIFT } + 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> + { + let tigers = self.tiger_mask; + let sheep = self.sheep_mask & BOARD_MASK; + let empty = !(tigers | sheep) & BOARD_MASK; + + match turn + { + Turn::Sheep if self.sheep_left() > 0 => + { + 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 mut moves = Vec::with_capacity(steps.iter().map(|m| m.count_ones() as usize).sum()); + for d in 0..8 + { + for to in indices(steps[d]) + { + let from = (to as isize - DELTAS[d]) as usize; + moves.push(Move::MoveSheep { from: pos_of(from), to: pos_of(to) }); + } + } + moves + } + 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 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]) + { + let from = (to as isize - DELTAS[d]) as usize; + moves.push(Move::MoveTiger { from: pos_of(from), to: pos_of(to) }); + } + for to in indices(jumps[d]) + { + let from = (to as isize - 2 * DELTAS[d]) as usize; + moves.push(Move::MoveTiger { from: pos_of(from), to: pos_of(to) }); + } + } + moves + } + } + } + + /// Play `mv` if it is legal, otherwise leave the board unchanged and return why it is illegal. + /// A tiger jump kills the sheep it jumps over. + pub fn make_move(&mut self, mv: Move) -> Result<(), MoveError> + { + self.check_move(mv)?; + self.make_move_unchecked(mv); + Ok(()) + } + + /// Play `mv` without checking that it is legal, e.g. for moves straight from `get_moves`. + /// An illegal move leaves the board in a state the rules can't reach. + pub fn make_move_unchecked(&mut self, mv: Move) -> () + { + match mv + { + Move::PlaceSheep { pos } => self.place_sheep(pos), + Move::MoveSheep { from, to } => self.move_sheep(from, to), + Move::MoveTiger { from, to } => self.move_tiger(from, to), + } + } + + /// `Ok` if `mv` is legal, otherwise the reason it is illegal. + pub fn check_move(&self, mv: Move) -> Result<(), MoveError> + { + match mv + { + Move::PlaceSheep { pos } => + { + if self.sheep_left() == 0 + { + return Err(MoveError::NoSheepLeft); + } + if !matches!(self.get(pos), PieceType::Empty) + { + return Err(MoveError::PlaceOnOccupied); + } + } + Move::MoveSheep { from, to } => + { + if self.sheep_left() != 0 + { + return Err(MoveError::SheepStillInHand); + } + if !matches!(self.get(from), PieceType::Sheep) + { + return Err(MoveError::NoSheepToMove); + } + if !matches!(self.get(to), PieceType::Empty) + { + return Err(MoveError::SheepOntoOccupied); + } + if !GameBoard::on_line(from, to, 1) + { + return Err(MoveError::SheepNotOneStep); + } + } + Move::MoveTiger { from, to } => + { + if !matches!(self.get(from), PieceType::Tiger) + { + return Err(MoveError::NoTigerToMove); + } + if !matches!(self.get(to), PieceType::Empty) + { + return Err(MoveError::TigerOntoOccupied); + } + if GameBoard::on_line(from, to, 2) + { + if !matches!(self.get(GameBoard::midpoint(from, to)), PieceType::Sheep) + { + return Err(MoveError::JumpOverNonSheep); + } + } + else if !GameBoard::on_line(from, to, 1) + { + return Err(MoveError::TigerNotOnLine); + } + } + } + Ok(()) + } + + /// True if the board is in a winning state before the next turn. + /// 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 + } + } + + pub fn after_move_unchecked(&self, mv: Move) -> Self + { + let mut new = self.clone(); + new.make_move_unchecked(mv); + new + } + + + /// True if `to` is `dist` points away from `from` along a board line. + /// Orthogonal lines are everywhere; diagonals only run through points where x + y is even. + fn on_line((fx, fy): Pos, (tx, ty): Pos, dist: u8) -> bool + { + let dx = fx.abs_diff(tx); + let dy = fy.abs_diff(ty); + let orthogonal = (dx == dist && dy == 0) || (dx == 0 && dy == dist); + let diagonal = dx == dist && dy == dist && (fx + fy) % 2 == 0; + orthogonal || diagonal + } + + fn midpoint(from: Pos, to: Pos) -> Pos + { + ((from.0 + to.0) / 2, (from.1 + to.1) / 2) + } + + // The functions below apply a move without checking it; `check_move` does the checks. + + fn place_sheep(&mut self, pos: Pos) -> () { + self.set(pos, PieceType::Sheep); + self.sheep_mask -= ONE_SHEEP; + } + + fn move_sheep(&mut self, from: Pos, to: Pos) -> () { + self.set(from, PieceType::Empty); + self.set(to, PieceType::Sheep); + } + + fn kill_sheep(&mut self, pos: Pos) -> () { + self.set(pos, PieceType::Empty); + } + + /// A move of two points along a line is a jump, which kills the sheep in between. + fn move_tiger(&mut self, from: Pos, to: Pos) -> () { + if from.0.abs_diff(to.0) == 2 || from.1.abs_diff(to.1) == 2 + { + self.kill_sheep(GameBoard::midpoint(from, to)); + } + self.set(from, PieceType::Empty); + self.set(to, PieceType::Tiger); + } +} + +impl Default for GameBoard +{ + fn default() -> Self { + Self { tiger_mask: 0b1_0001_0000_0000_0000_0001_0001, sheep_mask: 20 * ONE_SHEEP } + } +} + +#[cfg(test)] +mod tests +{ + use super::*; + + /// A board with no tigers and the full 20 sheep in hand. + fn empty_board() -> GameBoard + { + GameBoard { tiger_mask: 0, sheep_mask: 20 * ONE_SHEEP } + } + + fn is_tiger(board: &GameBoard, pos: Pos) -> bool { matches!(board.get(pos), PieceType::Tiger) } + fn is_sheep(board: &GameBoard, pos: Pos) -> bool { matches!(board.get(pos), PieceType::Sheep) } + fn is_empty(board: &GameBoard, pos: Pos) -> bool { matches!(board.get(pos), PieceType::Empty) } + + // --- bit_idx / get / set --- + + #[test] + fn bit_idx_maps_rows_and_columns() + { + assert_eq!(GameBoard::bit_idx((0, 0)), 0); + assert_eq!(GameBoard::bit_idx((4, 0)), 4); + assert_eq!(GameBoard::bit_idx((0, 1)), 5); + assert_eq!(GameBoard::bit_idx((4, 4)), 24); + } + + #[test] + #[should_panic(expected = "Board is only 5x5!")] + fn bit_idx_rejects_x_out_of_range() + { + GameBoard::bit_idx((5, 0)); + } + + #[test] + #[should_panic(expected = "Board is only 5x5!")] + fn bit_idx_rejects_y_out_of_range() + { + GameBoard::bit_idx((0, 5)); + } + + #[test] + fn set_and_get_every_point() + { + for y in 0..5 + { + for x in 0..5 + { + let mut board = empty_board(); + board.set((x, y), PieceType::Tiger); + assert!(is_tiger(&board, (x, y))); + board.set((x, y), PieceType::Sheep); + assert!(is_sheep(&board, (x, y))); + board.set((x, y), PieceType::Empty); + assert!(is_empty(&board, (x, y))); + } + } + } + + #[test] + fn set_does_not_touch_sheep_count() + { + let mut board = empty_board(); + board.set((4, 4), PieceType::Sheep); + board.set((4, 4), PieceType::Empty); + assert_eq!(board.sheep_left(), 20); + } + + #[test] + fn default_has_tigers_in_corners_and_20_sheep() + { + let board = GameBoard::default(); + for y in 0..5 + { + for x in 0..5 + { + let corner = (x == 0 || x == 4) && (y == 0 || y == 4); + assert_eq!(is_tiger(&board, (x, y)), corner, "at ({x}, {y})"); + assert!(!is_sheep(&board, (x, y))); + } + } + assert_eq!(board.sheep_left(), 20); + } + + // --- on_line --- + + #[test] + fn on_line_orthogonal_everywhere() + { + assert!(GameBoard::on_line((1, 0), (2, 0), 1)); + assert!(GameBoard::on_line((1, 0), (1, 1), 1)); + assert!(GameBoard::on_line((1, 0), (3, 0), 2)); + assert!(GameBoard::on_line((2, 3), (2, 1), 2)); + } + + #[test] + fn on_line_diagonal_only_from_even_points() + { + assert!(GameBoard::on_line((0, 0), (1, 1), 1)); + assert!(GameBoard::on_line((2, 2), (1, 3), 1)); + assert!(GameBoard::on_line((0, 0), (2, 2), 2)); + assert!(!GameBoard::on_line((1, 0), (2, 1), 1)); + assert!(!GameBoard::on_line((1, 2), (2, 3), 1)); + } + + #[test] + fn on_line_rejects_wrong_distance_and_knight_moves() + { + assert!(!GameBoard::on_line((0, 0), (0, 0), 1)); + assert!(!GameBoard::on_line((0, 0), (2, 0), 1)); + assert!(!GameBoard::on_line((0, 0), (1, 0), 2)); + assert!(!GameBoard::on_line((0, 0), (1, 2), 1)); + assert!(!GameBoard::on_line((0, 0), (1, 2), 2)); + } + + // --- place_sheep --- + + #[test] + fn place_sheep_places_and_decrements() + { + let mut board = empty_board(); + board.make_move(Move::PlaceSheep { pos: (2, 2) }).unwrap(); + assert!(is_sheep(&board, (2, 2))); + assert_eq!(board.sheep_left(), 19); + } + + #[test] + fn place_all_20_sheep() + { + let mut board = empty_board(); + for i in 0..20 + { + board.make_move(Move::PlaceSheep { pos: (i % 5, i / 5) }).unwrap(); + } + assert_eq!(board.sheep_left(), 0); + } + + #[test] + fn place_sheep_rejects_when_none_left() + { + let mut board = empty_board(); + for i in 0..20 + { + board.make_move(Move::PlaceSheep { pos: (i % 5, i / 5) }).unwrap(); + } + assert_eq!(board.make_move(Move::PlaceSheep { pos: (0, 4) }), Err(MoveError::NoSheepLeft)); + } + + #[test] + fn place_sheep_rejects_on_sheep() + { + let mut board = empty_board(); + board.make_move(Move::PlaceSheep { pos: (2, 2) }).unwrap(); + assert_eq!(board.make_move(Move::PlaceSheep { pos: (2, 2) }), Err(MoveError::PlaceOnOccupied)); + } + + #[test] + fn place_sheep_rejects_on_tiger() + { + let mut board = GameBoard::default(); + assert_eq!(board.make_move(Move::PlaceSheep { pos: (0, 0) }), Err(MoveError::PlaceOnOccupied)); + } + + // --- move_sheep --- + + /// A board where every sheep has been placed, with sheep on `sheep` and tigers on `tigers`. + fn movement_board(sheep: &[Pos], tigers: &[Pos]) -> GameBoard + { + let mut board = GameBoard { tiger_mask: 0, sheep_mask: 0 }; + for &pos in sheep { board.set(pos, PieceType::Sheep); } + for &pos in tigers { board.set(pos, PieceType::Tiger); } + board + } + + #[test] + fn move_sheep_rejects_while_sheep_in_hand() + { + let mut board = empty_board(); + board.make_move(Move::PlaceSheep { pos: (1, 2) }).unwrap(); + assert_eq!(board.make_move(Move::MoveSheep { from: (1, 2), to: (1, 3) }), Err(MoveError::SheepStillInHand)); + } + + #[test] + fn move_sheep_allowed_after_placing_all_20() + { + let mut board = empty_board(); + for i in 0..20 + { + board.make_move(Move::PlaceSheep { pos: (i % 5, i / 5) }).unwrap(); + } + board.make_move(Move::MoveSheep { from: (0, 3), to: (0, 4) }).unwrap(); + assert!(is_empty(&board, (0, 3))); + assert!(is_sheep(&board, (0, 4))); + } + + #[test] + fn move_sheep_orthogonal() + { + let mut board = movement_board(&[(1, 2)], &[]); + board.make_move(Move::MoveSheep { from: (1, 2), to: (1, 3) }).unwrap(); + assert!(is_empty(&board, (1, 2))); + assert!(is_sheep(&board, (1, 3))); + } + + #[test] + fn move_sheep_diagonal_from_even_point() + { + let mut board = movement_board(&[(2, 2)], &[]); + board.make_move(Move::MoveSheep { from: (2, 2), to: (3, 1) }).unwrap(); + assert!(is_empty(&board, (2, 2))); + assert!(is_sheep(&board, (3, 1))); + } + + #[test] + fn move_sheep_rejects_diagonal_from_odd_point() + { + let mut board = movement_board(&[(1, 2)], &[]); + assert_eq!(board.make_move(Move::MoveSheep { from: (1, 2), to: (2, 3) }), Err(MoveError::SheepNotOneStep)); + } + + #[test] + fn move_sheep_rejects_two_steps() + { + let mut board = movement_board(&[(0, 2)], &[]); + assert_eq!(board.make_move(Move::MoveSheep { from: (0, 2), to: (2, 2) }), Err(MoveError::SheepNotOneStep)); + } + + #[test] + fn move_sheep_rejects_from_empty() + { + let mut board = movement_board(&[], &[]); + assert_eq!(board.make_move(Move::MoveSheep { from: (2, 2), to: (2, 3) }), Err(MoveError::NoSheepToMove)); + } + + #[test] + fn move_sheep_rejects_from_tiger() + { + let mut board = movement_board(&[], &[(0, 0)]); + assert_eq!(board.make_move(Move::MoveSheep { from: (0, 0), to: (1, 0) }), Err(MoveError::NoSheepToMove)); + } + + #[test] + fn move_sheep_rejects_onto_sheep() + { + let mut board = movement_board(&[(2, 2), (2, 3)], &[]); + assert_eq!(board.make_move(Move::MoveSheep { from: (2, 2), to: (2, 3) }), Err(MoveError::SheepOntoOccupied)); + } + + #[test] + fn move_sheep_rejects_onto_tiger() + { + let mut board = movement_board(&[(1, 0)], &[(0, 0)]); + assert_eq!(board.make_move(Move::MoveSheep { from: (1, 0), to: (0, 0) }), Err(MoveError::SheepOntoOccupied)); + } + + // --- kill_sheep --- + + #[test] + fn kill_sheep_removes_sheep() + { + let mut board = empty_board(); + board.make_move(Move::PlaceSheep { pos: (2, 2) }).unwrap(); + board.kill_sheep((2, 2)); + assert!(is_empty(&board, (2, 2))); + assert_eq!(board.sheep_left(), 19); + } + + // --- get_moves / make_move --- + + /// Slow reference: try every (from, to) pair with the rule checks used by check_move. + fn reference_moves(board: &GameBoard, turn: Turn) -> Vec<Move> + { + let all: Vec<Pos> = (0..25).map(pos_of).collect(); + let mut moves = Vec::new(); + match turn + { + Turn::Sheep if board.sheep_left() > 0 => + { + for &pos in &all + { + if is_empty(board, pos) { moves.push(Move::PlaceSheep { pos }); } + } + } + Turn::Sheep => + { + for &from in &all + { + for &to in &all + { + if is_sheep(board, from) && is_empty(board, to) && GameBoard::on_line(from, to, 1) + { + moves.push(Move::MoveSheep { from, to }); + } + } + } + } + Turn::Tiger => + { + for &from in &all + { + for &to in &all + { + if !is_tiger(board, from) || !is_empty(board, to) { continue; } + if GameBoard::on_line(from, to, 1) + || (GameBoard::on_line(from, to, 2) && is_sheep(board, GameBoard::midpoint(from, to))) + { + moves.push(Move::MoveTiger { from, to }); + } + } + } + } + } + moves.sort(); + moves + } + + fn assert_moves_match(board: &GameBoard, turn: Turn) + { + let mut moves = board.get_moves(turn); + moves.sort(); + assert_eq!(moves, reference_moves(board, turn), "turn {turn:?}"); + } + + #[test] + fn get_moves_default_board() + { + let board = GameBoard::default(); + let tiger_moves = board.get_moves(Turn::Tiger); + assert_eq!(tiger_moves.len(), 12); + assert!(tiger_moves.contains(&Move::MoveTiger { from: (0, 0), to: (1, 1) })); + assert!(tiger_moves.contains(&Move::MoveTiger { from: (4, 4), to: (4, 3) })); + assert_eq!(board.get_moves(Turn::Sheep).len(), 21); + assert_moves_match(&board, Turn::Tiger); + assert_moves_match(&board, Turn::Sheep); + } + + #[test] + fn get_moves_tiger_jumps() + { + let board = movement_board(&[(1, 0), (1, 1), (0, 1), (3, 2)], &[(0, 0), (2, 2)]); + let moves = board.get_moves(Turn::Tiger); + assert!(moves.contains(&Move::MoveTiger { from: (0, 0), to: (2, 0) })); + assert!(moves.contains(&Move::MoveTiger { from: (0, 0), to: (0, 2) })); + assert!(moves.contains(&Move::MoveTiger { from: (2, 2), to: (4, 2) })); + assert!(!moves.contains(&Move::MoveTiger { from: (2, 2), to: (0, 0) })); + assert_moves_match(&board, Turn::Tiger); + } + + #[test] + fn get_moves_no_diagonal_from_odd_points() + { + let board = movement_board(&[(1, 2), (2, 1)], &[(1, 0)]); + assert_moves_match(&board, Turn::Sheep); + assert_moves_match(&board, Turn::Tiger); + let moves = board.get_moves(Turn::Sheep); + assert!(!moves.contains(&Move::MoveSheep { from: (1, 2), to: (2, 3) })); + } + + #[test] + fn get_moves_ignores_sheep_count_bits() + { + // A full 0b1111111 in hand must not be read as sheep on any board points. + let board = GameBoard { tiger_mask: 1 << 24, sheep_mask: 0b1111111 * ONE_SHEEP }; + assert_moves_match(&board, Turn::Tiger); + assert_eq!(board.get_moves(Turn::Sheep).len(), 24); + } + + #[test] + fn get_moves_matches_reference_on_random_boards() + { + let mut seed: u64 = 0x2545F4914F6CDD1D; + let mut next = || { seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17; seed }; + for _ in 0..2000 + { + let mut board = GameBoard { tiger_mask: 0, sheep_mask: (next() % 3) as u32 * ONE_SHEEP }; + for idx in 0..25 + { + match next() % 4 + { + 0 => board.set(pos_of(idx), PieceType::Tiger), + 1 | 2 => board.set(pos_of(idx), PieceType::Sheep), + _ => (), + } + } + assert_moves_match(&board, Turn::Tiger); + assert_moves_match(&board, Turn::Sheep); + } + } + + #[test] + fn make_move_plays_every_generated_move() + { + let mut seed: u64 = 0x9E3779B97F4A7C15; + let mut next = || { seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17; seed }; + let mut board = GameBoard::default(); + let mut turn = Turn::Sheep; + for _ in 0..200 + { + let moves = board.get_moves(turn); + if moves.is_empty() { break; } + board.make_move(moves[(next() % moves.len() as u64) as usize]).unwrap(); + turn = if turn == Turn::Sheep { Turn::Tiger } else { Turn::Sheep }; + } + } + + #[test] + fn make_move_dispatches_each_kind() + { + let mut board = GameBoard::default(); + board.make_move(Move::PlaceSheep { pos: (1, 0) }).unwrap(); + assert!(is_sheep(&board, (1, 0))); + board.make_move(Move::MoveTiger { from: (0, 0), to: (2, 0) }).unwrap(); + assert!(is_tiger(&board, (2, 0))); + assert!(is_empty(&board, (1, 0))); + + let mut board = movement_board(&[(2, 2)], &[]); + board.make_move(Move::MoveSheep { from: (2, 2), to: (3, 3) }).unwrap(); + assert!(is_sheep(&board, (3, 3))); + } + + #[test] + fn check_move_accepts_every_generated_move() + { + let board = GameBoard::default(); + for turn in [Turn::Tiger, Turn::Sheep] + { + for mv in board.get_moves(turn) + { + assert_eq!(board.check_move(mv), Ok(()), "{mv:?}"); + } + } + } + + #[test] + fn check_move_reports_each_error() + { + let board = GameBoard::default(); + assert_eq!(board.check_move(Move::PlaceSheep { pos: (0, 0) }), Err(MoveError::PlaceOnOccupied)); + assert_eq!(board.check_move(Move::MoveSheep { from: (1, 0), to: (2, 0) }), Err(MoveError::SheepStillInHand)); + assert_eq!(board.check_move(Move::MoveTiger { from: (2, 2), to: (2, 3) }), Err(MoveError::NoTigerToMove)); + assert_eq!(board.check_move(Move::MoveTiger { from: (0, 0), to: (4, 0) }), Err(MoveError::TigerOntoOccupied)); + assert_eq!(board.check_move(Move::MoveTiger { from: (0, 0), to: (2, 0) }), Err(MoveError::JumpOverNonSheep)); + assert_eq!(board.check_move(Move::MoveTiger { from: (0, 0), to: (1, 2) }), Err(MoveError::TigerNotOnLine)); + + let board = movement_board(&[(1, 2), (1, 3)], &[]); + assert_eq!(board.check_move(Move::PlaceSheep { pos: (0, 0) }), Err(MoveError::NoSheepLeft)); + assert_eq!(board.check_move(Move::MoveSheep { from: (2, 2), to: (2, 3) }), Err(MoveError::NoSheepToMove)); + assert_eq!(board.check_move(Move::MoveSheep { from: (1, 2), to: (1, 3) }), Err(MoveError::SheepOntoOccupied)); + assert_eq!(board.check_move(Move::MoveSheep { from: (1, 2), to: (2, 3) }), Err(MoveError::SheepNotOneStep)); + } + + #[test] + fn make_move_rejects_illegal_move() + { + let mut board = GameBoard::default(); + assert_eq!(board.make_move(Move::MoveTiger { from: (0, 0), to: (2, 0) }), Err(MoveError::JumpOverNonSheep)); + assert!(is_tiger(&board, (0, 0))); + assert!(is_empty(&board, (2, 0))); + } + + // --- move_tiger --- + + #[test] + fn move_tiger_orthogonal_step() + { + let mut board = GameBoard::default(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 0) }).unwrap(); + assert!(is_empty(&board, (0, 0))); + assert!(is_tiger(&board, (1, 0))); + } + + #[test] + fn move_tiger_diagonal_step_from_even_point() + { + let mut board = GameBoard::default(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 1) }).unwrap(); + assert!(is_empty(&board, (0, 0))); + assert!(is_tiger(&board, (1, 1))); + } + + #[test] + fn move_tiger_orthogonal_jump_kills_sheep() + { + let mut board = GameBoard::default(); + board.make_move(Move::PlaceSheep { pos: (1, 0) }).unwrap(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (2, 0) }).unwrap(); + assert!(is_empty(&board, (0, 0))); + assert!(is_empty(&board, (1, 0))); + assert!(is_tiger(&board, (2, 0))); + } + + #[test] + fn move_tiger_diagonal_jump_kills_sheep() + { + let mut board = GameBoard::default(); + board.make_move(Move::PlaceSheep { pos: (1, 1) }).unwrap(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (2, 2) }).unwrap(); + assert!(is_empty(&board, (0, 0))); + assert!(is_empty(&board, (1, 1))); + assert!(is_tiger(&board, (2, 2))); + } + + #[test] + fn move_tiger_jump_leaves_other_sheep_alone() + { + let mut board = GameBoard::default(); + board.make_move(Move::PlaceSheep { pos: (1, 0) }).unwrap(); + board.make_move(Move::PlaceSheep { pos: (0, 1) }).unwrap(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (2, 0) }).unwrap(); + assert!(is_sheep(&board, (0, 1))); + assert_eq!(board.sheep_left(), 18); + } + + #[test] + fn move_tiger_rejects_jumping_empty_point() + { + let mut board = GameBoard::default(); + assert_eq!(board.make_move(Move::MoveTiger { from: (0, 0), to: (2, 0) }), Err(MoveError::JumpOverNonSheep)); + } + + #[test] + fn move_tiger_rejects_jumping_tiger() + { + let mut board = GameBoard::default(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 0) }).unwrap(); + board.make_move(Move::MoveTiger { from: (4, 0), to: (3, 0) }).unwrap(); + board.make_move(Move::MoveTiger { from: (3, 0), to: (2, 0) }).unwrap(); + assert_eq!(board.make_move(Move::MoveTiger { from: (1, 0), to: (3, 0) }), Err(MoveError::JumpOverNonSheep)); + } + + #[test] + fn move_tiger_rejects_diagonal_from_odd_point() + { + let mut board = GameBoard::default(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 0) }).unwrap(); + assert_eq!(board.make_move(Move::MoveTiger { from: (1, 0), to: (2, 1) }), Err(MoveError::TigerNotOnLine)); + } + + #[test] + fn move_tiger_rejects_diagonal_jump_from_odd_point() + { + let mut board = GameBoard::default(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 0) }).unwrap(); + board.make_move(Move::PlaceSheep { pos: (2, 1) }).unwrap(); + assert_eq!(board.make_move(Move::MoveTiger { from: (1, 0), to: (3, 2) }), Err(MoveError::TigerNotOnLine)); + } + + #[test] + fn move_tiger_rejects_three_steps() + { + let mut board = GameBoard::default(); + assert_eq!(board.make_move(Move::MoveTiger { from: (0, 0), to: (3, 0) }), Err(MoveError::TigerNotOnLine)); + } + + #[test] + fn move_tiger_rejects_knight_move() + { + let mut board = GameBoard::default(); + assert_eq!(board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 2) }), Err(MoveError::TigerNotOnLine)); + } + + #[test] + fn move_tiger_rejects_from_empty() + { + let mut board = GameBoard::default(); + assert_eq!(board.make_move(Move::MoveTiger { from: (2, 2), to: (2, 3) }), Err(MoveError::NoTigerToMove)); + } + + #[test] + fn move_tiger_rejects_from_sheep() + { + let mut board = GameBoard::default(); + board.make_move(Move::PlaceSheep { pos: (2, 2) }).unwrap(); + assert_eq!(board.make_move(Move::MoveTiger { from: (2, 2), to: (2, 3) }), Err(MoveError::NoTigerToMove)); + } + + #[test] + fn move_tiger_rejects_onto_sheep() + { + let mut board = GameBoard::default(); + board.make_move(Move::PlaceSheep { pos: (1, 0) }).unwrap(); + assert_eq!(board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 0) }), Err(MoveError::TigerOntoOccupied)); + } + + #[test] + fn move_tiger_rejects_onto_tiger() + { + let mut board = GameBoard::default(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 0) }).unwrap(); + board.make_move(Move::MoveTiger { from: (1, 0), to: (0, 0) }).unwrap(); + board.make_move(Move::MoveTiger { from: (0, 0), to: (1, 0) }).unwrap(); + board.make_move(Move::MoveTiger { from: (4, 0), to: (3, 0) }).unwrap(); + board.make_move(Move::MoveTiger { from: (3, 0), to: (2, 0) }).unwrap(); + assert_eq!(board.make_move(Move::MoveTiger { from: (2, 0), to: (1, 0) }), Err(MoveError::TigerOntoOccupied)); + } + + // --- sheep_left / sheep_count --- + + #[test] + fn sheep_left_counts_down_only_when_placing() + { + let mut board = GameBoard::default(); + assert_eq!(board.sheep_left(), 20); + board.make_move(Move::PlaceSheep { pos: (1, 0) }).unwrap(); + assert_eq!(board.sheep_left(), 19); + board.make_move(Move::MoveTiger { from: (0, 0), to: (2, 0) }).unwrap(); + assert_eq!(board.sheep_left(), 19); + board.make_move(Move::PlaceSheep { pos: (2, 2) }).unwrap(); + assert_eq!(board.sheep_left(), 18); + } + + #[test] + fn sheep_count_counts_sheep_on_board() + { + let mut board = GameBoard::default(); + assert_eq!(board.sheep_count(), 0); + board.make_move(Move::PlaceSheep { pos: (1, 0) }).unwrap(); + board.make_move(Move::MoveTiger { from: (4, 4), to: (3, 3) }).unwrap(); + board.make_move(Move::PlaceSheep { pos: (2, 2) }).unwrap(); + assert_eq!(board.sheep_count(), 2); + board.make_move(Move::MoveTiger { from: (0, 0), to: (2, 0) }).unwrap(); + assert_eq!(board.sheep_count(), 1); + assert_eq!(board.sheep_left(), 18); + } + + #[test] + fn sheep_count_ignores_sheep_in_hand() + { + let board = GameBoard { tiger_mask: 0, sheep_mask: 0b1111111 * ONE_SHEEP }; + assert_eq!(board.sheep_count(), 0); + let board = movement_board(&[(0, 0), (4, 4), (2, 3)], &[]); + assert_eq!(board.sheep_count(), 3); + } + + // --- check_win --- + + #[test] + fn check_win_not_at_start() + { + let board = GameBoard::default(); + assert!(!board.check_win(Turn::Sheep)); + assert!(!board.check_win(Turn::Tiger)); + } + + #[test] + fn check_win_after_fifth_kill() + { + let mut board = GameBoard::default(); + let kills = [ + ((1, 0), (0, 0), (2, 0)), + ((1, 4), (0, 4), (2, 4)), + ((4, 1), (4, 0), (4, 2)), + ((2, 1), (2, 0), (2, 2)), + ((1, 1), (2, 2), (0, 0)), + ]; + for (i, &(sheep, from, to)) in kills.iter().enumerate() + { + assert!(!board.check_win(Turn::Sheep), "before kill {}", i + 1); + board.make_move(Move::PlaceSheep { pos: sheep }).unwrap(); + board.make_move(Move::MoveTiger { from, to }).unwrap(); + assert!(is_empty(&board, sheep)); + } + assert_eq!(board.sheep_count() + board.sheep_left(), 15); + // Checked before the sheep's turn, so the tigers (who just moved) have won. + assert!(board.check_win(Turn::Sheep)); + } + + #[test] + fn check_win_counts_sheep_on_board_and_in_hand() + { + // Sheep fill the left two columns, well away from the tiger in the far corner. + let on_board: Vec<Pos> = (0..2).flat_map(|x| (0..5).map(move |y| (x, y))).collect(); + let mut board = movement_board(&on_board[..5], &[(4, 4)]); + board.sheep_mask |= 10 * ONE_SHEEP; + assert!(board.check_win(Turn::Sheep), "5 on board + 10 in hand"); + + let mut board = movement_board(&on_board[..6], &[(4, 4)]); + board.sheep_mask |= 10 * ONE_SHEEP; + assert!(!board.check_win(Turn::Sheep), "6 on board + 10 in hand"); + assert!(!board.check_win(Turn::Tiger), "6 on board + 10 in hand"); + } + + #[test] + fn check_win_when_tigers_are_trapped() + { + let mut board = movement_board(&[(1, 0), (0, 1), (1, 1), (2, 0), (0, 2), (2, 2)], &[(0, 0)]); + board.sheep_mask |= 14 * ONE_SHEEP; + assert!(board.get_moves(Turn::Tiger).is_empty()); + assert!(board.check_win(Turn::Tiger)); + assert!(!board.check_win(Turn::Sheep)); + } + + #[test] + fn check_win_when_sheep_are_trapped() + { + // The only empty point is (4, 4), and every point next to it holds a tiger. + let tigers = [(0, 0), (3, 3), (4, 3), (3, 4)]; + let sheep: Vec<Pos> = (0..25).map(pos_of).filter(|p| !tigers.contains(p) && *p != (4, 4)).collect(); + assert_eq!(sheep.len(), 20); + let board = movement_board(&sheep, &tigers); + assert!(board.get_moves(Turn::Sheep).is_empty()); + assert!(board.check_win(Turn::Sheep)); + assert!(!board.check_win(Turn::Tiger)); + } +} diff --git a/src/claude-player.rs b/src/claude-player.rs new file mode 100644 index 0000000..4590c12 --- /dev/null +++ b/src/claude-player.rs @@ -0,0 +1,79 @@ +use std::{collections::HashMap, time::Duration}; + +use crate::{board::{GameBoard, Move, PieceType, Turn}, player::{CacheEntry, MinimaxPlayer}}; + +/// Sheep that start the game: on the board plus in hand. +const TOTAL_SHEEP: u32 = 20; + +/// A computer player that searches with minimax for `time_limit` per move and scores positions with `evaluate`. +pub struct ClaudePlayer +{ + pub time_limit: Duration, + cache: HashMap<(GameBoard, Turn, usize), CacheEntry> +} + +impl Default for ClaudePlayer +{ + fn default() -> Self + { + Self { time_limit: Duration::from_secs(1), cache: HashMap::new() } + } +} + +impl ClaudePlayer +{ + pub fn new(time_limit: Duration) -> Self + { + Self { time_limit, cache: HashMap::new() } + } +} + +impl MinimaxPlayer for ClaudePlayer +{ + /// Scored from the tigers' side. In order of weight: + /// - dead sheep, since five of them wins the game for the tigers; + /// - jumps the tigers could make right now (sheep left hanging); + /// - tigers boxed in with no move at all, since trapping every tiger wins for the sheep; + /// - tiger mobility in general, since the sheep win by squeezing it to zero. + fn evaluate(&mut self, board: &GameBoard) -> f32 + { + let dead = TOTAL_SHEEP - board.sheep_count() - board.sheep_left(); + + let tiger_moves = board.get_moves(Turn::Tiger); + let jumps = tiger_moves.iter().filter(|m| is_jump(**m)).count(); + + let mut trapped = 0; + for y in 0..5 + { + for x in 0..5 + { + if matches!(board.get((x, y)), PieceType::Tiger) + && !tiger_moves.iter().any(|m| matches!(m, Move::MoveTiger { from, .. } if *from == (x, y))) + { + trapped += 1; + } + } + } + + 100.0 * dead as f32 + + 20.0 * jumps as f32 + - 15.0 * trapped as f32 + + 2.0 * tiger_moves.len() as f32 + } + + fn time_limit(&self) -> Duration { self.time_limit } + + fn cache(&mut self) -> Option<&mut dyn crate::player::ScoreCache> { + Some(&mut self.cache) + } +} + +/// True for a tiger move of two points, which always jumps (and kills) a sheep. +fn is_jump(mv: Move) -> bool +{ + match mv + { + Move::MoveTiger { from: (fx, fy), to: (tx, ty) } => fx.abs_diff(tx) == 2 || fy.abs_diff(ty) == 2, + _ => false, + } +} diff --git a/src/game.rs b/src/game.rs new file mode 100644 index 0000000..96f71b3 --- /dev/null +++ b/src/game.rs @@ -0,0 +1,44 @@ +use crate::{board::{GameBoard, Turn}, player::Player}; + +pub struct GameHandler +{ + board: GameBoard, +} + +impl Default for GameHandler +{ + fn default() -> Self + { + Self + { + board: GameBoard::default() + } + } +} + +impl GameHandler +{ + // fn play_move<T: Player>(&mut self, player: &mut T) + // { + // let m = player.pick_move(self.board); + // self.board.make_move(m).unwrap(); + // } + + /// Play until someone wins, with `p1` as the sheep and `p2` as the tigers. Returns the winner. + pub fn play_game<T1: Player, T2: Player>(&mut self, p1: &mut T1, p2: &mut T2) -> Turn + { + let mut turn = Turn::Sheep; + while !self.board.check_win(turn) + { + let m = match turn + { + Turn::Sheep => p1.pick_move(self.board, turn), + Turn::Tiger => p2.pick_move(self.board, turn), + }; + self.board.make_move(m).unwrap(); + turn = turn.next_turn(); + } + // check_win runs before `turn`'s move, so whoever moved last has won. + turn.next_turn() + } +} diff --git a/src/local-player.rs b/src/local-player.rs new file mode 100644 index 0000000..962460e --- /dev/null +++ b/src/local-player.rs @@ -0,0 +1,209 @@ +use std::io::{self, BufRead, Write}; + +use crate::{board::{GameBoard, Move, PieceType, Turn}, player::Player}; + +/// A human player at the terminal. Shows the board, lists the legal moves and reads a choice from stdin. +pub struct LocalPlayer; + +impl Player for LocalPlayer +{ + fn pick_move(&mut self, board: GameBoard, turn: Turn) -> Move + { + let mut moves = board.get_moves(turn); + moves.sort(); + print!("{}", render_board(&board)); + println!(); + println!("{:?} to move. Sheep in hand: {}, on board: {}", turn, board.sheep_left(), board.sheep_count()); + for (i, mv) in moves.iter().enumerate() + { + println!("{:>3}) {}", i + 1, describe_move(*mv)); + } + println!("Enter a move number, a point \"x y\" to place, or \"x y x y\" to move from/to. \"q\" quits."); + + let stdin = io::stdin(); + let mut lines = stdin.lock().lines(); + loop + { + print!("> "); + io::stdout().flush().unwrap(); + let line = match lines.next() + { + Some(Ok(line)) => line, + _ => std::process::exit(0), + }; + if line.trim() == "q" + { + std::process::exit(0); + } + match parse_choice(&line, &board, turn, &moves) + { + Ok(mv) => return mv, + Err(err) => println!("{err}"), + } + } + } +} + +/// Turn a line of input into one of `moves`, or explain why it isn't one. +fn parse_choice(input: &str, board: &GameBoard, turn: Turn, moves: &[Move]) -> Result<Move, String> +{ + let nums: Vec<u8> = input + .split(|c: char| c.is_whitespace() || c == ',') + .filter(|s| !s.is_empty()) + .map(|s| s.parse().map_err(|_| format!("\"{s}\" isn't a number"))) + .collect::<Result<_, _>>()?; + + let mv = match nums[..] + { + [n] => + { + return moves.get((n as usize).wrapping_sub(1)).copied() + .ok_or_else(|| format!("Pick a move from 1 to {}", moves.len())); + } + [x, y] => Move::PlaceSheep { pos: (x, y) }, + [fx, fy, tx, ty] => match turn + { + Turn::Sheep => Move::MoveSheep { from: (fx, fy), to: (tx, ty) }, + Turn::Tiger => Move::MoveTiger { from: (fx, fy), to: (tx, ty) }, + }, + _ => return Err("Enter 1, 2 or 4 numbers".to_string()), + }; + + if points(mv).iter().any(|&(x, y)| x > 4 || y > 4) + { + return Err("Points go from 0 to 4".to_string()); + } + if moves.contains(&mv) + { + return Ok(mv); + } + match board.check_move(mv) + { + Err(err) => Err(err.to_string()), + // Legal by the rules but not this side's move, e.g. placing as the tiger. + Ok(()) => Err(format!("{} isn't a move for {:?}", describe_move(mv), turn)), + } +} + +fn points(mv: Move) -> Vec<(u8, u8)> +{ + match mv + { + Move::PlaceSheep { pos } => vec![pos], + Move::MoveSheep { from, to } | Move::MoveTiger { from, to } => vec![from, to], + } +} + +fn describe_move(mv: Move) -> String +{ + match mv + { + Move::PlaceSheep { pos: (x, y) } => format!("Place sheep at {x} {y}"), + Move::MoveSheep { from: (fx, fy), to: (tx, ty) } => format!("Sheep {fx} {fy} -> {tx} {ty}"), + Move::MoveTiger { from: (fx, fy), to: (tx, ty) } => + { + let jump = if fx.abs_diff(tx) == 2 || fy.abs_diff(ty) == 2 { " (jump)" } else { "" }; + format!("Tiger {fx} {fy} -> {tx} {ty}{jump}") + } + } +} + +/// The board with its lines, x across the top and y down the side: +/// +/// ```text +/// 0 1 2 3 4 +/// 0 T - . - . - . - T +/// | \ | / | \ | / | +/// 1 . - . - . - . - . +/// ``` +fn render_board(board: &GameBoard) -> String +{ + let mut out = String::from(" 0 1 2 3 4\n"); + for y in 0..5u8 + { + out += &format!("{y} "); + for x in 0..5u8 + { + out += match board.get((x, y)) + { + PieceType::Tiger => "T", + PieceType::Sheep => "S", + PieceType::Empty => ".", + }; + if x < 4 + { + out += " - "; + } + } + out += "\n"; + if y < 4 + { + out += " "; + for x in 0..5u8 + { + out += "|"; + if x < 4 + { + out += if (x + y) % 2 == 0 { " \\ " } else { " / " }; + } + } + out += "\n"; + } + } + out +} + +#[cfg(test)] +mod tests +{ + use super::*; + + #[test] + fn render_default_board() + { + let expected = " 0 1 2 3 4\n\ + 0 T - . - . - . - T\n | \\ | / | \\ | / |\n\ + 1 . - . - . - . - .\n | / | \\ | / | \\ |\n\ + 2 . - . - . - . - .\n | \\ | / | \\ | / |\n\ + 3 . - . - . - . - .\n | / | \\ | / | \\ |\n\ + 4 T - . - . - . - T\n"; + assert_eq!(render_board(&GameBoard::default()), expected); + } + + #[test] + fn parse_choice_by_number() + { + let board = GameBoard::default(); + let moves = board.get_moves(Turn::Tiger); + assert_eq!(parse_choice("1", &board, Turn::Tiger, &moves), Ok(moves[0])); + assert_eq!(parse_choice(" 3 ", &board, Turn::Tiger, &moves), Ok(moves[2])); + assert!(parse_choice("0", &board, Turn::Tiger, &moves).is_err()); + assert!(parse_choice("99", &board, Turn::Tiger, &moves).is_err()); + } + + #[test] + fn parse_choice_by_points() + { + let board = GameBoard::default(); + let sheep = board.get_moves(Turn::Sheep); + let tiger = board.get_moves(Turn::Tiger); + assert_eq!(parse_choice("2 2", &board, Turn::Sheep, &sheep), Ok(Move::PlaceSheep { pos: (2, 2) })); + assert_eq!(parse_choice("2,2", &board, Turn::Sheep, &sheep), Ok(Move::PlaceSheep { pos: (2, 2) })); + assert_eq!(parse_choice("0 0 1 1", &board, Turn::Tiger, &tiger), Ok(Move::MoveTiger { from: (0, 0), to: (1, 1) })); + } + + #[test] + fn parse_choice_explains_bad_input() + { + let board = GameBoard::default(); + let sheep = board.get_moves(Turn::Sheep); + let tiger = board.get_moves(Turn::Tiger); + assert_eq!(parse_choice("0 0", &board, Turn::Sheep, &sheep), Err("Can't place a sheep on an occupied point!".to_string())); + assert_eq!(parse_choice("0 0 2 0", &board, Turn::Tiger, &tiger), Err("Tigers can only jump over a sheep!".to_string())); + assert_eq!(parse_choice("2 2", &board, Turn::Tiger, &tiger), Err("Place sheep at 2 2 isn't a move for Tiger".to_string())); + assert_eq!(parse_choice("5 0", &board, Turn::Sheep, &sheep), Err("Points go from 0 to 4".to_string())); + assert!(parse_choice("a", &board, Turn::Sheep, &sheep).is_err()); + assert!(parse_choice("1 2 3", &board, Turn::Sheep, &sheep).is_err()); + assert!(parse_choice("", &board, Turn::Sheep, &sheep).is_err()); + } +} diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..981d3dd --- /dev/null +++ b/src/main.rs @@ -0,0 +1,18 @@ +use std::time::Duration; + +use crate::{claude_player::ClaudePlayer, game::GameHandler, local_player::LocalPlayer}; + +mod board; +mod player; +mod game; +#[path = "local-player.rs"] +mod local_player; +#[path = "claude-player.rs"] +mod claude_player; + +fn main() { + let mut game = GameHandler::default(); + // I play sheep, claude plays tiger + let winner = game.play_game(&mut LocalPlayer, &mut ClaudePlayer::new(Duration::from_secs(2))); + println!("{winner:?} wins!"); +} diff --git a/src/player.rs b/src/player.rs new file mode 100644 index 0000000..f46e36b --- /dev/null +++ b/src/player.rs @@ -0,0 +1,420 @@ +use std::{collections::HashMap, time::{Duration, Instant}}; + +use crate::board::{GameBoard, Move, Turn}; + +pub trait Player +{ + fn pick_move(&mut self, board: GameBoard, turn: Turn) -> Move; +} + +pub type ScoreType = f32; + +/// 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. +/// 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(); + } +} + +pub trait MinimaxPlayer +{ + const WIN: f32 = f32::INFINITY; + + /// Scores outside `alpha..beta` are only bounds: at most `alpha`, or at least `beta`. + /// 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 mut hint = None; + if let Some(k) = known + { + if k.lower >= beta + { + return Some(k.lower); + } + if k.upper <= alpha || k.lower == k.upper + { + return Some(k.upper); + } + alpha = alpha.max(k.lower); + beta = beta.min(k.upper); + hint = k.best; + } + // 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); + } + let (score, best) = self.minimax_uncached(board, turn, depth, alpha, beta, hint, deadline)?; + if let Some(c) = self.cache() + { + // 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(&board, 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. + 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>)> { + if board.check_win(turn) + { + let score = match turn { + Turn::Tiger => -Self::WIN, + Turn::Sheep => Self::WIN, + }; + return Some((score, None)); + } + if depth == 0 + { + return Some((self.evaluate(&board), None)); + } + if deadline.is_some_and(|d| Instant::now() >= d) + { + return None; + } + + let mut moves = board.get_moves(turn); + 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 m in moves + { + let score = self.minimax(board.after_move_unchecked(m), next, depth - 1, alpha, beta, deadline)?; + 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 + { + 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 + } + + /// 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 } + + /// How long `pick_move` may spend searching. + fn time_limit(&self) -> Duration { Duration::from_secs(1) } +} + +impl<P: MinimaxPlayer> Player for P +{ + + /// 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) -> 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(); + } + let mut best = 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) + else + { + break; + }; + best = m; + // 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; + } + } + best.expect("pick_move called with no legal moves") + } + +} + +#[cfg(test)] +mod tests +{ + use super::*; + use crate::board::PieceType; + + /// A minimax player with a cheap evaluation that still varies a lot between positions. + struct TestPlayer + { + depth: usize, + time_limit: Duration, + cache: Option<HashMap<(GameBoard, Turn, usize), CacheEntry>>, + } + + impl TestPlayer + { + fn new(depth: usize, cached: bool) -> Self + { + // 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) } + } + } + + impl MinimaxPlayer for TestPlayer + { + fn evaluate(&mut self, board: &GameBoard) -> 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> + { + self.cache.as_mut().map(|c| c as &mut dyn ScoreCache) + } + + 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 + { + if board.check_win(turn) + { + return match turn { Turn::Tiger => -TestPlayer::WIN, Turn::Sheep => TestPlayer::WIN }; + } + if depth == 0 + { + return player.evaluate(&board); + } + let scores = board.get_moves(turn).into_iter() + .map(|m| reference(player, board.after_move_unchecked(m), turn.next_turn(), depth - 1)); + match turn + { + Turn::Tiger => scores.fold(f32::NEG_INFINITY, f32::max), + Turn::Sheep => scores.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, false); + 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"); + } + } + } + + #[test] + fn cached_alpha_beta_matches_plain_minimax() + { + for (board, turn) in test_positions() + { + 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"); + } + } + } + + #[test] + fn any_hint_gives_the_same_score() + { + for (board, turn) in test_positions() + { + let mut player = TestPlayer::new(3, true); + 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:?}"); + } + } + } + + #[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()); + } + + #[test] + fn pick_move_respects_time_limit() + { + let mut player = TestPlayer::new(64, true); + player.time_limit = Duration::from_millis(50); + let board = GameBoard::default(); + let start = Instant::now(); + let m = player.pick_move(board, Turn::Sheep); + 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 cached in [false, true] + { + let mut player = TestPlayer::new(4, cached); + let best = reference(&mut player, board, turn, 4); + let m = player.pick_move(board, turn); + let score = reference(&mut player, board.after_move_unchecked(m), turn.next_turn(), 3); + assert_eq!(score, best, "{turn:?} picked {m:?} (cached: {cached})"); + } + } + } + + #[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 cached in [false, true] + { + let m = TestPlayer::new(3, cached).pick_move(board, Turn::Tiger); + assert!(board.after_move_unchecked(m).check_win(Turn::Sheep), "picked {m:?} (cached: {cached})"); + } + } +} |