From 15bdaa5d550115d97be3f89126c924b49c10a70f Mon Sep 17 00:00:00 2001 From: Dylan Date: Mon, 19 Oct 2026 00:37:17 +1300 Subject: feat: Initial commit What works: - Minimax search - With a simple player claude designed - Manual player - Move generation - Board display What needs improvement: - Manual player - Game coordinator - Draw checking - Nix setup --- .envrc | 1 + .gitignore | 12 + CLAUDE.md | 49 +++ Cargo.lock | 7 + Cargo.toml | 8 + default.nix | 9 + flake.lock | 137 ++++++ flake.nix | 38 ++ plans.org | 10 + shell.nix | 9 + src/board.rs | 1149 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/claude-player.rs | 79 ++++ src/game.rs | 44 ++ src/local-player.rs | 209 +++++++++ src/main.rs | 18 + src/player.rs | 420 ++++++++++++++++++ 16 files changed, 2199 insertions(+) create mode 100644 .envrc create mode 100644 .gitignore create mode 100644 CLAUDE.md create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 default.nix create mode 100644 flake.lock create mode 100644 flake.nix create mode 100644 plans.org create mode 100644 shell.nix create mode 100644 src/board.rs create mode 100644 src/claude-player.rs create mode 100644 src/game.rs create mode 100644 src/local-player.rs create mode 100644 src/main.rs create mode 100644 src/player.rs diff --git a/.envrc b/.envrc new file mode 100644 index 0000000..3550a30 --- /dev/null +++ b/.envrc @@ -0,0 +1 @@ +use flake diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..52b5187 --- /dev/null +++ b/.gitignore @@ -0,0 +1,12 @@ +# Cargo build output +/target + +# Nix build output symlinks (nix build) +/result +/result-* + +# direnv cache +/.direnv + +# Temporary removing github workflows +.github \ No newline at end of file diff --git a/CLAUDE.md b/CLAUDE.md new file mode 100644 index 0000000..29064ea --- /dev/null +++ b/CLAUDE.md @@ -0,0 +1,49 @@ +# CLAUDE.md + +This file provides guidance to Claude Code (claude.ai/code) when working with code in this repository. + +## Project + +A Rust implementation of "Tigers and Sheep" (a Bagh-Chal–style hunt game) on a 5x5 point board. The crate/binary is still named `rust-hello` (leftover from the template), not `tigers-and-sheep`. + +## Environment & commands + +The toolchain comes from a Nix flake (`flake.nix`, loaded via direnv `.envrc` → `use flake`); `shell.nix`/`default.nix` are flake-compat shims. Enter with `nix develop` if direnv isn't active. + +- Build: `cargo build` +- Run: `cargo run` +- Test all: `cargo test` +- Single test: `cargo test move_tiger_diagonal_jump_kills_sheep` (any substring of the test name filters) +- Lint / format: `cargo clippy`, `cargo fmt` +- Nix package build (what CI runs in `.github/workflows/build_nix.yml`): `nix build` + +## Architecture + +- `src/board.rs` — all game logic and its unit tests (`#[cfg(test)] mod tests` at the bottom). +- `src/player.rs` — the `Player` trait (`pick_move(board, turn) -> Move`). Also the private `MinimaxPlayer` trait: implementors supply `evaluate` (positive favours tigers) and optionally `depth()`, and a blanket impl makes every `MinimaxPlayer` a `Player`. +- `src/game.rs` — `GameHandler::play_game(sheep_player, tiger_player)` runs the game loop. Sheep move first, and it returns the winning `Turn`. +- `src/local-player.rs` (module `local_player`, pulled in via `#[path]` because of the hyphen) — `LocalPlayer`, a human at the terminal: renders the board, lists legal moves, and parses a move number or coordinates from stdin. +- `src/main.rs` — plays a game between two `LocalPlayer`s and prints the winner. + +Win check: `check_win(turn)` is called with the side about to move, and true means the side that *just* moved has won. Tigers win once 5 sheep are dead (`sheep_count() + sheep_left() <= 15`); otherwise the side that just moved wins if the side to move has no legal moves. + +### Board representation (`GameBoard`) + +The board is two `u32` bitmasks, `tiger_mask` and `sheep_mask`. This encoding is non-obvious: + +- Point `(x, y)` maps to index `x + y*5` (0..24), and its bit is `1 << idx`. So board bits occupy the **low 25 bits** (`BOARD_MASK`), with `(0,0)` at bit 0. +- The **high 7 bits of `sheep_mask`** (from `SHEEP_COUNT_SHIFT = 25`) are not board points — they hold the count of sheep still in hand (starts at 20). `sheep_left()` reads it; `place_sheep` subtracts `ONE_SHEEP` (`1 << 25`) from `sheep_mask` directly. Killing a sheep does not change this count (it counts unplaced sheep, not living ones). +- `Pos = (u8, u8)` is `(x, y)`; out-of-range coordinates panic in `bit_idx`. +- Default layout: tigers in the four corners, 20 sheep in hand. + +### Rules as implemented + +- Movement follows board lines: orthogonal lines everywhere; diagonals only through points where `x + y` is even (`on_line`). +- Sheep: placed one at a time until none remain in hand; only then may they move one step along a line. +- Tigers: step one along a line, or jump two along a line over a sheep, which kills it. +- `check_move` returns `Err(MoveError::…)` for an illegal move; `make_move` runs it first and returns the error without touching the board. `make_move_unchecked` skips the checks (for moves from `get_moves`). `MoveError`'s `Display` gives a human-readable message. Tests assert on the specific `MoveError` variant. +- `bit_idx` still panics on out-of-range coordinates. + +## Code style + +Mostly tabs for indentation, with braces on their own line (Allman style). A few trait-impl blocks use 4-space indentation, and `cargo fmt` would reformat everything, so don't run it across the whole crate unless asked. diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..ee133b2 --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "tigers-and-sheep-rs" +version = "0.1.0" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..646cfba --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "tigers-and-sheep-rs" +version = "0.1.0" +edition = "2021" + +[[bin]] +name = "tigers-and-sheep-rs" +path = "src/main.rs" diff --git a/default.nix b/default.nix new file mode 100644 index 0000000..2541ddb --- /dev/null +++ b/default.nix @@ -0,0 +1,9 @@ +(import + (fetchTarball { + url = "https://github.com/edolstra/flake-compat/archive/99f1c2157fba4bfe6211a321fd0ee43199025dbf.tar.gz"; + sha256 = "0x2jn3vrawwv9xp15674wjz9pixwjyj3j771izayl962zziivbx2"; + }) + { + src = ./.; + } +).defaultNix diff --git a/flake.lock b/flake.lock new file mode 100644 index 0000000..babfbdc --- /dev/null +++ b/flake.lock @@ -0,0 +1,137 @@ +{ + "nodes": { + "fenix": { + "inputs": { + "nixpkgs": [ + "naersk", + "nixpkgs" + ], + "rust-analyzer-src": "rust-analyzer-src" + }, + "locked": { + "lastModified": 1752475459, + "narHash": "sha256-z6QEu4ZFuHiqdOPbYss4/Q8B0BFhacR8ts6jO/F/aOU=", + "owner": "nix-community", + "repo": "fenix", + "rev": "bf0d6f70f4c9a9cf8845f992105652173f4b617f", + "type": "github" + }, + "original": { + "owner": "nix-community", + "repo": "fenix", + "type": "github" + } + }, + "naersk": { + "inputs": { + "fenix": "fenix", + "nixpkgs": "nixpkgs" + }, + "locked": { + "lastModified": 1782220280, + "narHash": "sha256-thLTFbp9D5Qknmh8q/v4FRpLGphUSijT3E86cbLYTXo=", + "owner": "nix-community", + "repo": "naersk", + "rev": "9aa07bb0256d300219b30622d2454e85f7f3667e", + "type": "github" + }, + "original": { + "owner": "nix-community", + "ref": "master", + "repo": "naersk", + "type": "github" + } + }, + "nixpkgs": { + "locked": { + "lastModified": 1752077645, + "narHash": "sha256-HM791ZQtXV93xtCY+ZxG1REzhQenSQO020cu6rHtAPk=", + "owner": "NixOS", + "repo": "nixpkgs", + "rev": "be9e214982e20b8310878ac2baa063a961c1bdf6", + "type": "github" + }, + "original": { + "owner": "NixOS", + "ref": "nixpkgs-unstable", + "repo": "nixpkgs", + "type": "github" + } + }, + "nixpkgs_2": { + "locked": { + "lastModified": 1780145889, + "narHash": "sha256-md0zn0RnwNvPyASas1yG5YUuwQ4ALA6ucL50l0DvqCo=", + "owner": "nixos", + "repo": "nixpkgs", + "rev": "8c50a710ddca43d7a530fb805ad55bde8d0141c5", + "type": "github" + }, + "original": { + "owner": "nixos", + "ref": "26.05", + "repo": "nixpkgs", + "type": "github" + } + }, + "root": { + "inputs": { + "naersk": "naersk", + "nixpkgs": "nixpkgs_2", + "utils": "utils" + } + }, + "rust-analyzer-src": { + "flake": false, + "locked": { + "lastModified": 1752428706, + "narHash": "sha256-EJcdxw3aXfP8Ex1Nm3s0awyH9egQvB2Gu+QEnJn2Sfg=", + "owner": "rust-lang", + "repo": "rust-analyzer", + "rev": "591e3b7624be97e4443ea7b5542c191311aa141d", + "type": "github" + }, + "original": { + "owner": "rust-lang", + "ref": "nightly", + "repo": "rust-analyzer", + "type": "github" + } + }, + "systems": { + "locked": { + "lastModified": 1681028828, + "narHash": "sha256-Vy1rq5AaRuLzOxct8nz4T6wlgyUR7zLU309k9mBC768=", + "owner": "nix-systems", + "repo": "default", + "rev": "da67096a3b9bf56a91d16901293e51ba5b49a27e", + "type": "github" + }, + "original": { + "owner": "nix-systems", + "repo": "default", + "type": "github" + } + }, + "utils": { + "inputs": { + "systems": "systems" + }, + "locked": { + "lastModified": 1731533236, + "narHash": "sha256-l0KFg5HjrsfsO/JpG+r7fRrqm12kzFHyUHqHCVpMMbI=", + "owner": "numtide", + "repo": "flake-utils", + "rev": "11707dc2f618dd54ca8739b309ec4fc024de578b", + "type": "github" + }, + "original": { + "owner": "numtide", + "repo": "flake-utils", + "type": "github" + } + } + }, + "root": "root", + "version": 7 +} diff --git a/flake.nix b/flake.nix new file mode 100644 index 0000000..2c3f987 --- /dev/null +++ b/flake.nix @@ -0,0 +1,38 @@ +{ + inputs = { + naersk.url = "github:nix-community/naersk/master"; + nixpkgs.url = "github:nixos/nixpkgs/26.05"; + utils.url = "github:numtide/flake-utils"; + }; + + outputs = + { + self, + nixpkgs, + utils, + naersk, + }: + utils.lib.eachDefaultSystem ( + system: + let + pkgs = import nixpkgs { inherit system; }; + naersk-lib = pkgs.callPackage naersk { }; + in + { + defaultPackage = naersk-lib.buildPackage ./.; + devShell = + with pkgs; + mkShell { + buildInputs = [ + cargo + rustc + rustfmt + pre-commit + rustPackages.clippy + rust-analyzer + ]; + RUST_SRC_PATH = rustPlatform.rustLibSrc; + }; + } + ); +} diff --git a/plans.org b/plans.org new file mode 100644 index 0000000..1fdc965 --- /dev/null +++ b/plans.org @@ -0,0 +1,10 @@ +* Minimax improvements +** DONE Alpha beta pruning +- Move ordering too + - Probably after iterative deepening +** DONE Score caching +** Move generation caching? +** DONE Iterative deepening +- Use results of previous searches for move ordering +** Profile to see what needs optimization the most +* Draws diff --git a/shell.nix b/shell.nix new file mode 100644 index 0000000..c5584b1 --- /dev/null +++ b/shell.nix @@ -0,0 +1,9 @@ +(import + (fetchTarball { + url = "https://github.com/edolstra/flake-compat/archive/99f1c2157fba4bfe6211a321fd0ee43199025dbf.tar.gz"; + sha256 = "0x2jn3vrawwv9xp15674wjz9pixwjyj3j771izayl962zziivbx2"; + }) + { + src = ./.; + } +).shellNix 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 +{ + 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 + { + 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 + { + let all: Vec = (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 = (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 = (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(&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(&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 +{ + let nums: Vec = 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::>()?; + + 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, +} + +/// 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; + 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 { + 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) -> Option { + 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, deadline: Option) -> Option<(ScoreType, Option)> { + 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 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>, + } + + 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})"); + } + } +} -- cgit v1.3.1