From 0fd43eb6d9a4bae8d4c29fd614f9cf2a362f7b7c Mon Sep 17 00:00:00 2001 From: Dylan Date: Mon, 9 Nov 2026 16:17:04 +1300 Subject: feat: Draw by threefold repetition A position coming up for the third time with the same side to move ends the game as a draw, in the TUI and in training self-play. Players now get the game's earlier boards in pick_move, and the search scores the first repetition on its path as a draw, so a side that is ahead avoids one and a side that is behind seeks one. Co-Authored-By: Claude Opus 5.5 --- CLAUDE.md | 11 +++-- README.md | 2 + plans.org | 14 ++++++ src/bench.rs | 9 ++-- src/board.rs | 118 +++++++++++++++++++++++++++++++++++++++++++++ src/claude-player.rs | 4 +- src/game.rs | 114 +++++++++++++++++++++++++++++++++++++------- src/main.rs | 9 ++-- src/neural-player.rs | 4 +- src/player.rs | 132 +++++++++++++++++++++++++++++++++++++++++++-------- src/train.rs | 53 ++++++++------------- 11 files changed, 385 insertions(+), 85 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index bf8e2ac..35305bc 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -28,25 +28,28 @@ The toolchain comes from a Nix flake (`flake.nix`, loaded via direnv `.envrc` ## Architecture - `src/board.rs` — all game logic and its unit tests (`#[cfg(test)] mod tests` at the bottom). -- `src/player.rs` — the `Player` trait. Players are polled, not blocking: the coordinator calls `update(board, turn)` before each draw, `pick_move(board, turn) -> Option` once per loop (computer players search and return `Some`), and passes clicks/keys to `handle_input(Input, board, turn) -> Option`. `highlights()` gives points for the board to highlight, `reset()` is called on both players after a revert (drop any selection and last-move comments; it is *not* called after a normal move, so players clear their own selection when they return a move), `render(area, buf)` draws the current player's panel (default: its name), and `render_last_turn(area, buf)` draws end-of-turn comments on the move it just made (default: nothing). `impl Widget for &dyn Player` makes every player a ratatui widget. Also the private-ish `MinimaxPlayer` trait: implementors supply `evaluate(board, turn)` (positive favours tigers; `turn` is the side to move) and optionally `depth()` (at most `MAX_DEPTH` = 64)/`time_limit()`/`name()`, plus `set_last_search`/`last_search` to keep a `SearchReport` (move, depth reached, score) that the blanket impl's `render_last_turn` shows; a blanket impl makes every `MinimaxPlayer` a `Player`. +- `src/player.rs` — the `Player` trait. Players are polled, not blocking: the coordinator calls `update(board, turn)` before each draw, `pick_move(board, turn, previous) -> Option` once per loop (computer players search and return `Some`; `previous` is the game's boards before this one, oldest first, for spotting repetitions), and passes clicks/keys to `handle_input(Input, board, turn) -> Option`. `highlights()` gives points for the board to highlight, `reset()` is called on both players after a revert (drop any selection and last-move comments; it is *not* called after a normal move, so players clear their own selection when they return a move), `render(area, buf)` draws the current player's panel (default: its name), and `render_last_turn(area, buf)` draws end-of-turn comments on the move it just made (default: nothing). `impl Widget for &dyn Player` makes every player a ratatui widget. Also the private-ish `MinimaxPlayer` trait: implementors supply `evaluate(board, turn)` (positive favours tigers; `turn` is the side to move) and optionally `depth()` (at most `MAX_DEPTH` = 64)/`time_limit()`/`name()`, plus `set_last_search`/`last_search` to keep a `SearchReport` (move, depth reached, score) that the blanket impl's `render_last_turn` shows; a blanket impl makes every `MinimaxPlayer` a `Player`. - Search: alpha-beta (`minimax` checks the cache, `minimax_uncached` searches) with iterative deepening in `pick_move` until half the time limit has passed. Moves are tried in this order: the cache's best move (the `hint`), then tiger jumps (`get_moves` lists them first), then killer moves, then the rest. This is done by rotating moves to the front, because a `sort_by_key` here cost more than it saved. + - Repetitions: `minimax` and `minimax_uncached` carry `path`, the game's earlier boards (from `previous`) followed by the search's own, pushed and popped around each child. A non-root position that repeats one on the path (`repetitions(path, &board) > 0`, so twofold, not the game's threefold) scores `DRAW` = 0 before the cache is consulted. The cache doesn't know the path, so an entry influenced by a repetition can be slightly off for the same board reached another way (accepted, as in chess engines). Every path holds the root, so this can't happen below depth 5 and the depth-3/4 tests against `reference` (which applies the same rule) stay exact. - `cache()` returns an optional `ScoreCache`, keyed by board, side to move and remaining depth. `minimax` passes it `board.canonical()`, so the 8 symmetric boards share one entry, and turns the entry's best move between orientations with `transform_move`/`inverse_symmetry`. This assumes `evaluate` gives symmetric boards the same score. `ClaudePlayer`'s does; a `Network` only does so approximately, since it learns symmetry from augmented data. Entries are `CacheEntry` bounds. `TranspositionTable` is the fixed-size one (`new(bits)`: `1 << bits` slots of ~24 bytes, in two-slot buckets where one slot keeps the deepest entry; `clear()` bumps a generation number instead of wiping). The `HashMap` impl is kept as a simple reference for tests. - `killers()` returns optional `Killers`: two quiet moves per remaining depth that last caused a cutoff. `pick_move` clears both the cache and the killers. - Tests compare the search with plain minimax (`reference`) for every cache kind (`CacheKind::None`/`Map`/`TinyTable`, a table small enough to collide constantly) with and without killers. -- `src/game.rs` — `GameHandler::play_game(sheep_player, tiger_player)` runs a ratatui TUI (mouse capture on) until the user quits, returning the winner if there was one. Layout: board | move history on top; below, the current player's panel (70%) | the previous player's last-turn panel (30%). Panes overlap by one cell (`Layout::spacing(-1)`) and are built with `panel()` (`MergeStrategy::Exact`) so shared borders join up. The bottom row is drawn first and keeps its titles on its bottom border, because its top border is the same line as the board's bottom border, which lists the keybinds (keep them in step with `handle_event`). History is `Vec<(Move, GameBoard)>` (board *after* each move); the side to move comes from its length's parity (sheep first). Clicking a history row calls `revert(i)`, which goes back to the board *before* move `i`. The loop only waits for input (`event::read`) when `pick_move` returns `None`. After a computer's search, `pending_action` handles any input that came in meanwhile, so quit and revert still work in computer-vs-computer games. They take effect once the current search finishes. +- `src/game.rs` — `GameHandler::play_game(sheep_player, tiger_player)` runs a ratatui TUI (mouse capture on) until the user quits, returning the `Outcome` if the game ended. `outcome()` is a win from `check_win`, else `Draw` once `repetitions(&previous(), &board()) >= REPETITION_DRAW`. Layout: board | move history on top; below, the current player's panel (70%) | the previous player's last-turn panel (30%). Panes overlap by one cell (`Layout::spacing(-1)`) and are built with `panel()` (`MergeStrategy::Exact`) so shared borders join up. The bottom row is drawn first and keeps its titles on its bottom border, because its top border is the same line as the board's bottom border, which lists the keybinds (keep them in step with `handle_event`). History is `Vec<(Move, GameBoard)>` (board *after* each move); the side to move comes from its length's parity (sheep first). Clicking a history row calls `revert(i)`, which goes back to the board *before* move `i`. The loop only waits for input (`event::read`) when `pick_move` returns `None`. After a computer's search, `pending_action` handles any input that came in meanwhile, so quit and revert still work in computer-vs-computer games. They take effect once the current search finishes. - `src/board-view.rs` (module `board_view`) — `BoardView` widget (board with rank/file labels and highlights) and `pos_at`, which maps a mouse cell to the nearest point. Both pick the scale from the area (`scale_to_fit`: the largest whole-number scale whose `size(scale)` fits), so the coordinator sizes `board_area` to exactly `size(scale)` and the two agree. Pieces grow with the scale (`reach`): `T` at 1, `[T]` at 2, a 3x3 box from 3, which `size`, `cell` and `pos_at` all allow for. The history pane is a fixed 20 columns; the board pane gets the rest. - `src/local-player.rs` (module `local_player`, pulled in via `#[path]` because of the hyphen) — `LocalPlayer`, a human using the mouse: click a point to place a sheep, or click a piece then one of its highlighted destinations. - `src/claude-player.rs` — `ClaudePlayer`, the minimax computer player: `time_limit` and `max_depth` are public fields, with a 2^20-slot `TranspositionTable` and killer moves. - `src/bench.rs` — the `bench` mode (see above). - `src/network.rs` — `Network`, a small MLP (52 inputs → 64 ReLU → 32 ReLU → tanh, positive favours tigers) with hand-written backprop and an `Adam` optimiser, all in one flat `params` Vec at the `W1`/`B1`/… offsets. Inputs are only the raw position: a bit per point for tigers and for sheep, sheep in hand / 20, and whether tigers are to move. `forward` adds up the layer-1 weight rows of the set bits rather than multiplying through the zeros. Also `Rng` (xorshift64*) and `Sample` (board, turn, target). File format (`save`/`load`): `TSNN`, then version, inputs, hidden1, hidden2 as little-endian u32s, then every param as a little-endian f32; changing the layer sizes makes old files fail to load. - `src/neural-player.rs` — `NeuralPlayer`, a `MinimaxPlayer` like `ClaudePlayer` whose `evaluate` is a `Network`. -- `src/train.rs` — self-play training. Each generation plays `games_per_generation` games of the net against itself at a fixed depth (default 3) across all cores. Moves are random for the first `random_plies`, and with chance `epsilon` after that. A game reaching `ply_cap` is a draw, since the rules have no draw. Each position is labelled with a TD(λ) target worked backwards from the result (±1, or 0) through the searched scores. A position where a random move was played is labelled with its own search score instead, which cuts the chain there. Without that cut, the sheep's random moves (which usually hang a sheep) taught the net that tigers nearly always win. Self-play still ends mostly in tiger wins, because of those random moves, so judge progress by the match against `ClaudePlayer` (`match_games` = 100). The net then trains on the last `buffer_generations` generations, each position shown in a random one of the board's 8 symmetries (`GameBoard::transformed`). With `balance_outcomes` (the default), `balanced` builds each epoch from as many positions of sheep-win games as of tiger-win games: their mean, so the epoch stays the same size. Tiger-win positions are subsampled and sheep-win ones repeated; draws are kept as they are. The output shows the mean error on tiger-win (T) and sheep-win (S) positions separately, before and after training. After that it plays matches against the previous generation and against `ClaudePlayer`, which is only a yardstick and never a training signal. Each generation is saved as `out_dir/gen-NNN.bin` and `latest.bin`, and a rerun carries on from the newest `gen-NNN.bin`. `Config::from` (`--from`) starts from any weights file instead. Generation numbers still follow on from the out dir. The Adam state and the sample buffer are not saved, so they start empty either way. -- `src/main.rs` — the command line, parsed with clap's derive API (`Cli`, `Command`, `PlayArgs`, `TrainArgs`). With no command, or `play`, it plays a game in the TUI and prints the winner; `--sheep`/`--tiger` take `human`, `claude` or a weights file (`parse_player` → `PlayerKind`, turned into a `Box` by `make_player`), and `--time` is each computer player's time limit in seconds. `neural [sheep|tiger]` is shorthand for you against a `NeuralPlayer`. `bench [depth]` runs the benchmark. `train [generations] [games] [out dir]` trains a network (use `--release`); every other `train::Config` field is a `--long-option` whose default is read from `Config::default()`, so keep `TrainArgs` and its `From` impl in step with `Config`. +- `src/train.rs` — self-play training. Each generation plays `games_per_generation` games of the net against itself at a fixed depth (default 3) across all cores. Moves are random for the first `random_plies`, and with chance `epsilon` after that. A game is a draw on a threefold repetition (`play` keeps the earlier boards and passes them to `choose`, so the search sees them too), or on reaching `ply_cap`, a backstop for long games that never repeat. Each position is labelled with a TD(λ) target worked backwards from the result (±1, or 0) through the searched scores. A position where a random move was played is labelled with its own search score instead, which cuts the chain there. Without that cut, the sheep's random moves (which usually hang a sheep) taught the net that tigers nearly always win. Self-play still ends mostly in tiger wins, because of those random moves, so judge progress by the match against `ClaudePlayer` (`match_games` = 100). The net then trains on the last `buffer_generations` generations, each position shown in a random one of the board's 8 symmetries (`GameBoard::transformed`). With `balance_outcomes` (the default), `balanced` builds each epoch from as many positions of sheep-win games as of tiger-win games: their mean, so the epoch stays the same size. Tiger-win positions are subsampled and sheep-win ones repeated; draws are kept as they are. The output shows the mean error on tiger-win (T) and sheep-win (S) positions separately, before and after training. After that it plays matches against the previous generation and against `ClaudePlayer`, which is only a yardstick and never a training signal. Each generation is saved as `out_dir/gen-NNN.bin` and `latest.bin`, and a rerun carries on from the newest `gen-NNN.bin`. `Config::from` (`--from`) starts from any weights file instead. Generation numbers still follow on from the out dir. The Adam state and the sample buffer are not saved, so they start empty either way. +- `src/main.rs` — the command line, parsed with clap's derive API (`Cli`, `Command`, `PlayArgs`, `TrainArgs`). With no command, or `play`, it plays a game in the TUI and prints the result; `--sheep`/`--tiger` take `human`, `claude` or a weights file (`parse_player` → `PlayerKind`, turned into a `Box` by `make_player`), and `--time` is each computer player's time limit in seconds. `neural [sheep|tiger]` is shorthand for you against a `NeuralPlayer`. `bench [depth]` runs the benchmark. `train [generations] [games] [out dir]` trains a network (use `--release`); every other `train::Config` field is a `--long-option` whose default is read from `Config::default()`, so keep `TrainArgs` and its `From` impl in step with `Config`. Notation (`pos_name`, `impl Display for Move` in board.rs): files `a`–`e` are x 0–4, ranks are `5 - y` (y = 0 is drawn at the top as rank 5). Moves are `sc3` (place), `sc3c2` (sheep move), `ta5b4` (tiger step), `ta5xc3` (tiger jump). 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. That check uses `has_moves(turn)`, which tests the same bitmasks as `get_moves` (shared through `sheep_steps`/`tiger_targets`) without building a list. +Draw: threefold repetition, as in chess. `repetitions(previous, board)` in board.rs counts earlier occurrences of `board` with the same side to move (every second entry of `previous` from the end). Placing and killing can't be undone, so it returns 0 while sheep are in hand and stops scanning at the first board with a different sheep count. A position is drawn when it has come up `REPETITION_DRAW` = 2 times before. `Outcome { Tiger, Sheep, Draw }` (board.rs) is shared by the coordinator and training. + ### Board representation (`GameBoard`) The board is two `u32` bitmasks, `tiger_mask` and `sheep_mask`. This encoding is non-obvious: diff --git a/README.md b/README.md index 888b961..2d20ba5 100644 --- a/README.md +++ b/README.md @@ -16,6 +16,8 @@ and diagonals run through every other point (those where x + y is even). - Sheep move first, then the sides take turns. - **Tigers win** by killing 5 sheep. **Either side wins** if the other has no legal move on its turn, so sheep win by trapping every tiger. +- **Draw:** the game is drawn when the same position, with the same side to move, comes up for the + third time, as in chess. ## Running diff --git a/plans.org b/plans.org index 8f53255..b54040b 100644 --- a/plans.org +++ b/plans.org @@ -50,6 +50,20 @@ source, so the times are only comparable with each other; moves and scores uncha - =evaluate=: tiger moves and trapped tigers from bitmasks rather than =get_moves= + 25 =get()= calls - Table lookups are now the top item (~28% of cycles), mostly cache misses into the 24 MB table * Draws +** DONE Threefold repetition +The game is drawn on the third occurrence of a position. The search scores the first repetition +on its path (game history plus search line) as 0. =bench 9= (hpet clocksource), before -> after: +| Position | Move | Score | Time ms | Repetitions | +|------------------+-------------+-----------+-------------+-------------| +| opening | sc5 | 40 | 160 -> 161 | 0 | +| tiger reply | ta1b2 | 50 | 230 -> 232 | 0 | +| mid-placement | se2 | 22 | 92 -> 97 | 0 | +| end of placement | sc4 -> sc3 | 91 -> 77 | 5 -> 7 | 19 | +| early movement | td2c3 | 212 | 40 -> 41 | 102 | +| movement | sc4d4 | 214 | 58 -> 60 | 421 | +| total | | | 584 -> 598 | | +- About 2% slower overall, from scanning the path at every node. +- The cache ignores the path, so scores near repetitions can be slightly off (graph-history interaction). * Neural player training ** DONE Tiger bias in self-play Before the fix, tigers won ~97% of self-play games and the net only reached ~15-20% against diff --git a/src/bench.rs b/src/bench.rs index ad6d63f..8ee2c00 100644 --- a/src/bench.rs +++ b/src/bench.rs @@ -23,7 +23,7 @@ fn find_position(plies: usize) -> (GameBoard, Turn) for _ in 0..plies { assert!(!board.check_win(turn), "the self-play game ended before ply {plies}"); - board.make_move_unchecked(player.pick_move(board, turn).expect("a move")); + board.make_move_unchecked(player.pick_move(board, turn, &[]).expect("a move")); turn = turn.next_turn(); } (board, turn) @@ -44,7 +44,7 @@ pub fn run(depth: usize) player.max_depth = depth; SearchStats::take(); let start = Instant::now(); - let m = player.pick_move(board, turn).expect("a move"); + let m = player.pick_move(board, turn, &[]).expect("a move"); let time = start.elapsed(); let stats = SearchStats::take(); total_time += time; @@ -65,6 +65,7 @@ fn add(total: &mut SearchStats, s: &SearchStats) total.nodes += s.nodes; total.leaves += s.leaves; total.terminal += s.terminal; + total.repetitions += s.repetitions; total.cache_probes += s.cache_probes; total.cache_hits += s.cache_hits; total.cache_returns += s.cache_returns; @@ -81,8 +82,8 @@ fn print_stats(s: &SearchStats, time: Duration) return; } let pct = |a: u64, b: u64| if b == 0 { 0.0 } else { 100.0 * a as f64 / b as f64 }; - println!(" {} nodes ({:.2} M/s), {} leaves, {} terminal, {:.2} move gens/node", - s.nodes, s.nodes as f64 / time.as_secs_f64() / 1e6, s.leaves, s.terminal, + println!(" {} nodes ({:.2} M/s), {} leaves, {} terminal, {} repetitions, {:.2} move gens/node", + s.nodes, s.nodes as f64 / time.as_secs_f64() / 1e6, s.leaves, s.terminal, s.repetitions, s.move_gens as f64 / s.nodes.max(1) as f64); println!(" cache: {} probes, {:.1}% hit, {:.1}% of hits settle the score, {} overwrites; cutoffs: {}, {:.1}% on the first move", s.cache_probes, pct(s.cache_hits, s.cache_probes), pct(s.cache_returns, s.cache_hits), s.cache_overwrites, diff --git a/src/board.rs b/src/board.rs index 087ac0e..8957111 100644 --- a/src/board.rs +++ b/src/board.rs @@ -45,6 +45,54 @@ impl Turn } } +/// 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 { @@ -1366,6 +1414,76 @@ mod tests 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 + { + 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] diff --git a/src/claude-player.rs b/src/claude-player.rs index c25c5e1..2b7004c 100644 --- a/src/claude-player.rs +++ b/src/claude-player.rs @@ -92,12 +92,12 @@ mod tests fn pick_move_reports_its_search() { let mut player = ClaudePlayer::new(Duration::from_millis(50)); - let m = player.pick_move(GameBoard::default(), Turn::Tiger).unwrap(); + let m = player.pick_move(GameBoard::default(), Turn::Tiger, &[]).unwrap(); let report = player.last_search.expect("a report"); assert_eq!(report.mv, m); assert!(report.depth >= 1); assert_eq!(report.score, player.minimax(GameBoard::default(), Turn::Tiger, report.depth, - f32::NEG_INFINITY, f32::INFINITY, None).unwrap()); + f32::NEG_INFINITY, f32::INFINITY, None, &mut Vec::new()).unwrap()); player.reset(); assert_eq!(player.last_search, None); diff --git a/src/game.rs b/src/game.rs index 5aef809..716446d 100644 --- a/src/game.rs +++ b/src/game.rs @@ -10,7 +10,7 @@ use ratatui::{ DefaultTerminal, Frame, }; -use crate::{board::{GameBoard, Move, Turn}, board_view::{pos_at, BoardView}, player::{Input, Player}}; +use crate::{board::{repetitions, GameBoard, Move, Outcome, Turn, REPETITION_DRAW}, board_view::{pos_at, BoardView}, player::{Input, Player}}; /// Runs a game in the terminal: draws the board, the move history and the current player's panel, /// and passes mouse clicks on the board to the player whose turn it is. @@ -64,11 +64,23 @@ impl GameHandler if self.history.len().is_multiple_of(2) { Turn::Sheep } else { Turn::Tiger } } - /// The side that has won, if the game is over. - pub fn winner(&self) -> Option + /// The boards before the current one, oldest first. + pub fn previous(&self) -> Vec { + std::iter::once(self.start).chain(self.history.iter().map(|&(_, board)| board)) + .take(self.history.len()).collect() + } + + /// How the game ended, if it is over: a win, or a draw once a position comes up a third time. + pub fn outcome(&self) -> Option + { + let (board, turn) = (self.board(), self.turn()); // check_win runs before `turn`'s move, so whoever moved last has won. - self.board().check_win(self.turn()).then(|| self.turn().next_turn()) + if board.check_win(turn) + { + return Some(Outcome::win(turn.next_turn())); + } + (repetitions(&self.previous(), &board) >= REPETITION_DRAW).then_some(Outcome::Draw) } /// Play `m` for the side to move. Panics if it is illegal. @@ -86,8 +98,8 @@ impl GameHandler } /// Play in the terminal with `p1` as the sheep and `p2` as the tigers, until someone wins and - /// the user quits. Returns the winner, or None if the user quit before the game was won. - pub fn play_game(&mut self, p1: &mut dyn Player, p2: &mut dyn Player) -> io::Result> + /// the user quits. Returns how it ended, or None if the user quit before the game was over. + pub fn play_game(&mut self, p1: &mut dyn Player, p2: &mut dyn Player) -> io::Result> { let mut terminal = ratatui::init(); let result = execute!(io::stdout(), EnableMouseCapture) @@ -97,19 +109,19 @@ impl GameHandler result } - fn run(&mut self, terminal: &mut DefaultTerminal, mut players: [&mut dyn Player; 2]) -> io::Result> + fn run(&mut self, terminal: &mut DefaultTerminal, mut players: [&mut dyn Player; 2]) -> io::Result> { let idx = |turn: Turn| match turn { Turn::Sheep => 0, Turn::Tiger => 1 }; loop { let (board, turn) = (self.board(), self.turn()); - let over = self.winner().is_some(); + let over = self.outcome().is_some(); players[idx(turn)].update(board, turn); // Drawn before `pick_move`, so a computer's "thinking" panel is on screen while it searches terminal.draw(|frame| self.draw(frame, &players))?; let player = &mut *players[idx(turn)]; - let action = match (!over).then(|| player.pick_move(board, turn)).flatten() + let action = match (!over).then(|| player.pick_move(board, turn, &self.previous())).flatten() { // Input that came in during the search goes first, so a quit or a revert isn't // lost when both players are computers and nothing ever waits for input @@ -120,7 +132,7 @@ impl GameHandler match action { Action::None => (), - Action::Quit => return Ok(self.winner()), + Action::Quit => return Ok(self.outcome()), Action::Play(m) => self.play(m), Action::Revert(i) => { @@ -188,20 +200,26 @@ impl GameHandler let [board_pane, history_pane] = Layout::horizontal([Constraint::Min(0), Constraint::Length(20)]).spacing(-1).areas(top); let [current_pane, last_pane] = Layout::horizontal([Constraint::Percentage(70), Constraint::Fill(1)]).spacing(-1).areas(bottom); - let winner = self.winner(); + let outcome = self.outcome(); let turn = self.turn(); let player = &*players[match turn { Turn::Sheep => 0, Turn::Tiger => 1 }]; // The bottom row is drawn first, so the top row's bottom titles (keybinds, revert hint) // land on the shared border line over it. Its own titles go on its bottom border. // Player output, or the result once the game is over - match winner + match outcome { - Some(w) => + Some(o) => { let block = panel().title_bottom(" Game over "); + let result = match o + { + Outcome::Tiger => format!("{} win!", side_name(Turn::Tiger)), + Outcome::Sheep => format!("{} win!", side_name(Turn::Sheep)), + Outcome::Draw => "Draw by repetition!".to_string(), + }; let text = vec![ - Line::styled(format!("{} win!", side_name(w)), Style::new().add_modifier(Modifier::BOLD)), + Line::styled(result, Style::new().add_modifier(Modifier::BOLD)), Line::from("Click a move to revert to it, or press q to quit."), ]; frame.render_widget(Paragraph::new(text).block(block), current_pane); @@ -247,7 +265,7 @@ impl GameHandler let view = BoardView { board: self.board(), - highlights: if winner.is_none() { player.highlights() } else { Default::default() }, + highlights: if outcome.is_none() { player.highlights() } else { Default::default() }, last_move: self.history.last().map(|&(m, _)| m), }; frame.render_widget(&view, padded); @@ -318,7 +336,7 @@ mod tests } use ratatui::{backend::TestBackend, crossterm::event::{MouseEvent, KeyEvent}, Terminal}; - use crate::{claude_player::ClaudePlayer, local_player::LocalPlayer}; + use crate::{board::PieceType, claude_player::ClaudePlayer, local_player::LocalPlayer}; fn draw(game: &mut GameHandler, players: &[&mut dyn Player; 2]) -> Terminal { @@ -394,7 +412,7 @@ mod tests let mut sheep = LocalPlayer::default(); let mut tiger = ClaudePlayer::new(std::time::Duration::from_millis(50)); game.play(Move::PlaceSheep { pos: (2, 2) }); - let m = tiger.pick_move(game.board(), game.turn()).unwrap(); + let m = tiger.pick_move(game.board(), game.turn(), &[]).unwrap(); game.play(m); let mut terminal = Terminal::new(TestBackend::new(100, 24)).unwrap(); @@ -419,6 +437,66 @@ mod tests #[test] fn no_winner_at_the_start() { - assert_eq!(GameHandler::default().winner(), None); + assert_eq!(GameHandler::default().outcome(), None); + } + + /// Movement phase with 16 sheep: tigers in the corners, and sheep filling rows 1 to 4 except + /// c4 and c1, with a sheep at b4 free to step to c4 and the tiger at a5 free to step to b5. + fn movement_game() -> GameHandler + { + let mut start = GameBoard::EMPTY; + for pos in [(0, 0), (4, 0), (0, 4), (4, 4)] + { + start.set(pos, PieceType::Tiger); + } + for y in 1..5 + { + for x in 0..5 + { + if matches!(start.get((x, y)), PieceType::Empty) && (x, y) != (2, 1) && (x, y) != (2, 4) + { + start.set((x, y), PieceType::Sheep); + } + } + } + assert_eq!((start.sheep_count(), start.sheep_left()), (16, 0)); + GameHandler { start, ..Default::default() } + } + + /// The sheep at b4 and the tiger at a5 step out and back. + const SHUFFLE: [Move; 4] = [ + Move::MoveSheep { from: (1, 1), to: (2, 1) }, + Move::MoveTiger { from: (0, 0), to: (1, 0) }, + Move::MoveSheep { from: (2, 1), to: (1, 1) }, + Move::MoveTiger { from: (1, 0), to: (0, 0) }, + ]; + + #[test] + fn third_repetition_is_a_draw() + { + let mut game = movement_game(); + for (i, &m) in SHUFFLE.iter().cycle().take(8).enumerate() + { + assert_eq!(game.outcome(), None, "before move {i}"); + game.play(m); + } + // The start position, for the third time + assert_eq!(game.board(), game.start); + assert_eq!(game.outcome(), Some(Outcome::Draw)); + assert_eq!(game.previous().len(), 8); + + game.revert(7); + assert_eq!(game.outcome(), None); + } + + #[test] + fn game_over_panel_shows_a_draw() + { + let mut game = movement_game(); + SHUFFLE.iter().cycle().take(8).for_each(|&m| game.play(m)); + let (mut sheep, mut tiger) = (LocalPlayer::default(), LocalPlayer::default()); + let terminal = draw(&mut game, &[&mut sheep, &mut tiger]); + let screen = format!("{:?}", terminal.backend().buffer()); + assert!(screen.contains("Draw by repetition!"), "{screen}"); } } diff --git a/src/main.rs b/src/main.rs index b6a4ad0..5a3c798 100644 --- a/src/main.rs +++ b/src/main.rs @@ -2,7 +2,7 @@ use std::{path::PathBuf, time::Duration}; use clap::{Args, Parser, Subcommand, ValueEnum}; -use crate::{claude_player::ClaudePlayer, game::GameHandler, local_player::LocalPlayer, network::Network, neural_player::NeuralPlayer, player::Player}; +use crate::{board::Outcome, claude_player::ClaudePlayer, game::GameHandler, local_player::LocalPlayer, network::Network, neural_player::NeuralPlayer, player::Player}; mod board; mod player; @@ -218,9 +218,12 @@ fn play(args: PlayArgs) -> std::io::Result<()> let mut sheep = make_player(args.sheep, time_limit)?; let mut tiger = make_player(args.tiger, time_limit)?; let mut game = GameHandler::default(); - if let Some(winner) = game.play_game(sheep.as_mut(), tiger.as_mut())? + match game.play_game(sheep.as_mut(), tiger.as_mut())? { - println!("{winner:?} wins!"); + Some(Outcome::Tiger) => println!("Tigers win!"), + Some(Outcome::Sheep) => println!("Sheep win!"), + Some(Outcome::Draw) => println!("Draw by repetition."), + None => (), } Ok(()) } diff --git a/src/neural-player.rs b/src/neural-player.rs index 3a9c4a0..f7e54c7 100644 --- a/src/neural-player.rs +++ b/src/neural-player.rs @@ -59,10 +59,10 @@ mod tests let mut player = NeuralPlayer::new(Network::random(2), Duration::from_secs(3600), 12); player.max_depth = 3; let board = GameBoard::default(); - let m = player.pick_move(board, Turn::Sheep).unwrap(); + let m = player.pick_move(board, Turn::Sheep, &[]).unwrap(); assert_eq!(board.check_move(m), Ok(())); let report = player.last_search.expect("a report"); assert_eq!((report.mv, report.depth), (m, 3)); - assert_eq!(report.score, player.minimax(board, Turn::Sheep, 3, f32::NEG_INFINITY, f32::INFINITY, None).unwrap()); + assert_eq!(report.score, player.minimax(board, Turn::Sheep, 3, f32::NEG_INFINITY, f32::INFINITY, None, &mut Vec::new()).unwrap()); } } diff --git a/src/player.rs b/src/player.rs index 0c58a58..1766d24 100644 --- a/src/player.rs +++ b/src/player.rs @@ -2,7 +2,7 @@ use std::{collections::HashMap, time::{Duration, Instant}}; use ratatui::{buffer::Buffer, crossterm::event::KeyEvent, layout::Rect, widgets::{Paragraph, Widget, Wrap}}; -use crate::board::{inverse_symmetry, is_jump, transform_move, GameBoard, Move, Pos, Turn}; +use crate::board::{inverse_symmetry, is_jump, repetitions, transform_move, GameBoard, Move, Pos, Turn}; /// Input the game coordinator passes on to the player whose turn it is. #[derive(Clone, Copy, Debug, PartialEq, Eq)] @@ -31,8 +31,9 @@ pub trait Player fn update(&mut self, _board: GameBoard, _turn: Turn) {} /// Computer players search here and return Some. Interactive players return None and - /// wait for `handle_input`. - fn pick_move(&mut self, _board: GameBoard, _turn: Turn) -> Option { None } + /// wait for `handle_input`. `previous` is the game's boards before this one, oldest first, + /// for spotting repetitions. + fn pick_move(&mut self, _board: GameBoard, _turn: Turn, _previous: &[GameBoard]) -> Option { None } /// A click on a board point, or a key press, while it's this player's turn. fn handle_input(&mut self, _input: Input, _board: GameBoard, _turn: Turn) -> Option { None } @@ -267,6 +268,8 @@ pub struct SearchStats pub leaves: u64, /// Positions where `check_win` ended the search. pub terminal: u64, + /// Positions scored as a draw because they repeat an earlier one. + pub repetitions: u64, pub cache_probes: u64, pub cache_hits: u64, /// Cache hits whose bounds settled the score without searching. @@ -313,11 +316,23 @@ impl SearchStats pub trait MinimaxPlayer { const WIN: f32 = f32::INFINITY; + /// The score of a position that repeats one on `path`. + const DRAW: f32 = 0.0; /// Scores outside `alpha..beta` are only bounds: at most `alpha`, or at least `beta`. + /// `path` is the boards before this one, in the game and then in the search, oldest first. /// Returns None if `deadline` passed before the search finished. + #[allow(clippy::too_many_arguments)] fn minimax(&mut self, board: GameBoard, turn: Turn, depth: usize, - mut alpha: ScoreType, mut beta: ScoreType, deadline: Option) -> Option { + mut alpha: ScoreType, mut beta: ScoreType, deadline: Option, path: &mut Vec) -> Option { + // A side that can repeat a position once can repeat it until the game is drawn, so the + // first repetition already scores as a draw. The cache doesn't know the path, so an entry + // that came from a repetition can be slightly wrong for the same board reached another way. + if repetitions(path, &board) > 0 + { + count!(repetitions); + return Some(Self::DRAW); + } // Symmetric boards are equally good, so they share an entry, under the canonical board. // Entries' best moves are stored as played on that board, and turned back for this one. let (canon, sym) = if self.cache().is_some() { board.canonical() } else { (board, 0) }; @@ -346,7 +361,7 @@ pub trait MinimaxPlayer { hint = self.cache().and_then(|c| { count!(cache_probes); c.lookup(&canon, turn, depth - 1) }).and_then(|e| e.best).map(back); } - let (score, best) = self.minimax_uncached(board, turn, depth, alpha, beta, hint, deadline)?; + let (score, best) = self.minimax_uncached(board, turn, depth, alpha, beta, hint, deadline, path)?; if let Some(c) = self.cache() { let best = best.map(|m| transform_move(m, sym)); @@ -376,9 +391,10 @@ pub trait MinimaxPlayer /// The score and the move that gave it (None at a leaf), trying `hint` first if it is legal. /// Returns None if `deadline` passed before the search finished. + #[allow(clippy::too_many_arguments)] fn minimax_uncached(&mut self, board: GameBoard, turn: Turn, depth: usize, mut alpha: ScoreType, mut beta: ScoreType, - hint: Option, deadline: Option) -> Option<(ScoreType, Option)> { + hint: Option, deadline: Option, path: &mut Vec) -> Option<(ScoreType, Option)> { count!(nodes); if board.check_win(turn) { @@ -423,7 +439,10 @@ pub trait MinimaxPlayer let mut best: Option<(ScoreType, Move)> = None; for (_i, m) in moves.into_iter().enumerate() { - let score = self.minimax(board.after_move_unchecked(m), next, depth - 1, alpha, beta, deadline)?; + path.push(board); + let score = self.minimax(board.after_move_unchecked(m), next, depth - 1, alpha, beta, deadline, path); + path.pop(); + let score = score?; let better = match best { None => true, @@ -500,7 +519,7 @@ 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) -> Option { + fn pick_move(&mut self, board: GameBoard, turn: Turn, previous: &[GameBoard]) -> Option { let start = Instant::now(); let time_limit = self.time_limit(); let deadline = start + time_limit; @@ -513,6 +532,7 @@ impl Player for P { k.clear(); } + let mut path = previous.to_vec(); let mut best = None; let mut report = None; for depth in 1..=self.depth().max(1) @@ -520,7 +540,7 @@ impl Player for P // 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) + let Some((score, m)) = self.minimax_uncached(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, best, dl, &mut path) else { break; @@ -650,6 +670,16 @@ mod tests /// Plain minimax with no pruning or cache, to check the real search against. fn reference(player: &mut TestPlayer, board: GameBoard, turn: Turn, depth: usize) -> ScoreType { + reference_from(player, board, turn, depth, &mut Vec::new()) + } + + /// `reference` with `path` the boards before this one, like `minimax`'s. + fn reference_from(player: &mut TestPlayer, board: GameBoard, turn: Turn, depth: usize, path: &mut Vec) -> ScoreType + { + if repetitions(path, &board) > 0 + { + return TestPlayer::DRAW; + } if board.check_win(turn) { return match turn { Turn::Tiger => -TestPlayer::WIN, Turn::Sheep => TestPlayer::WIN }; @@ -658,12 +688,15 @@ mod tests { return player.evaluate(&board, turn); } - let scores = board.get_moves(turn).into_iter() - .map(|m| reference(player, board.after_move_unchecked(m), turn.next_turn(), depth - 1)); + path.push(board); + let scores: Vec = board.get_moves(turn).into_iter() + .map(|m| reference_from(player, board.after_move_unchecked(m), turn.next_turn(), depth - 1, path)) + .collect(); + path.pop(); match turn { - Turn::Tiger => scores.fold(f32::NEG_INFINITY, f32::max), - Turn::Sheep => scores.fold(f32::INFINITY, f32::min), + Turn::Tiger => scores.into_iter().fold(f32::NEG_INFINITY, f32::max), + Turn::Sheep => scores.into_iter().fold(f32::INFINITY, f32::min), } } @@ -703,7 +736,7 @@ mod tests { let mut player = TestPlayer::new(depth, CacheKind::None); let expected = reference(&mut player, board, turn, depth); - let score = player.minimax(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, None).unwrap(); + let score = player.minimax(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, None, &mut Vec::new()).unwrap(); assert_eq!(score, expected, "depth {depth}, {turn:?} to move"); } } @@ -722,7 +755,7 @@ mod tests { let mut player = TestPlayer::new(depth, kind).with_killers(killers); let expected = reference(&mut player, board, turn, depth); - let score = player.minimax(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, None).unwrap(); + let score = player.minimax(board, turn, depth, f32::NEG_INFINITY, f32::INFINITY, None, &mut Vec::new()).unwrap(); assert_eq!(score, expected, "depth {depth}, {turn:?} to move, {kind:?}, killers {killers}"); } } @@ -742,7 +775,7 @@ mod tests for kind in CACHED { let mut player = TestPlayer::new(3, kind).with_killers(true); - let (score, _) = player.minimax_uncached(board, turn, 3, f32::NEG_INFINITY, f32::INFINITY, Some(hint), None).unwrap(); + let (score, _) = player.minimax_uncached(board, turn, 3, f32::NEG_INFINITY, f32::INFINITY, Some(hint), None, &mut Vec::new()).unwrap(); assert_eq!(score, expected, "{turn:?} to move, hint {hint:?}, {kind:?}"); } } @@ -756,7 +789,7 @@ mod tests { let mut player = TestPlayer::new(3, kind); let past = Instant::now(); - assert_eq!(player.minimax(GameBoard::default(), Turn::Sheep, 3, f32::NEG_INFINITY, f32::INFINITY, Some(past)), None); + assert_eq!(player.minimax(GameBoard::default(), Turn::Sheep, 3, f32::NEG_INFINITY, f32::INFINITY, Some(past), &mut Vec::new()), None); // The root gives up before searching any move, so its entry is the only one there could be assert_eq!(player.cache.unwrap().lookup(&GameBoard::default(), Turn::Sheep, 3), None, "{kind:?}"); } @@ -769,7 +802,7 @@ mod tests player.time_limit = Duration::from_millis(50); let board = GameBoard::default(); let start = Instant::now(); - let m = player.pick_move(board, Turn::Sheep).unwrap(); + let m = player.pick_move(board, Turn::Sheep, &[]).unwrap(); assert!(start.elapsed() < Duration::from_millis(500), "took {:?}", start.elapsed()); assert_eq!(board.check_move(m), Ok(())); } @@ -785,7 +818,7 @@ mod tests { let mut player = TestPlayer::new(4, kind).with_killers(killers); let best = reference(&mut player, board, turn, 4); - let m = player.pick_move(board, turn).unwrap(); + let m = player.pick_move(board, turn, &[]).unwrap(); let score = reference(&mut player, board.after_move_unchecked(m), turn.next_turn(), 3); assert_eq!(score, best, "{turn:?} picked {m:?} ({kind:?}, killers {killers})"); } @@ -793,6 +826,65 @@ mod tests } } + /// A movement-phase position with `turn` to move and at least one sheep dead, so the + /// evaluation is well above the draw score, and at least two moves. + fn sheep_down_position(turn: Turn) -> (GameBoard, Turn) + { + (41..80).flat_map(|plies| (1..20).filter_map(move |seed| position(plies, seed))) + .find(|&(board, t)| t == turn && board.sheep_left() == 0 && board.sheep_count() < 20 + && board.get_moves(t).len() >= 2) + .expect("a position with a sheep down") + } + + /// A history in which the board after `m` came up before, with the same side to move: + /// that board, then `board`, then that board again. + fn history_repeating(board: GameBoard, m: Move) -> Vec + { + let after = board.after_move_unchecked(m); + vec![after, board, after] + } + + #[test] + fn search_scores_a_repeated_position_as_a_draw() + { + let (board, turn) = sheep_down_position(Turn::Tiger); + let m = board.get_moves(turn)[0]; + let mut path = history_repeating(board, m); + path.push(board); + let mut player = TestPlayer::new(3, CacheKind::None); + assert_eq!(player.minimax(board.after_move_unchecked(m), turn.next_turn(), 3, + f32::NEG_INFINITY, f32::INFINITY, None, &mut path), Some(TestPlayer::DRAW)); + assert_eq!(path.len(), 4, "the search leaves the path as it found it"); + } + + #[test] + fn tiger_ahead_avoids_a_repetition() + { + let (board, turn) = sheep_down_position(Turn::Tiger); + for kind in ALL_CACHES + { + let m = TestPlayer::new(3, kind).pick_move(board, turn, &[]).unwrap(); + assert!(reference(&mut TestPlayer::new(3, kind), board.after_move_unchecked(m), turn.next_turn(), 2) > TestPlayer::DRAW); + let previous = history_repeating(board, m); + let again = TestPlayer::new(3, kind).pick_move(board, turn, &previous).unwrap(); + assert_ne!(again, m, "{kind:?}"); + } + } + + #[test] + fn sheep_behind_takes_a_repetition() + { + let (board, turn) = sheep_down_position(Turn::Sheep); + for kind in ALL_CACHES + { + let best = TestPlayer::new(3, kind).pick_move(board, turn, &[]).unwrap(); + assert!(reference(&mut TestPlayer::new(3, kind), board.after_move_unchecked(best), turn.next_turn(), 2) > TestPlayer::DRAW); + let m = *board.get_moves(turn).iter().find(|&&m| m != best).unwrap(); + let previous = history_repeating(board, m); + assert_eq!(TestPlayer::new(3, kind).pick_move(board, turn, &previous), Some(m), "{kind:?}"); + } + } + #[test] fn tiger_takes_the_winning_kill() { @@ -819,7 +911,7 @@ mod tests for kind in ALL_CACHES { - let m = TestPlayer::new(3, kind).pick_move(board, Turn::Tiger).unwrap(); + let m = TestPlayer::new(3, kind).pick_move(board, Turn::Tiger, &[]).unwrap(); assert!(board.after_move_unchecked(m).check_win(Turn::Sheep), "picked {m:?} ({kind:?})"); } } diff --git a/src/train.rs b/src/train.rs index e6ed822..1e68080 100644 --- a/src/train.rs +++ b/src/train.rs @@ -1,6 +1,6 @@ use std::{collections::VecDeque, fs, path::{Path, PathBuf}, sync::atomic::{AtomicUsize, Ordering}, time::{Duration, Instant}}; -use crate::{board::{GameBoard, Move, Turn, SYMMETRIES}, claude_player::ClaudePlayer, network::{Adam, Network, Rng, Sample}, neural_player::NeuralPlayer, player::{MinimaxPlayer, Player}}; +use crate::{board::{repetitions, GameBoard, Move, Outcome, Turn, REPETITION_DRAW, SYMMETRIES}, claude_player::ClaudePlayer, network::{Adam, Network, Rng, Sample}, neural_player::NeuralPlayer, player::{MinimaxPlayer, Player}}; /// Settings for `run`. #[derive(Clone, Debug)] @@ -58,25 +58,6 @@ impl Default for Config } } -#[derive(Clone, Copy, Debug, PartialEq, Eq)] -pub enum Outcome -{ - Tiger, - Sheep, - Draw, -} - -impl Outcome -{ - const ALL: [Outcome; 3] = [Outcome::Tiger, Outcome::Sheep, Outcome::Draw]; - - /// +1 for a tiger win, -1 for a sheep win, matching the sign of the scores. - fn value(self) -> f32 - { - match self { Outcome::Tiger => 1.0, Outcome::Sheep => -1.0, Outcome::Draw => 0.0 } - } -} - /// A position from a game, with the searching player's score for it (clamped to -1..1). #[derive(Clone, Copy, Debug)] struct Ply @@ -88,24 +69,29 @@ struct Ply random: bool, } -/// Plays one game from the start. `choose` gives the move and score for a position; for the -/// first `random_plies` plies, and with chance `epsilon` after, a random move is played instead -/// (the position keeps `choose`'s score, and is marked `random` unless the two moves are the same). -fn play(mut choose: impl FnMut(GameBoard, Turn) -> (Move, f32), ply_cap: usize, random_plies: usize, epsilon: f32, rng: &mut Rng) +/// Plays one game from the start. `choose` gives the move and score for a position, given the +/// boards before it; for the first `random_plies` plies, and with chance `epsilon` after, a random +/// move is played instead (the position keeps `choose`'s score, and is marked `random` unless the +/// two moves are the same). A threefold repetition, or reaching `ply_cap`, is a draw. +fn play(mut choose: impl FnMut(GameBoard, Turn, &[GameBoard]) -> (Move, f32), ply_cap: usize, random_plies: usize, epsilon: f32, rng: &mut Rng) -> (Outcome, Vec) { let mut board = GameBoard::default(); let mut turn = Turn::Sheep; let mut plies = Vec::new(); + let mut previous = Vec::new(); while plies.len() < ply_cap { if board.check_win(turn) { // The side that just moved has won - let winner = match turn { Turn::Sheep => Outcome::Tiger, Turn::Tiger => Outcome::Sheep }; - return (winner, plies); + return (Outcome::win(turn.next_turn()), plies); + } + if repetitions(&previous, &board) >= REPETITION_DRAW + { + return (Outcome::Draw, plies); } - let (searched, score) = choose(board, turn); + let (searched, score) = choose(board, turn, &previous); let mut m = searched; if plies.len() < random_plies || rng.next_f32() < epsilon { @@ -113,6 +99,7 @@ fn play(mut choose: impl FnMut(GameBoard, Turn) -> (Move, f32), ply_cap: usize, m = moves[rng.below(moves.len())]; } plies.push(Ply { board, turn, score: score.clamp(-1.0, 1.0), random: m != searched }); + previous.push(board); board.make_move_unchecked(m); turn = turn.next_turn(); } @@ -180,9 +167,9 @@ fn claude(depth: usize) -> ClaudePlayer } /// The move a minimax player picks, and the score it gave it. -fn search(player: &mut (impl MinimaxPlayer + Player), board: GameBoard, turn: Turn) -> (Move, f32) +fn search(player: &mut (impl MinimaxPlayer + Player), board: GameBoard, turn: Turn, previous: &[GameBoard]) -> (Move, f32) { - let m = player.pick_move(board, turn).expect("the game is not over, so there is a move"); + let m = player.pick_move(board, turn, previous).expect("the game is not over, so there is a move"); (m, player.last_search().map_or(0.0, |r| r.score)) } @@ -191,7 +178,7 @@ fn self_play(net: &Network, cfg: &Config, seed: u64) -> (Outcome, Vec) { let mut player = neural(net, cfg.depth); let mut rng = Rng::new(seed); - let (outcome, plies) = play(|b, t| search(&mut player, b, t), cfg.ply_cap, cfg.random_plies, cfg.epsilon, &mut rng); + let (outcome, plies) = play(|b, t, p| search(&mut player, b, t, p), cfg.ply_cap, cfg.random_plies, cfg.epsilon, &mut rng); let targets = td_targets(&plies, outcome, cfg.lambda); let samples = plies.iter().zip(targets).map(|(p, target)| Sample { board: p.board, turn: p.turn, target }).collect(); (outcome, samples) @@ -208,7 +195,7 @@ fn match_score(net: &Network, opponent: impl Fn() -> let mut them = opponent(); let neural_side = if i % 2 == 0 { Turn::Sheep } else { Turn::Tiger }; let mut rng = Rng::new(seed ^ (i / 2) as u64); - let (outcome, _) = play(|b, t| if t == neural_side { search(&mut me, b, t) } else { search(&mut them, b, t) }, + let (outcome, _) = play(|b, t, p| if t == neural_side { search(&mut me, b, t, p) } else { search(&mut them, b, t, p) }, cfg.ply_cap, 4, 0.0, &mut rng); match (outcome, neural_side) { @@ -389,9 +376,11 @@ mod tests assert!(w[0].board.get_moves(w[0].turn).iter().any(|&m| w[0].board.after_move_unchecked(m) == w[1].board)); } assert!(samples.iter().all(|s| (-1.0..=1.0).contains(&s.target))); + // A draw is the ply cap, or a position coming up a third time (the last time isn't a sample) + let repeated = samples.iter().any(|s| samples.iter().filter(|o| o.board == s.board && o.turn == s.turn).count() >= 2); if outcome == Outcome::Draw { - assert_eq!(samples.len(), cfg.ply_cap); + assert!(samples.len() == cfg.ply_cap || repeated); } } -- cgit v1.3.1