use std::{fmt::Display};
pub 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, Debug, 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,
}
}
}
/// How a game ended.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Outcome
{
Tiger,
Sheep,
Draw,
}
impl Outcome
{
pub const ALL: [Outcome; 3] = [Outcome::Tiger, Outcome::Sheep, Outcome::Draw];
/// The win for `turn`'s side.
pub fn win(turn: Turn) -> Self
{
match turn { Turn::Tiger => Outcome::Tiger, Turn::Sheep => Outcome::Sheep }
}
/// +1 for a tiger win, -1 for a sheep win, matching the sign of the scores.
pub fn value(self) -> f32
{
match self { Outcome::Tiger => 1.0, Outcome::Sheep => -1.0, Outcome::Draw => 0.0 }
}
}
/// A position seen this many times before, with the same side to move, is a draw:
/// the third occurrence, as in chess.
pub const REPETITION_DRAW: usize = 2;
/// How many times `board` came up before with the same side to move. `previous` is the boards
/// before it, oldest first, so the last one had the other side to move.
///
/// Placing a sheep and killing one can't be undone, so the scan stops at the first board with a
/// different number of sheep, and nothing repeats while sheep are still in hand.
pub fn repetitions(previous: &[GameBoard], board: &GameBoard) -> usize
{
if board.sheep_left() > 0
{
return 0;
}
let sheep = board.sheep_count();
previous.iter().rev().skip(1).step_by(2)
.take_while(|b| b.sheep_left() == 0 && b.sheep_count() == sheep)
.filter(|&b| b == board)
.count()
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum Move
{
PlaceSheep{pos: Pos},
MoveSheep{from: Pos, to: Pos},
MoveTiger{from: Pos, to: Pos}
}
/// A point in chess-style notation: files `a`–`e` for x 0–4, ranks `5`–`1` for y 0–4
/// (so y = 0, drawn at the top, is rank 5).
pub fn pos_name((x, y): Pos) -> String
{
format!("{}{}", (b'a' + x) as char, 5 - y)
}
/// True for a tiger move of two points, which always jumps (and kills) a sheep.
pub 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,
}
}
/// Chess-like notation: `s<pos>` places a sheep, `s<from><to>` moves one,
/// `t<from><to>` moves a tiger and `t<from>x<to>` is a tiger jump.
impl Display for Move
{
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result
{
match *self
{
Move::PlaceSheep { pos } => write!(f, "s{}", pos_name(pos)),
Move::MoveSheep { from, to } => write!(f, "s{}{}", pos_name(from), pos_name(to)),
Move::MoveTiger { from, to } =>
{
let x = if is_jump(*self) { "x" } else { "" };
write!(f, "t{}{x}{}", pos_name(from), pos_name(to))
}
}
}
}
/// 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)
}
/// The board's 8 symmetries (rotations and reflections) as a point map: bit 2 of `sym` swaps x and
/// y, then bit 0 mirrors x and bit 1 mirrors y. They all keep the board lines, since x + y keeps
/// its parity, so a transformed position is just as legal and just as good for either side.
pub const SYMMETRIES: usize = 8;
pub const fn transform_pos((x, y): Pos, sym: usize) -> Pos
{
let (x, y) = if sym & 4 != 0 { (y, x) } else { (x, y) };
let x = if sym & 1 != 0 { 4 - x } else { x };
let y = if sym & 2 != 0 { 4 - y } else { y };
(x, y)
}
/// For each symmetry, where each bit index goes.
const SYMMETRY_MAPS: [[u8; 25]; SYMMETRIES] = {
let mut maps = [[0; 25]; SYMMETRIES];
let mut sym = 0;
while sym < SYMMETRIES
{
let mut idx = 0;
while idx < 25
{
let (x, y) = transform_pos(((idx % 5) as u8, (idx / 5) as u8), sym);
maps[sym][idx] = x + y * 5;
idx += 1;
}
sym += 1;
}
maps
};
/// For each symmetry and row, where each of the 32 possible sets of points in that row go, so a
/// whole mask transforms in 5 lookups. The search does this for every cache probe.
const ROW_MAPS: [[[u32; 32]; 5]; SYMMETRIES] = {
let mut maps = [[[0; 32]; 5]; SYMMETRIES];
let mut sym = 0;
while sym < SYMMETRIES
{
let mut row = 0;
while row < 5
{
let mut bits = 0;
while bits < 32
{
let mut x = 0;
while x < 5
{
if bits & 1 << x != 0
{
maps[sym][row][bits] |= 1 << SYMMETRY_MAPS[sym][x + row * 5];
}
x += 1;
}
bits += 1;
}
row += 1;
}
sym += 1;
}
maps
};
#[inline(always)]
fn transform_mask(mask: u32, sym: usize) -> u32
{
let rows = &ROW_MAPS[sym];
rows[0][(mask & 31) as usize] | rows[1][(mask >> 5 & 31) as usize] | rows[2][(mask >> 10 & 31) as usize]
| rows[3][(mask >> 15 & 31) as usize] | rows[4][(mask >> 20 & 31) as usize]
}
/// The symmetry that undoes `sym`. The mirrors undo themselves, but with the swap of x and y
/// first, undoing them means swapping which axis is mirrored.
pub const fn inverse_symmetry(sym: usize) -> usize
{
if sym & 4 == 0 { sym } else { 4 | (sym & 1) << 1 | (sym >> 1 & 1) }
}
/// `mv` as played on the board transformed by `sym`.
pub fn transform_move(mv: Move, sym: usize) -> Move
{
match mv
{
Move::PlaceSheep { pos } => Move::PlaceSheep { pos: transform_pos(pos, sym) },
Move::MoveSheep { from, to } => Move::MoveSheep { from: transform_pos(from, sym), to: transform_pos(to, sym) },
Move::MoveTiger { from, to } => Move::MoveTiger { from: transform_pos(from, sym), to: transform_pos(to, sym) },
}
}
impl GameBoard
{
/// No pieces on the board and none in hand.
pub const EMPTY: GameBoard = GameBoard { sheep_mask: 0, tiger_mask: 0 };
fn bit_idx((x, y): Pos) -> usize
{
if x > 4 || y > 4
{
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 }
/// The whole board, sheep in hand included, as one number: different boards give different keys.
pub fn key(&self) -> u64 { (self.sheep_mask as u64) << 32 | self.tiger_mask as u64 }
pub fn sheep_count(&self) -> u32 { (self.sheep_mask & BOARD_MASK).count_ones() }
/// The points holding a tiger, as bits `x + y*5`.
pub fn tiger_points(&self) -> u32 { self.tiger_mask }
/// The points holding a sheep, as bits `x + y*5`.
pub fn sheep_points(&self) -> u32 { self.sheep_mask & BOARD_MASK }
/// The board under symmetry `sym` (see `transform_pos`), with the same sheep in hand.
pub fn transformed(&self, sym: usize) -> GameBoard
{
GameBoard
{
tiger_mask: transform_mask(self.tiger_mask, sym),
sheep_mask: transform_mask(self.sheep_points(), sym) | (self.sheep_mask & !BOARD_MASK),
}
}
/// One board standing for all 8 symmetric ones (the one whose `key` is smallest), and the
/// symmetry that takes `self` to it. Symmetric boards are equally good, so the search caches
/// them under one entry.
pub fn canonical(&self) -> (GameBoard, usize)
{
let mut best = (*self, 0);
for sym in 1..SYMMETRIES
{
let t = self.transformed(sym);
if t.key() < best.0.key()
{
best = (t, sym);
}
}
best
}
/// Empty board points.
fn empty(&self) -> u32
{
!(self.tiger_mask | self.sheep_mask) & BOARD_MASK
}
/// For each direction, the points a sheep can step to in that direction.
fn sheep_steps(&self) -> [u32; 8]
{
let sheep = self.sheep_mask & BOARD_MASK;
let empty = self.empty();
let mut steps = [0; 8];
for d in 0..8
{
steps[d] = shift(sheep & STEP_SOURCES[d], DELTAS[d]) & empty;
}
steps
}
/// For each direction, the points a tiger can step to and the points it can jump to.
fn tiger_targets(&self) -> ([u32; 8], [u32; 8])
{
let tigers = self.tiger_mask;
let sheep = self.sheep_mask & BOARD_MASK;
let empty = self.empty();
let mut steps = [0; 8];
let mut jumps = [0; 8];
for d in 0..8
{
steps[d] = shift(tigers & STEP_SOURCES[d], DELTAS[d]) & empty;
let over = shift(tigers & JUMP_SOURCES[d], DELTAS[d]) & sheep;
jumps[d] = shift(over, DELTAS[d]) & empty;
}
(steps, jumps)
}
/// True if `turn` has a legal move: the same as `!get_moves(turn).is_empty()`, without building the list.
pub fn has_moves(&self, turn: Turn) -> bool
{
match turn
{
Turn::Sheep if self.sheep_left() > 0 => self.empty() != 0,
Turn::Sheep => self.sheep_steps().iter().any(|&m| m != 0),
Turn::Tiger =>
{
let (steps, jumps) = self.tiger_targets();
steps.iter().chain(jumps.iter()).fold(0, |acc, m| acc | m) != 0
}
}
}
/// All legal moves for `turn`. Sheep place while any are in hand, then move.
/// Tiger jumps come before steps, since the search tries kills first.
pub fn get_moves(&self, turn: Turn) -> Vec<Move>
{
crate::player::count!(move_gens);
match turn
{
Turn::Sheep if self.sheep_left() > 0 =>
{
let empty = self.empty();
let mut moves = Vec::with_capacity(empty.count_ones() as usize);
moves.extend(indices(empty).map(|idx| Move::PlaceSheep { pos: pos_of(idx) }));
moves
}
Turn::Sheep =>
{
let steps = self.sheep_steps();
let mut moves = Vec::with_capacity(steps.iter().map(|m| m.count_ones() as usize).sum());
for d in 0..8
{
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 (steps, jumps) = self.tiger_targets();
let count = steps.iter().chain(jumps.iter()).map(|m| m.count_ones() as usize).sum();
let mut moves = Vec::with_capacity(count);
for d in 0..8
{
for to in indices(jumps[d])
{
let from = (to as isize - 2 * DELTAS[d]) as usize;
moves.push(Move::MoveTiger { from: pos_of(from), to: pos_of(to) });
}
}
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) });
}
}
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
{
self.sheep_count() + self.sheep_left() <= 15 || !self.has_moves(turn)
}
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) }
// --- notation ---
#[test]
fn pos_name_uses_files_and_ranks()
{
assert_eq!(pos_name((0, 4)), "a1");
assert_eq!(pos_name((0, 0)), "a5");
assert_eq!(pos_name((4, 4)), "e1");
assert_eq!(pos_name((2, 2)), "c3");
}
#[test]
fn move_display_is_chess_like()
{
assert_eq!(Move::PlaceSheep { pos: (2, 2) }.to_string(), "sc3");
assert_eq!(Move::MoveSheep { from: (2, 2), to: (2, 3) }.to_string(), "sc3c2");
assert_eq!(Move::MoveTiger { from: (0, 0), to: (1, 1) }.to_string(), "ta5b4");
assert_eq!(Move::MoveTiger { from: (0, 0), to: (2, 2) }.to_string(), "ta5xc3");
}
// --- 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);
for turn in [Turn::Tiger, Turn::Sheep]
{
assert_eq!(board.has_moves(turn), !board.get_moves(turn).is_empty(), "{turn:?} on {board:?}");
}
}
}
#[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));
}
// --- repetitions ---
/// Movement phase: a tiger at a5 and sheep at e1 and d1, none in hand.
fn shuffle_board() -> GameBoard
{
let mut board = GameBoard::EMPTY;
board.set((0, 0), PieceType::Tiger);
board.set((4, 4), PieceType::Sheep);
board.set((3, 4), PieceType::Sheep);
board
}
/// The boards from `shuffle_board` with the tiger stepping a5-b5-a5 and a sheep e1-e2-e1, `cycles` times.
fn shuffle(cycles: usize) -> Vec<GameBoard>
{
let moves = [
Move::MoveTiger { from: (0, 0), to: (1, 0) },
Move::MoveSheep { from: (4, 4), to: (4, 3) },
Move::MoveTiger { from: (1, 0), to: (0, 0) },
Move::MoveSheep { from: (4, 3), to: (4, 4) },
];
let mut boards = vec![shuffle_board()];
for m in moves.iter().cycle().take(4 * cycles)
{
let next = boards.last().unwrap().after_move_unchecked(*m);
boards.push(next);
}
boards
}
#[test]
fn repetitions_count_earlier_occurrences()
{
let boards = shuffle(2);
assert_eq!(repetitions(&[], &boards[0]), 0);
assert_eq!(repetitions(&boards[..4], &boards[4]), 1);
assert_eq!(repetitions(&boards[..8], &boards[8]), 2);
// After the tiger's move: b5 came up once before, with sheep to move
assert_eq!(repetitions(&boards[..5], &boards[5]), 1);
}
#[test]
fn repetitions_need_the_same_side_to_move()
{
let board = shuffle_board();
let other = shuffle(1)[1];
// The same board, but with the other side to move
assert_eq!(repetitions(&[board], &board), 0);
assert_eq!(repetitions(&[board, other, board], &board), 0);
assert_eq!(repetitions(&[board, other], &board), 1);
}
#[test]
fn repetitions_stop_at_a_kill()
{
let boards = shuffle(1);
let mut killed = boards[2];
killed.set((3, 4), PieceType::Empty);
// An identical board from before a kill doesn't count
let previous = [boards[0], boards[1], killed, boards[3]];
assert_eq!(repetitions(&previous, &boards[4]), 0);
}
#[test]
fn nothing_repeats_with_sheep_in_hand()
{
let board = GameBoard::default();
assert_eq!(repetitions(&[board, board], &board), 0);
}
// --- symmetries ---
#[test]
fn symmetries_are_distinct_bijections()
{
for sym in 0..SYMMETRIES
{
let mut seen = 0u32;
for idx in 0..25
{
seen |= 1 << SYMMETRY_MAPS[sym][idx];
}
assert_eq!(seen, BOARD_MASK, "symmetry {sym} is not a bijection");
for other in 0..sym
{
assert_ne!(SYMMETRY_MAPS[sym], SYMMETRY_MAPS[other], "symmetries {sym} and {other}");
}
}
assert_eq!(transform_pos((1, 0), 0), (1, 0));
assert_eq!(GameBoard::default().transformed(5), GameBoard::default());
}
#[test]
fn inverse_symmetry_undoes_it()
{
for sym in 0..SYMMETRIES
{
for idx in 0..25
{
let pos = pos_of(idx);
assert_eq!(transform_pos(transform_pos(pos, sym), inverse_symmetry(sym)), pos, "symmetry {sym}");
}
}
}
#[test]
fn canonical_is_shared_by_symmetric_boards()
{
let mut seed: u64 = 0x94D049BB133111EB;
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..60
{
if board.check_win(turn) { break; }
let (canon, sym) = board.canonical();
assert_eq!(board.transformed(sym), canon);
for s in 0..SYMMETRIES
{
let t = board.transformed(s);
assert_eq!(t.canonical().0, canon, "symmetry {s} of {board:?}");
// The fast transform agrees with moving each point
let slow = |mask: u32| indices(mask).fold(0, |m, idx| m | 1 << SYMMETRY_MAPS[s][idx]);
assert_eq!((t.tiger_points(), t.sheep_points()), (slow(board.tiger_points()), slow(board.sheep_points())));
}
let moves = board.get_moves(turn);
board.make_move_unchecked(moves[(next() % moves.len() as u64) as usize]);
turn = turn.next_turn();
}
}
#[test]
fn transformed_boards_have_transformed_moves()
{
let mut seed: u64 = 0xD1B54A32D192ED03;
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..80
{
if board.check_win(turn) { break; }
for sym in 0..SYMMETRIES
{
let t = board.transformed(sym);
assert_eq!(t.sheep_left(), board.sheep_left());
assert_eq!(t.sheep_count(), board.sheep_count());
for side in [Turn::Tiger, Turn::Sheep]
{
let mut expected: Vec<Move> = board.get_moves(side).into_iter().map(|m| transform_move(m, sym)).collect();
expected.sort();
let mut moves = t.get_moves(side);
moves.sort();
assert_eq!(moves, expected, "symmetry {sym}, {side:?} on {board:?}");
assert_eq!(t.check_win(side), board.check_win(side));
}
}
let moves = board.get_moves(turn);
board.make_move_unchecked(moves[(next() % moves.len() as u64) as usize]);
turn = turn.next_turn();
}
}
}
