From f17308e3c132ee18cc4cbd458329958c99a712ed Mon Sep 17 00:00:00 2001 From: Dylan Date: Mon, 9 Nov 2026 23:32:43 +1300 Subject: docs: Add a docs folder on building, the code's structure, the search and training Covers building and dependencies, the architecture and game loop, the board representation, the Player and MinimaxPlayer traits, the minimax search, the network and self-play training, benchmarking, and how to add a player. Co-Authored-By: Claude Opus 5.5 --- docs/README.md | 27 +++++ docs/adding-a-player.md | 214 +++++++++++++++++++++++++++++++++++++++ docs/architecture.md | 133 +++++++++++++++++++++++++ docs/benchmarking.md | 79 +++++++++++++++ docs/board.md | 163 ++++++++++++++++++++++++++++++ docs/building.md | 114 +++++++++++++++++++++ docs/players.md | 170 +++++++++++++++++++++++++++++++ docs/search.md | 204 +++++++++++++++++++++++++++++++++++++ docs/training.md | 260 ++++++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 1364 insertions(+) create mode 100644 docs/README.md create mode 100644 docs/adding-a-player.md create mode 100644 docs/architecture.md create mode 100644 docs/benchmarking.md create mode 100644 docs/board.md create mode 100644 docs/building.md create mode 100644 docs/players.md create mode 100644 docs/search.md create mode 100644 docs/training.md (limited to 'docs') diff --git a/docs/README.md b/docs/README.md new file mode 100644 index 0000000..9d5a60c --- /dev/null +++ b/docs/README.md @@ -0,0 +1,27 @@ +# Tigers and Sheep documentation + +These pages explain how the game is built and how its computer players think. The top-level +[README](../README.md) covers the rules and how to play; start here when you want to change the code. + +| Page | What it covers | +|------|----------------| +| [Building](building.md) | Toolchain, dependencies and what each is for, Cargo profiles and features, the Nix flake, CI | +| [Architecture](architecture.md) | The modules, how a game runs from `main` to the TUI loop, and how the pieces talk to each other | +| [The board](board.md) | The bitboard representation, move generation, the rules as implemented, symmetries and repetitions | +| [Players](players.md) | The `Player` and `MinimaxPlayer` traits, and the players that implement them | +| [The minimax search](search.md) | Alpha-beta, iterative deepening, the transposition table, move ordering, repetitions | +| [The neural network and training](training.md) | The network, backprop and Adam, and the self-play training loop with TD(λ) targets | +| [Benchmarking and profiling](benchmarking.md) | The `bench` command, search counters, `perf`/`samply`, and pitfalls when timing | +| [Adding a player](adding-a-player.md) | Step by step: a simple player, a minimax player, and wiring either into the command line | + +## Conventions used throughout + +- **Scores favour tigers.** Every score in the code, from `evaluate` to the network's output, is + positive when it's good for the tigers and negative when it's good for the sheep. Tigers maximise, + sheep minimise. +- **Coordinates.** A point is `Pos = (x, y)`, with `x` and `y` in `0..5`. `y = 0` is drawn at the + top. In notation, files `a`–`e` are `x` 0–4 and ranks are `5 - y`, so `(0, 0)` is `a5`. +- **Move notation.** `sc3` places a sheep on c3, `sc3c2` moves a sheep, `ta5b4` is a tiger step and + `ta5xc3` a tiger jump (which kills the sheep on b4). +- **Turns.** Sheep move first. `Turn` is the side *about to move*, and most functions take it + alongside the board, since the same board can come up with either side to move. diff --git a/docs/adding-a-player.md b/docs/adding-a-player.md new file mode 100644 index 0000000..915831a --- /dev/null +++ b/docs/adding-a-player.md @@ -0,0 +1,214 @@ +# Adding a player + +There are two kinds of player to add: + +- **A minimax player** — a new evaluation function on top of the existing search. This is the + easiest and usually what you want for a new computer opponent. Implement `MinimaxPlayer`. +- **Any other player** — a different algorithm (Monte Carlo tree search, a random mover, a player + over the network, a keyboard-driven human…). Implement `Player` directly. + +Then, either way, make it selectable on the command line. + +Read [Players](players.md) first for what each trait method is for. + +## Option A: a minimax player + +Say we want a player that only counts dead sheep and tiger mobility. Create +`src/greedy-player.rs`: + +```rust +use std::time::Duration; + +use crate::{board::{GameBoard, Turn}, player::{Killers, MinimaxPlayer, ScoreCache, SearchReport, TranspositionTable}}; + +/// A computer player that searches like `ClaudePlayer` but only counts dead sheep and tiger moves. +pub struct GreedyPlayer +{ + pub time_limit: Duration, + cache: TranspositionTable, + killers: Killers, + last_search: Option, +} + +impl GreedyPlayer +{ + pub fn new(time_limit: Duration) -> Self + { + Self { time_limit, cache: TranspositionTable::new(20), killers: Killers::default(), last_search: None } + } +} + +impl MinimaxPlayer for GreedyPlayer +{ + /// Positive favours tigers, whichever side is to move. + fn evaluate(&mut self, board: &GameBoard, _turn: Turn) -> f32 + { + let dead = 20 - board.sheep_count() - board.sheep_left(); + 100.0 * dead as f32 + board.get_moves(Turn::Tiger).len() as f32 + } + + fn name(&self) -> String { "Greedy".to_string() } + + fn time_limit(&self) -> Duration { self.time_limit } + + fn cache(&mut self) -> Option<&mut dyn ScoreCache> { Some(&mut self.cache) } + + fn killers(&mut self) -> Option<&mut Killers> { Some(&mut self.killers) } + + fn set_last_search(&mut self, report: Option) { self.last_search = report; } + + fn last_search(&self) -> Option { self.last_search } +} +``` + +That's all: the blanket `impl Player for P` gives it `pick_move` with iterative +deepening, the "Thinking…" panel and the last-turn report. **Don't also write `impl Player for +GreedyPlayer`**; it would conflict with the blanket impl. + +Things to get right in `evaluate`: + +- **Sign.** Positive is good for the tigers, negative good for the sheep, regardless of `turn`. +- **Finite values.** `±f32::INFINITY` means a won game to the search; an evaluation that returns it + would be read as a forced win and stop iterative deepening. +- **Symmetry.** With a cache, the search shares one entry between the 8 symmetric boards, so + `evaluate` should give them the same score. Anything built from counts (pieces, moves, jumps) is + symmetric automatically; something like "sheep on the left half" is not. +- **Speed.** `evaluate` runs at every leaf, which is most of the nodes. `get_moves` allocates a + `Vec`; the bitmask accessors (`tiger_points`, `sheep_points`, `sheep_count`) are much cheaper. + +`cache`, `killers` and the `last_search` pair are optional. Leave them out and the player still +works, just searching more slowly and with an empty last-turn panel. + +## Option B: any other player + +Implement `Player`. A computer player does its work in `pick_move` and returns `Some`. Here is a +player that moves at random, using the crate's own `Rng` from `network.rs` +(`src/random-player.rs`): + +```rust +use crate::{board::{GameBoard, Move, Turn}, network::Rng, player::Player}; + +/// Plays a uniformly random legal move. +pub struct RandomPlayer +{ + rng: Rng, +} + +impl RandomPlayer +{ + pub fn new(seed: u64) -> Self + { + Self { rng: Rng::new(seed) } + } +} + +impl Player for RandomPlayer +{ + fn name(&self) -> String { "Random".to_string() } + + fn pick_move(&mut self, board: GameBoard, turn: Turn, _previous: &[GameBoard]) -> Option + { + // pick_move is only called while the game is on, so there is always a move + let moves = board.get_moves(turn); + Some(moves[self.rng.below(moves.len())]) + } +} +``` + +Things to keep in mind: + +- **Return only legal moves.** The coordinator `unwrap`s `make_move`, so an illegal move panics. + Pick from `board.get_moves(turn)`, or check with `board.check_move(mv)`. +- **Don't block forever.** The coordinator can't redraw or react to `q` while `pick_move` runs. Input + that arrives meanwhile is handled as soon as it returns. Keep a time limit. +- **Repetitions.** `previous` holds every earlier board in the game. `board::repetitions(previous, + &next)` says how often a position came up before; `REPETITION_DRAW` (2) earlier occurrences make a + draw. +- **Interactive players** return `None` from `pick_move` and produce their move from + `handle_input`, as `LocalPlayer` does. Use `update` to remember the position for `render`, + `highlights` to show a selection, and clear your own selection when you return a move. `reset` + is called after the user reverts, so drop any selection there too. +- **Panels.** Override `render` for the panel shown on your turn and `render_last_turn` for comments + on your last move, shown during the opponent's turn. Both draw with ratatui into the given `area` + of `buf`, e.g. `Paragraph::new(text).render(area, buf)` (with `ratatui::widgets::Widget` in scope). + +## Wiring it into the command line + +All in [`src/main.rs`](../src/main.rs). + +**1. Declare the module.** File names with a hyphen need `#[path]`: + +```rust +#[path = "greedy-player.rs"] +mod greedy_player; +``` + +and import the type: `use crate::greedy_player::GreedyPlayer;` (or add it to the existing +`use crate::{…}` list). + +**2. Add a `PlayerKind` variant:** + +```rust +enum PlayerKind +{ + Human, + Claude, + Greedy, + Neural(PathBuf), +} +``` + +**3. Parse its name** in `parse_player`, before the file-path case, and mention it in the error: + +```rust +"greedy" => Ok(PlayerKind::Greedy), +… +_ => Err(format!("expected `human`, `claude`, `greedy` or a weights file, but `{s}` is none of these")), +``` + +**4. Construct it** in `make_player`: + +```rust +PlayerKind::Greedy => Box::new(GreedyPlayer::new(time_limit)), +``` + +**5. Update the help text** on the `sheep` and `tiger` fields of `PlayArgs` (their doc comments are +what `--help` shows), and the player list in the top-level `README.md`. + +Then: + +```bash +cargo run --release -- -S human -T greedy +cargo run --release -- -S greedy -T claude --time 1 +``` + +If the new type is only used from `main.rs` through `make_player`, everything is reachable and there +are no dead-code warnings. A constructor or field that nothing uses yet will warn; that's a sign to +either use it or remove it. + +## Testing it + +Put tests in a `#[cfg(test)] mod tests` at the bottom of the player's file, as the other players do. +Useful checks: + +- `pick_move` from a few positions returns a move with `board.check_move(m) == Ok(())`. +- For a minimax player, `last_search()` reports the move it returned. +- A player with a clear preference picks the obvious move: `player.rs` has a position where one + tiger jump wins the game (`tiger_takes_the_winning_kill`) that is easy to copy. + +To see how it plays, play it against `ClaudePlayer` in the TUI with both sides computer-controlled: + +```bash +cargo run --release -- -S greedy -T claude +``` + +For a proper strength comparison over many games, `train.rs`'s `match_score` and `play` show how to +run games without the TUI: `play` takes a closure that returns `(move, score)` for a position, so +any `Player` can be plugged in. + +## Using it in training + +`train.rs` plays its matches against `ClaudePlayer` (`claude(depth)`). To measure the network +against your player instead, add a constructor like `claude` for it and pass it to `match_score`, +which accepts any `MinimaxPlayer + Player`. Keep the match opponents out of the training data: +they are a yardstick, and the network is meant to learn from self-play alone. diff --git a/docs/architecture.md b/docs/architecture.md new file mode 100644 index 0000000..dc0fc0c --- /dev/null +++ b/docs/architecture.md @@ -0,0 +1,133 @@ +# Architecture + +The crate is a single binary, `tigers-and-sheep-rs`. It has three modes: play a game in the +terminal, benchmark the search, or train a neural network. + +## Modules + +```text +main.rs ─── command line (clap) ──┬── game.rs ─────── GameHandler: the TUI and game loop + │ └── board-view.rs BoardView widget, pos_at + ├── bench.rs ────── fixed-depth search timings + └── train.rs ────── self-play training + +player.rs ───── Player trait, MinimaxPlayer trait + search, ScoreCache, TranspositionTable, Killers + ├── local-player.rs LocalPlayer a human with a mouse + ├── claude-player.rs ClaudePlayer minimax + hand-written evaluation + └── neural-player.rs NeuralPlayer minimax + network evaluation +network.rs ──── Network (MLP), Adam, Rng, Sample +board.rs ────── GameBoard, Move, Turn, Outcome, rules, move generation, symmetries, repetitions +``` + +| File | Module | Contents | +|------|--------|----------| +| [`src/main.rs`](../src/main.rs) | crate root | `Cli` and its subcommands, `parse_player`, `make_player`, `play` | +| [`src/board.rs`](../src/board.rs) | `board` | All the game logic and its unit tests. See [The board](board.md). | +| [`src/player.rs`](../src/player.rs) | `player` | The `Player` trait, and the `MinimaxPlayer` trait with the whole search. See [Players](players.md) and [The minimax search](search.md). | +| [`src/game.rs`](../src/game.rs) | `game` | `GameHandler`, which owns the move history and runs the TUI loop | +| [`src/board-view.rs`](../src/board-view.rs) | `board_view` | `BoardView`, the board widget, and `pos_at`, which maps a mouse click back to a point | +| [`src/local-player.rs`](../src/local-player.rs) | `local_player` | `LocalPlayer` | +| [`src/claude-player.rs`](../src/claude-player.rs) | `claude_player` | `ClaudePlayer` | +| [`src/neural-player.rs`](../src/neural-player.rs) | `neural_player` | `NeuralPlayer` | +| [`src/network.rs`](../src/network.rs) | `network` | The neural network, its optimiser and file format. See [Training](training.md). | +| [`src/train.rs`](../src/train.rs) | `train` | Self-play training (`Config`, `run`) | +| [`src/bench.rs`](../src/bench.rs) | `bench` | The `bench` command. See [Benchmarking](benchmarking.md). | + +Files with a hyphen in their name are pulled in with `#[path = "local-player.rs"] mod local_player;` +in `main.rs`, since a module name can't contain a hyphen. + +## The command line + +`main.rs` parses arguments with clap's derive API: + +- `Cli` has an optional subcommand and, flattened in, the `PlayArgs`, so `tigers-and-sheep-rs -S human` + works without writing `play`. `args_conflicts_with_subcommands` stops the two being mixed. +- `Command::Play(PlayArgs)` — `--sheep`/`-S` and `--tiger`/`-T` each take a `PlayerKind`, parsed + by `parse_player`: `human`, `claude`, or the path of an existing file (taken as network weights). + `--time`/`-t` is each computer player's time limit in seconds (default 2). +- `Command::Bench { depth }` — runs `bench::run(depth)`. +- `Command::Train(TrainArgs)` — every field of `train::Config` is an argument, and each default is + read from `Config::default()`, so the defaults live in one place. `impl From for Config` + converts them. Keep the two in step when adding a setting. + +`make_player` turns a `PlayerKind` into a `Box`, and `play` hands the two boxes to +`GameHandler::play_game` and prints the result. + +## How a game runs + +`GameHandler` ([`game.rs`](../src/game.rs)) holds the start board and the history, a +`Vec<(Move, GameBoard)>` with the board *after* each move. Everything else is derived from it: + +- `board()` is the last history entry's board, or the start board. +- `turn()` comes from the history's length: even means sheep to move. +- `previous()` is every board before the current one, oldest first, used to detect repetitions. +- `outcome()` is a win if `board.check_win(turn)` (the side that just moved has won), otherwise a + draw if the position has come up `REPETITION_DRAW` = 2 times before, otherwise `None`. + +`play_game` enters the alternate screen with `ratatui::init()`, turns on mouse capture, runs the +loop, and restores the terminal however the loop ends. Each pass of the loop: + +1. Calls `update(board, turn)` on the player to move, so it can show the position in its panel. +2. Draws the whole screen. This happens *before* asking for a move, so a computer player's + "Thinking…" panel is on screen while it searches. +3. If the game isn't over, calls `pick_move(board, turn, &previous)`. + - A computer player searches and returns `Some(move)`. Before playing it, `pending_action` + handles any key presses and clicks that arrived during the search, without blocking. A quit or + a revert there wins over the move. This is what makes quitting work in a computer-against-computer + game, where nothing else ever waits for input. + - A human player returns `None`, and the loop blocks on `event::read()` for the next event. +4. Handles the resulting `Action`: + - **Quit** (`q`, `Esc`, `Ctrl+C`): returns the outcome. + - **Play(move)**: `make_move` (which panics on an illegal move, so players must only return legal ones) and push onto the history. + - **Revert(i)**: a click on history row `i` truncates the history to before move `i`, then calls + `reset()` on both players so they drop selections and stale comments. + - A click on the board goes to the player to move as `Input::Click(pos)`; other keys go as + `Input::Key`. If `handle_input` returns a move, it is played. + +Once the game is over the loop keeps running, showing the result, until the user quits or reverts. + +### Screen layout + +```text +┌ Board ──────────────────────────────┬ Moves ───────────┐ +│ │ 1. sc3 [↶] │ +│ (BoardView, scaled) │ 2. ta5b4 [↶] │ +│ │ … │ +├ click: select / move · q, Esc: quit ┼──── ↶ reverts ───┤ +│ current player's panel (70%) │ last turn (30%) │ +└───────────── Sheep: You ────────────┴ Last turn: … ────┘ +``` + +- Neighbouring panes overlap by one cell (`Layout::spacing(-1)`) and are built with `panel()`, + which uses `MergeStrategy::Exact`, so shared borders join into `┬ ┴ ┼`. +- 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. If you change the keys in + `handle_event`, change that title too. +- The current player's panel is drawn by `Player::render`; the other panel is the previous mover's + `Player::render_last_turn` (for minimax players: the move, depth reached and score). +- The history pane is a fixed 20 columns and scrolls to keep the newest move visible. Sheep moves + are white, tiger moves yellow. +- `BoardView` picks the largest whole-number scale that fits (`scale_to_fit`), and the coordinator + sizes `board_area` to exactly `BoardView::size(scale)`. `pos_at` uses the same calculation to map + a click back to the nearest point, so drawing and clicking always agree. Pieces grow with the + scale: `T` at scale 1, `[T]` at 2, a 3×3 box from 3 on. + +## Data flow between the pieces + +```text + GameHandler ──update/pick_move/handle_input──▶ dyn Player + │ │ + │ make_move, check_win, repetitions │ get_moves, after_move_unchecked, + ▼ ▼ check_win, evaluate + GameBoard ◀──────────────────────────────── MinimaxPlayer search + │ + ScoreCache / Killers / Network +``` + +The board is `Copy` and 8 bytes, so it is passed by value everywhere and nothing shares mutable +state. Players never see the `GameHandler`; they only get the board, the side to move and the +earlier boards. + +Training (`train.rs`) doesn't use `GameHandler` at all. It has its own small game loop, `play`, +that calls players directly, so it runs without a terminal and in parallel. `bench.rs` likewise +calls `pick_move` directly. diff --git a/docs/benchmarking.md b/docs/benchmarking.md new file mode 100644 index 0000000..9d85ddf --- /dev/null +++ b/docs/benchmarking.md @@ -0,0 +1,79 @@ +# Benchmarking and profiling + +## The `bench` command + +```bash +cargo run --profile profiling -- bench [depth] # default depth 6 +``` + +[`src/bench.rs`](../src/bench.rs) searches six fixed positions, one from each phase of the game, to a +fixed depth without the TUI, and prints the move, score and time for each, plus a total: + +| Label | Position after | +|-------|----------------| +| opening | 0 plies | +| tiger reply | 1 ply | +| mid-placement | 20 plies | +| end of placement | 38 plies | +| early movement | 45 plies | +| movement | 60 plies | + +The positions come from `ClaudePlayer` playing itself to depth 4, which is deterministic and plays +much more like a real game than random moves. Each search uses a fresh `ClaudePlayer` with +`max_depth` set to the requested depth and an effectively infinite time limit, so every run does +exactly the same work and timings can be compared. Depth 9 takes well under a second in total. + +**The rule for optimisations:** a change that only makes the search faster must leave every move +and every score unchanged. If they change, the change altered what the search computes, not just +how fast. + +## Search counters + +```bash +cargo run --profile profiling --features search-stats -- bench 9 +``` + +With the `search-stats` feature, each position also prints: + +- nodes searched and nodes per second, leaves, terminal positions, repetitions, move generations per node; +- cache probes, hit rate, the share of hits that settled the score without searching, and overwrites; +- cutoffs, and the share of them on the first move tried, which measures move ordering. + +The counters are thread-local `SearchStats` fields bumped by the `count!` macro (defined in +`player.rs`, also used in `board.rs`). Without the feature `count!` expands to nothing. Counting +slows the search a little, so compare times only between builds with the same features. + +## Profiling + +The `profiling` profile is `release` with debug info. The dev shell includes `perf` and `samply`. + +```bash +cargo build --profile profiling +perf record -e cycles:u -m 16 --call-graph dwarf target/profiling/tigers-and-sheep-rs bench 9 +perf report +``` + +As a non-root user `perf record` needs `-m 16` (a small ring buffer) with `--call-graph dwarf`, +otherwise mmap fails against the `perf_event_mlock_kb` limit. + +Or, for a flame graph in the browser: + +```bash +samply record target/profiling/tigers-and-sheep-rs bench 9 +``` + +## Check the clock source first + +```bash +cat /sys/devices/system/clocksource/clocksource0/current_clocksource +``` + +The search reads the clock (`Instant::now()`) once per interior node to check its deadline. With the +`tsc` clock source that's a cheap instruction. If the kernel has fallen back to `hpet`, as has +happened on the development machine, every read becomes a system call and the search runs at nearly +half speed. Only compare timings taken on the same clock source. + +## History + +[`plans.org`](../plans.org) records each optimisation with its before and after timings, node counts +and cutoff rates, and the next candidates. Add to it when you make a change that affects speed. diff --git a/docs/board.md b/docs/board.md new file mode 100644 index 0000000..8719d2b --- /dev/null +++ b/docs/board.md @@ -0,0 +1,163 @@ +# The board + +Everything about the rules lives in [`src/board.rs`](../src/board.rs), along with its unit tests at +the bottom of the file. + +## Types + +| Type | Meaning | +|------|---------| +| `Pos = (u8, u8)` | A point `(x, y)`, both in `0..5`. Out-of-range points panic in `bit_idx`. | +| `PieceType` | `Tiger`, `Sheep` or `Empty`; what `get(pos)` returns | +| `Turn` | `Tiger` or `Sheep`, the side about to move. `next_turn()` flips it. | +| `Move` | `PlaceSheep { pos }`, `MoveSheep { from, to }` or `MoveTiger { from, to }`. A tiger jump is a `MoveTiger` of two points; `is_jump` tells them apart. | +| `MoveError` | Why `check_move` rejected a move, with a human-readable `Display` | +| `Outcome` | `Tiger`, `Sheep` or `Draw`; `value()` is +1, -1 or 0, matching the sign of scores | +| `GameBoard` | The position, including the sheep still in hand. `Copy`, 8 bytes. | + +## The bitboard + +A `GameBoard` is two `u32`s: + +```text +tiger_mask: [ unused (7 bits) ][ 25 board bits ] +sheep_mask: [ sheep in hand ][ 25 board bits ] + bits 25..32 bits 0..25 +``` + +Point `(x, y)` is bit `x + 5*y`, so `(0, 0)` (a5, top left) is bit 0 and `(4, 4)` (e1) is bit 24: + +```text + a b c d e +5 0 1 2 3 4 +4 5 6 7 8 9 +3 10 11 12 13 14 +2 15 16 17 18 19 +1 20 21 22 23 24 +``` + +The high 7 bits of `sheep_mask`, from `SHEEP_COUNT_SHIFT` = 25, aren't points: they hold the +number of sheep still in hand, 20 at the start. `sheep_left()` reads them, and placing a sheep sets +its board bit and subtracts `ONE_SHEEP` (`1 << 25`) in one go. Killing a sheep only clears its board +bit; the in-hand count is unplaced sheep, not living ones. So the number of dead sheep is +`20 - sheep_count() - sheep_left()`. + +The default board has tigers on bits 0, 4, 20 and 24 (the corners) and 20 sheep in hand. +`GameBoard::EMPTY` has nothing at all and is used as the "no entry" board in the transposition table. + +Useful accessors: + +- `tiger_points()`, `sheep_points()` — the 25 board bits alone. +- `sheep_count()` — sheep on the board (`popcount` of the board bits). +- `key()` — the whole board as one `u64` (`sheep_mask << 32 | tiger_mask`). Different boards give + different keys, so it serves as a hash key and for ordering. + +## Lines + +Every point has horizontal and vertical lines. Diagonals only run through points where `x + y` is +even (the corners, the centre and so on), as on a Bagh-Chal board: + +```text +5 T───·───·───·───T + │ ╲ │ ╱ │ ╲ │ ╱ │ +4 ·───·───·───·───· + │ ╱ │ ╲ │ ╱ │ ╲ │ +3 ·───·───·───·───· + … +``` + +`on_line(from, to, dist)` checks this for a single move: orthogonal and `dist` away, or diagonal, +`dist` away and starting from an even point. A diagonal step keeps `x + y`'s parity, so a diagonal +never leaves the even points. + +## Move generation with bitmasks + +`get_moves(turn)` doesn't loop over pieces. It works on all pieces of a side at once, one direction +at a time. + +- `DIRS` lists the 8 directions as `(dx, dy)`: 4 orthogonal, then 4 diagonal. `DELTAS` is the + matching change in bit index, `dx + 5*dy`. +- `STEP_SOURCES[d]` is a mask, built at compile time by `line_sources`, of the points from which + one step in direction `d` stays on the board *and* follows a line. `JUMP_SOURCES[d]` is the same + for two steps. +- `shift(mask, delta)` moves every point in a mask by `delta` bits. Shifting can wrap a point from + the end of one row to the start of the next, but the source masks exclude every point for which + that would happen. + +Then: + +```text +sheep steps in direction d = shift(sheep & STEP_SOURCES[d], δ) & empty +tiger steps in direction d = shift(tigers & STEP_SOURCES[d], δ) & empty +jumped sheep = shift(tigers & JUMP_SOURCES[d], δ) & sheep +tiger jumps in direction d = shift(jumped sheep, δ) & empty +``` + +`sheep_steps()` and `tiger_targets()` compute these masks, and `get_moves` turns each set bit back +into a `Move` (the source is the destination minus `δ`, or minus `2δ` for a jump). Tiger jumps are +listed before tiger steps, since the search wants to try kills first. While sheep are in hand, the +sheep's only moves are placements on every empty point. + +`has_moves(turn)` uses the same masks but only asks whether any is non-zero, without building a +`Vec`. `check_win` uses it, since it's called at every node of the search. + +## Playing moves + +- `check_move(mv)` returns `Ok(())` or the specific `MoveError`: placing with none in hand, onto an + occupied point, moving a sheep while some are still in hand, moving something that isn't there, + moving off a line, jumping over something that isn't a sheep, and so on. The tests assert on the + exact variant. +- `make_move(mv)` checks first and leaves the board unchanged on an error. +- `make_move_unchecked(mv)` skips the checks. Use it only for moves from `get_moves` (the search + does, for speed). An illegal move here leaves the board in a state the rules can't reach. +- `after_move_unchecked(mv)` returns a new board instead of changing this one. + +A tiger move of two points always kills the sheep in between (`move_tiger` uses the `midpoint`). + +## Winning and drawing + +`check_win(turn)` is called with the side **about to move**, and `true` means the side that **just +moved** has won: + +- Tigers have won once 5 sheep are dead: `sheep_count() + sheep_left() <= 15`. +- Otherwise, the side that just moved has won if `turn` has no legal move. This is how sheep win, + by leaving every tiger without a move. (Tigers could in principle win this way too, by leaving the + sheep with no moves.) + +So `Outcome::win(turn.next_turn())` is the winner when `check_win(turn)` is true. + +### Repetitions + +A game is drawn on a threefold repetition, as in chess: the same position with the same side to +move, for the third time. `repetitions(previous, board)` counts how many times `board` came up +before with the same side to move, where `previous` is every earlier board, oldest first. Since the +last board in `previous` had the other side to move, it looks at every second board going back: +`previous.iter().rev().skip(1).step_by(2)`. + +Two shortcuts keep it cheap: + +- Placing and killing can't be undone, so nothing can repeat while sheep are in hand: it returns 0. +- For the same reason, it stops scanning at the first earlier board with a different number of + sheep on it. + +`REPETITION_DRAW` = 2: a position that has come up twice before is a draw. The search uses a +stricter rule internally (one earlier occurrence scores as a draw); see [The minimax search](search.md#repetitions). + +## Symmetries + +The board has 8 symmetries: 4 rotations, each optionally mirrored. All of them map lines to lines, +because they keep the parity of `x + y`, so a transformed position is just as legal and equally good +for either side. The search uses this to share cache entries between symmetric positions, and +training uses it to show the network each position in a random orientation. + +- `transform_pos(pos, sym)` with `sym` in `0..SYMMETRIES` (8): bit 2 of `sym` swaps x and y, then + bit 0 mirrors x and bit 1 mirrors y. +- `inverse_symmetry(sym)` undoes it. Plain mirrors undo themselves; with the swap first, undoing + means swapping which axis is mirrored. +- `transform_move(mv, sym)` transforms both ends of a move. +- `GameBoard::transformed(sym)` transforms a whole board. Doing that point by point would be slow, + so `ROW_MAPS` (built at compile time) holds, for each symmetry and each of the 5 rows, where each + of the 32 possible sets of points in that row end up. A mask then transforms in 5 table lookups + ORed together. The sheep-in-hand bits are carried over unchanged. +- `canonical()` returns the transform with the smallest `key()` and the `sym` that reaches it. All 8 + symmetric boards have the same canonical board. diff --git a/docs/building.md b/docs/building.md new file mode 100644 index 0000000..9c9609b --- /dev/null +++ b/docs/building.md @@ -0,0 +1,114 @@ +# Building + +## Quick start + +```bash +nix develop # or let direnv do it: the repo's .envrc says `use flake` +cargo run --release # play a game (computer against computer by default) +cargo test +``` + +Without Nix, any stable Rust toolchain from **1.87** on works (the code uses +`unsigned::is_multiple_of`, stabilised in 1.87). The flake currently pins rustc 1.95. + +```bash +rustup toolchain install stable +cargo run --release +``` + +Always use `--release` (or the `profiling` profile) for anything that searches or trains. A debug +build searches many times slower, so the computer players reach much shallower depths in the same +time limit and training takes hours longer. + +## The toolchain: Nix + +| File | Purpose | +|------|---------| +| `flake.nix` | The real definition: the package and the dev shell | +| `flake.lock` | Pins the exact revisions of the flake's inputs | +| `.envrc` | `use flake`, so [direnv](https://direnv.net) enters the dev shell when you `cd` in | +| `shell.nix`, `default.nix` | flake-compat shims, so `nix-shell` and `nix-build` work without flakes | + +### Flake inputs + +| Input | Used for | +|-------|----------| +| `nixpkgs` (26.05) | Everything: rustc, cargo and the dev tools | +| `naersk` | Builds the crate as a Nix package (`defaultPackage = naersk-lib.buildPackage ./.`), reading `Cargo.lock` so dependencies are fetched reproducibly | +| `flake-utils` | `eachDefaultSystem`, so the package and shell exist for every common platform | + +### What the dev shell provides + +| Tool | Why it's there | +|------|----------------| +| `cargo`, `rustc` | Building and testing | +| `rustfmt` | Formatting (but see the note on style below) | +| `clippy` | Lints: `cargo clippy` | +| `rust-analyzer` | Editor support; the shell sets `RUST_SRC_PATH` so it can find the standard library's source | +| `pre-commit` | Git hook runner, for anyone who sets up hooks | +| `perf`, `samply` | Profiling the search (see [Benchmarking and profiling](benchmarking.md)) | + +`nix build` builds the release binary into `./result/bin/tigers-and-sheep-rs`. This is also what +the GitHub workflow in `.github/workflows/build_nix.yml` runs on every push. Note that `.github` is +currently listed in `.gitignore`, so that workflow only exists locally and isn't committed. + +## Crate dependencies + +The crate keeps its dependencies few. Everything else (the board, the search, the neural network, +its optimiser, the random number generator, the weights file format) is written by hand. + +| Crate | Version | What it does here | +|-------|---------|-------------------| +| [`ratatui`](https://ratatui.rs) | 0.30 | The terminal UI: layout, bordered panes, paragraphs and the `Widget` trait that `BoardView` and every `Player` implement. It re-exports `crossterm`, which the game uses through `ratatui::crossterm` for raw mode, mouse capture and reading key and mouse events. Don't add `crossterm` as a direct dependency: the re-export keeps the two versions in step. | +| [`clap`](https://docs.rs/clap) | 4.6, feature `derive` | The command line (`Cli`, `Command`, `PlayArgs`, `TrainArgs` in `main.rs`), including `--help` text taken from the doc comments | +| [`rayon`](https://docs.rs/rayon) | 1.12 | Parallelism for training only: self-play games and matches run across all cores, and the network's gradient and loss are computed in parallel chunks. The game itself is single-threaded. | + +## Cargo profiles + +| Profile | Command | Use | +|---------|---------|-----| +| `dev` | `cargo build`, `cargo test` | Day-to-day development and tests | +| `release` | `cargo run --release` | Playing and training | +| `profiling` | `cargo build --profile profiling` | Release optimisations plus debug info, so profilers can show function names and source lines. The binary lands in `target/profiling/`. | + +## Cargo features + +| Feature | Effect | +|---------|--------| +| `search-stats` | Counts nodes, leaves, cache probes and hits, cutoffs and more during the search, and makes `bench` print them. Without it the `count!` macro compiles to nothing, so it costs nothing. | + +Run the tests both with and without it when touching the search, since some code only exists in +one configuration: + +```bash +cargo test +cargo test --features search-stats +``` + +## Running + +```bash +cargo run --release -- --help +cargo run --release -- -S human -T claude --time 5 # you play sheep against ClaudePlayer +cargo run --release -- -S weights/latest.bin -T human # a trained network plays sheep +cargo run --release -- train 50 500 weights # train a network +cargo run --profile profiling -- bench 9 # time the search +``` + +The game needs a terminal that supports mouse reporting and Unicode box-drawing characters; any +modern terminal emulator does. The board grows to fill whatever space the window gives it. + +## Generated files + +| Path | What | In git? | +|------|------|---------| +| `target/` | Cargo's build output | No | +| `result` | Symlink to the `nix build` output | No | +| `weights/` | Trained networks, `gen-NNN.bin` and `latest.bin` | No | +| `.direnv/` | direnv's cache of the dev shell | No | + +## Code style + +Tabs for indentation and braces on their own line (Allman style). A few trait-impl blocks use +4-space indentation. `cargo fmt` would reformat the whole crate to a different style, so only run it +on a file you're happy to see restyled, never across the crate. diff --git a/docs/players.md b/docs/players.md new file mode 100644 index 0000000..7a5c145 --- /dev/null +++ b/docs/players.md @@ -0,0 +1,170 @@ +# Players + +A side in the game is a `Player`. The game coordinator doesn't know or care whether it's a human +clicking, a search, or a network: it asks the player for a move, passes on input, and draws whatever +the player wants to show. Both traits are in [`src/player.rs`](../src/player.rs). + +## The `Player` trait + +```rust +pub trait Player +{ + fn name(&self) -> String; + fn update(&mut self, _board: GameBoard, _turn: Turn) {} + fn pick_move(&mut self, _board: GameBoard, _turn: Turn, _previous: &[GameBoard]) -> Option { None } + fn handle_input(&mut self, _input: Input, _board: GameBoard, _turn: Turn) -> Option { None } + fn highlights(&self) -> Highlights { Highlights::default() } + fn reset(&mut self) {} + fn render(&self, area: Rect, buf: &mut Buffer) { /* shows name() */ } + fn render_last_turn(&self, _area: Rect, _buf: &mut Buffer) {} +} +``` + +Only `name` is required. Players are **polled, not blocking**: no method waits for anything, so the +coordinator can keep redrawing and handling quit keys whatever kind of player is on move. + +| Method | When it's called | What to do | +|--------|------------------|------------| +| `name` | For panel titles and the result | A short name, e.g. `"Claude"` | +| `update(board, turn)` | Before every redraw, while it's this player's turn | Remember the position if `render` needs it | +| `pick_move(board, turn, previous)` | Once per loop, while it's this player's turn and the game isn't over | Computer players: search and return `Some(move)`. Interactive players: return `None`. `previous` is every earlier board in the game, oldest first, for spotting repetitions. | +| `handle_input(input, board, turn)` | When the user clicks a board point (`Input::Click(pos)`) or presses a key (`Input::Key(event)`) during this player's turn | Return `Some(move)` once the input completes a move | +| `highlights()` | When drawing the board during this player's turn | `Highlights { selected, targets }`: a selected piece and the points it can move to | +| `reset()` | On **both** players after the user reverts to an earlier move | Drop any half-made selection and any comments about the last move. It is *not* called after a normal move, so a player clears its own selection when it returns a move. | +| `render(area, buf)` | Every redraw, while it's this player's turn | Draw the player's panel. The default shows `name()`. | +| `render_last_turn(area, buf)` | Every redraw during the *other* player's turn | Draw comments on the move this player just made. The default draws nothing. | + +Rules a player must follow: + +- **Only return legal moves.** The coordinator plays them with `make_move(..).unwrap()`, so an + illegal move panics. Moves from `board.get_moves(turn)` are always legal; `board.check_move(mv)` + checks any other. +- `pick_move` is never called once the game is over, so `get_moves(turn)` is never empty there. +- Input that arrives while a computer player is searching is handled after the search, so a long + `pick_move` delays quitting until it returns. Keep a time limit. + +`impl Widget for &dyn Player` makes every player a ratatui widget by forwarding to +`Player::render`, which is how the coordinator draws the panel. (A blanket +`impl Widget for &P` would break the orphan rule.) + +### Where each method shows up on screen + +```text +┌ Board ───────────────────────────┬ Moves ─────┐ +│ highlights() of the player │ │ +│ to move are drawn here │ │ +├──────────────────────────────────┼────────────┤ +│ render() of the player to move │ render_last│ +│ │ _turn() of │ +│ │ the other │ +└────────── Sheep: name() ─────────┴────────────┘ +``` + +## `LocalPlayer`: a human with a mouse + +[`src/local-player.rs`](../src/local-player.rs). It's the example of an interactive player: + +- `pick_move` keeps the default `None`, so the coordinator waits for input. +- `handle_input` takes clicks. While sheep are in hand, a click on an empty point places a sheep. + Otherwise a click on one of its own pieces selects it and keeps its legal moves; a click on one of + their destinations plays that move; any other click clears the selection. Illegal clicks leave a + message in red, from `MoveError`'s `Display`. +- `highlights` returns the selected piece and its destinations. +- `update` stores the position so `render` can show the sheep counts and an instruction. +- `render_last_turn` shows `Played `. +- `reset` clears the selection, message and last move. + +## The `MinimaxPlayer` trait + +Every computer player so far is a search with a different evaluation. `MinimaxPlayer` holds that +search, and **a blanket impl makes every `MinimaxPlayer` a `Player`**: + +```rust +impl Player for P { … } +``` + +So a computer player implements `MinimaxPlayer` only, never `Player` directly (the two impls would +conflict). + +```rust +pub trait MinimaxPlayer +{ + const WIN: f32 = f32::INFINITY; + const DRAW: f32 = 0.0; + + // Required + fn evaluate(&mut self, board: &GameBoard, turn: Turn) -> ScoreType; + + // Optional settings + fn depth(&self) -> usize { MAX_DEPTH } // at most 64 + fn time_limit(&self) -> Duration { Duration::from_secs(1) } + fn name(&self) -> String { "Computer".to_string() } + + // Optional storage that speeds up the search + fn cache(&mut self) -> Option<&mut dyn ScoreCache> { None } + fn killers(&mut self) -> Option<&mut Killers> { None } + + // Optional storage for the last-turn panel + fn set_last_search(&mut self, _report: Option) {} + fn last_search(&self) -> Option { None } + + // The search itself; not meant to be overridden + fn minimax(…) -> Option; + fn minimax_uncached(…) -> Option<(ScoreType, Option)>; +} +``` + +| Item | Purpose | +|------|---------| +| `evaluate(board, turn)` | The score of a position where the search stops. Positive favours tigers, whichever side is to move; `turn` is there for evaluations that care. Return finite values: `±WIN` (infinity) is reserved for won games. If the player has a cache, give symmetric boards the same score (see [the search](search.md#symmetric-positions-share-entries)). | +| `depth()` | The most plies to search, counting the move itself. Normally the time limit stops the search first. | +| `time_limit()` | How long `pick_move` may take. It stops deepening after half of it. | +| `cache()` | Return a `ScoreCache` (normally a `TranspositionTable`) to turn on the transposition table. | +| `killers()` | Return a `Killers` to turn on killer-move ordering. | +| `set_last_search` / `last_search` | Store and return the `SearchReport { mv, depth, score }` of the last `pick_move`, which the blanket impl's `render_last_turn` shows as "Played … / Searched to depth … / Score: …". | +| `WIN`, `DRAW` | Scores of a won game and of a repetition | + +The blanket `Player` impl provides: + +- `pick_move`: iterative deepening with the time limit (see [The minimax search](search.md)). +- `render`: the name and "Thinking…", which is on screen while the search runs. +- `render_last_turn`: the search report, with the score to 5 significant figures, or "forced win for + tigers/sheep". +- `reset`: forgets the search report. + +### Supporting types + +| Type | Purpose | +|------|---------| +| `ScoreType` | `f32` | +| `SearchReport` | The move, depth and score of the last search | +| `CacheEntry` | Bounds `lower..=upper` on a position's score and its best move | +| `ScoreCache` | Trait for caches: `lookup`, `insert`, `clear`. Implemented by `TranspositionTable` and (for tests) `HashMap` | +| `TranspositionTable` | Fixed-size cache: `new(bits)` gives `1 << bits` slots of ~24 bytes | +| `Killers` | Two killer moves per remaining depth | +| `SearchStats` | Counters filled in with the `search-stats` feature | +| `MAX_DEPTH` | 64 | + +## `ClaudePlayer` + +[`src/claude-player.rs`](../src/claude-player.rs). A `MinimaxPlayer` with a 2^20-slot +`TranspositionTable`, killers, and a hand-written evaluation from the tigers' side: + +```text +100 × dead sheep five dead sheep win the game for the tigers ++20 × jumps available now sheep left hanging +−15 × trapped tigers tigers with no move; trapping all of them wins for the sheep + +2 × tiger moves mobility in general, which the sheep win by squeezing to zero +``` + +`time_limit` and `max_depth` are public fields. `ClaudePlayer::new(time_limit)` makes one; the +`bench` and `train` code set `max_depth` and a huge time limit to get fixed-depth, repeatable +searches. + +## `NeuralPlayer` + +[`src/neural-player.rs`](../src/neural-player.rs). The same as `ClaudePlayer`, except that +`evaluate` returns `self.net.forward(board, turn)`, the [network](training.md)'s output in `-1..1`. +`NeuralPlayer::new(net, time_limit, table_bits)` lets training use a smaller table (2^16 slots), +since it runs one player per thread. Forced wins are still `±WIN` from the search itself, far +outside the network's range. diff --git a/docs/search.md b/docs/search.md new file mode 100644 index 0000000..5165e51 --- /dev/null +++ b/docs/search.md @@ -0,0 +1,204 @@ +# The minimax search + +Both computer players, `ClaudePlayer` and `NeuralPlayer`, use the same search. It lives in the +default methods of the `MinimaxPlayer` trait in [`src/player.rs`](../src/player.rs), so a player only +supplies an evaluation function and some storage, and gets the whole search for free. (See +[Players](players.md) for the trait itself.) + +The search is alpha-beta minimax with iterative deepening, a transposition table shared between +symmetric positions, killer moves, and draw detection by repetition. + +## Scores + +- Scores are `f32` (`ScoreType`), from the **tigers' point of view**: tigers maximise, sheep + minimise. (This is plain minimax, not negamax, so there is a `match turn` wherever the two sides + differ.) +- `evaluate(board, turn)` scores a position where the search stops. It should return a finite + number. +- A finished game scores `±WIN`, where `WIN = f32::INFINITY`. When `check_win(turn)` is true the + side that just moved has won, so with tigers to move the score is `-WIN` (sheep won) and with + sheep to move it is `+WIN`. +- A position that repeats an earlier one scores `DRAW` = 0. + +Because every forced win is the same `±∞`, the search itself can't tell a win in 3 from a win in 9. +Iterative deepening makes up for it: it stops at the first depth that finds a forced win, so the +move it plays is one that wins in the fewest plies. + +## Iterative deepening: `pick_move` + +The blanket `impl Player for P` implements `pick_move`: + +1. Clear the cache and the killers. Cache entries would still be valid for the next move (the key + includes the depth), but clearing bounds the memory used and with `TranspositionTable` it is + nearly free. +2. Start `path` as the game's earlier boards (`previous`), for repetition checks. +3. Search the root to depth 1, 2, 3, … up to `depth()` (at most `MAX_DEPTH` = 64). Each pass calls + `minimax_uncached` on the root with the previous pass's best move as the `hint`, so it's tried + first. +4. Stop when: + - a pass runs out of time (it returns `None`): its partial result is thrown away and the last + finished pass's move is kept; + - a pass finds a forced win or loss (`|score| >= WIN`): more depth can't change it; + - more than **half** the time limit has gone: the next pass takes several times longer than the + last, so it probably wouldn't finish anyway. +5. Store a `SearchReport { mv, depth, score }` with `set_last_search`, and return the move. + +Depth 1 ignores the deadline, so there is always a move to play however short the time limit is. + +Why deepen at all, instead of searching to one depth? Because the time a search takes is hard to +predict, and because each pass makes the next one faster: the cache remembers the best move found in +every position, and trying that first gives far more alpha-beta cutoffs. + +## Alpha-beta: `minimax_uncached` + +`minimax_uncached(board, turn, depth, alpha, beta, hint, deadline, path)` returns the position's +score and the move that gave it, or `None` if the deadline passed. + +1. If `check_win(turn)`: return `±WIN`. +2. If `depth == 0`: return `evaluate(board, turn)`. +3. If the deadline has passed: return `None`. This is checked only at interior nodes, after the two + cheap cases, since reading the clock isn't free. +4. Generate and order the moves (below). +5. For each move: push `board` onto `path`, call `minimax` on the child with `depth - 1`, pop it. + Tigers raise `alpha` to the best score so far, sheep lower `beta`. Once `alpha >= beta` the rest + of the moves can't matter to the parent, so stop (a **cutoff**). A quiet move that caused a cutoff + becomes a killer. + +The window `alpha..beta` is what the parent can still use. A score at or below `alpha` only means +"no better than this", and one at or above `beta` only "at least this". The search is *fail-soft*: +it returns the real best score it found even when that falls outside the window, which gives the +cache tighter bounds. + +Ties keep the first move, so even a position where every move loses still returns one. + +## The cache: `minimax` + +`minimax` wraps `minimax_uncached` with the transposition table. Many move orders reach the same +position, especially while sheep are being placed, so remembering results saves a great deal of work. + +### What an entry holds + +A `CacheEntry { lower, upper, best }` records what a search proved: the true score lies in +`lower..=upper`, and `best` is the move that gave it. Entries are keyed by the board, the side to +move, and the remaining depth, since a deeper search of the same position gives a better answer. + +After searching, the entry depends on how the score compares with the window it was searched with: + +| Result | Entry | Why | +|--------|-------|-----| +| `score <= alpha` (fail low) | `lower = -∞, upper = score, best = None` | Every move was only bounded from above, so none is known to be best | +| `score >= beta` (fail high) | `lower = score, upper = +∞, best` | The search stopped at a cutoff, so the score is only a lower bound | +| inside the window | `lower = upper = score, best` | The exact score | + +If there was already an entry, the two are intersected (the larger `lower`, the smaller `upper`). + +### Using an entry + +Before searching, `minimax` looks the position up: + +- `lower >= beta`: the position is already good enough to cut off. Return `lower`. +- `upper <= alpha`, or `lower == upper`: return `upper`. +- Otherwise narrow the window to `max(alpha, lower)..min(beta, upper)` and search, trying the entry's + `best` move first. + +If there's no entry at this depth, it looks up the same position at `depth - 1` — the entry left by +the previous iterative-deepening pass — and uses its best move as the hint. + +The root position is searched with `minimax_uncached` directly, so it never goes in the cache. + +### Symmetric positions share entries + +The board has 8 symmetries that preserve the rules (see [The board](board.md#symmetries)), and +symmetric positions have the same score. So `minimax` looks positions up by `board.canonical()`, and +all 8 orientations share one entry. The best move is stored as played on the canonical board and +turned back with `transform_move(m, inverse_symmetry(sym))` when it's read. + +This assumes `evaluate` gives symmetric boards the same score. `ClaudePlayer`'s evaluation does. +A `Network` only does approximately, since it learns symmetry from training on transformed positions; +the small differences don't matter in practice. + +In the fully symmetric opening this cut the number of nodes searched by more than four times. + +### `TranspositionTable` + +The `ScoreCache` trait has `lookup`, `insert` and `clear`. There are two implementations: + +- `HashMap<(GameBoard, Turn, usize), CacheEntry>`: simple and exact, kept as a reference for tests. +- `TranspositionTable`: what the players use. `new(bits)` allocates `1 << bits` slots of about + 24 bytes once (2^20 slots, about 24 MB, for the players), so nothing grows or rehashes during a + search. + +How the table works: + +- **Hashing.** The board's `key()` is mixed with the depth and turn, multiplied by the 64-bit golden + ratio constant `0x9E3779B97F4A7C15` (Fibonacci hashing), and the top bits pick a **bucket of two + slots**. +- **Exact keys.** Each slot keeps the full board, turn and depth, so a collision can lose an entry + but never return the wrong one. +- **Replacement.** The first slot of a bucket keeps the deepest entry, and the second takes + everything else. A new entry at least as deep as the first slot's moves that entry down to the + second slot rather than losing it. Without this, the 1.5 million leaf-level entries of a deep + search pushed out the few deep ones that save the most work: an always-replace table needed about + 35% more nodes. +- **Clearing by generation.** Every slot stores the generation it was written in. `clear()` just + increments the generation, so all old slots count as empty. After 255 clears the counter would come + back round to an old slot's generation, so then it really wipes the table. + +## Move ordering + +Alpha-beta cuts off most when the best move is tried first. In a perfectly ordered tree it searches +roughly the square root of the nodes plain minimax does. Moves are tried in this order: + +1. **The hint**: the cache's best move for this position, or the previous pass's best move at the + root. +2. **Tiger jumps.** `get_moves` lists them first. A kill is usually the best tiger move. +3. **Killer moves.** For each remaining depth, `Killers` keeps the last two quiet (non-jump) moves + that caused a cutoff there. Within one pass of iterative deepening, a remaining depth is a fixed + distance from the root, so killers are moves that refuted a *sibling* position, and often refute + this one too. A new killer goes in front of the old one, and a move already in front isn't added + twice. +4. **Everything else**, in generated order. + +This is done by rotating each chosen move to the front of the list (`rotate_right(1)` on a slice), +not by sorting: a `sort_by_key` cost about a quarter of the search's time and made it slower overall. +With this ordering, about 97% of cutoffs come on the first move tried. + +## Repetitions + +`minimax` and `minimax_uncached` carry `path`: the game's earlier boards (from `previous`) followed +by the boards along the current search line, pushed and popped around each child. + +At every non-root position, `minimax` first checks `repetitions(path, &board) > 0`, and if so +returns `DRAW` before looking at the cache. This is a **twofold** rule, stricter than the game's +threefold one. The reasoning: a side that can repeat a position once can keep repeating it until the +game is drawn, so the first repetition is already as good as a draw. This lets the side that is +behind find draws, and the side that is ahead avoid them, much earlier. + +The cache doesn't know the path, so an entry whose score was influenced by a repetition can be +slightly wrong for the same board reached a different way. Chess engines accept the same +inaccuracy. Since every path includes the root, it can't happen below depth 5, which is why the +tests at depths 3 and 4 against the reference search (which applies the same rule) are exact. + +## Correctness tests + +The tests in `player.rs` compare the search against `reference`, a plain minimax with no pruning, no +cache and no ordering, on positions from a range of pseudo-random games: + +- alpha-beta with no cache gives exactly the same score as `reference`; +- so does every cache kind (`CacheKind::Map`, and `CacheKind::TinyTable`, a table of 8 slots that + collides constantly), with and without killers; +- any legal hint gives the same score; +- a search that runs out of time stores nothing in the cache; +- `pick_move` respects the time limit, and picks a move whose score equals the best; +- repetitions score as draws, a tiger who is ahead avoids one, a sheep who is behind takes one; +- a tiger takes a winning kill. + +An optimisation that only makes the search faster must keep all of these passing and must leave +every move and score in `bench` unchanged (see [Benchmarking](benchmarking.md)). + +## Search statistics + +With `--features search-stats`, the `count!` macro increments thread-local `SearchStats` counters: +nodes, leaves, terminal positions, repetitions, cache probes, hits, returns and overwrites, cutoffs, +first-move cutoffs and move generations. `SearchStats::take()` reads and resets them. Without the +feature the macro expands to nothing. diff --git a/docs/training.md b/docs/training.md new file mode 100644 index 0000000..79da8f2 --- /dev/null +++ b/docs/training.md @@ -0,0 +1,260 @@ +# The neural network and training + +`NeuralPlayer` uses the same [minimax search](search.md) as `ClaudePlayer`, but scores positions with +a small neural network instead of hand-written rules. The network starts out random and learns only +by playing against itself. No human idea of a good position goes into it, and `ClaudePlayer` is +only ever used to measure progress, never as something to learn from. + +The network is in [`src/network.rs`](../src/network.rs) and the training loop in +[`src/train.rs`](../src/train.rs). Neither uses a machine-learning library: the forward pass, the +backpropagation and the optimiser are all written by hand. + +## The network + +A multilayer perceptron: + +```text +52 inputs ──▶ 64 ReLU ──▶ 32 ReLU ──▶ 1 tanh +``` + +The output is in `-1..1` and, like every score, positive favours the tigers. + +### Inputs + +Only the raw position, nothing derived from it: + +| Inputs | Meaning | +|--------|---------| +| 0..25 | 1 if a tiger is on that point (bit `x + 5y`) | +| 25..50 | 1 if a sheep is on that point | +| 50 (`HAND`) | Sheep in hand / 20 | +| 51 (`TIGER_TO_MOVE`) | 1 if tigers are to move | + +The network has to work out for itself that dead sheep are bad for the sheep, that a sheep with an +empty point behind it can be jumped, and so on. + +### Parameters + +All the weights and biases live in one flat `Vec` (`params`), at fixed offsets `W1`, `B1`, +`W2`, `B2`, `W3`, `B3`, `PARAMS` in all (about 5,500). That lets the optimiser, the gradient and the +file format treat them as one list of numbers. + +- `W1` is **input-major**: input `i`'s weights to the 64 hidden units are contiguous, at + `W1 + i*64 .. W1 + (i+1)*64`. +- `W2` is **unit-major**: hidden-2 unit `k`'s 64 incoming weights are contiguous. + +### Forward pass + +Most inputs are 0: at most 4 tiger bits and 20 sheep bits are set out of 50. So instead of a full +matrix multiply, `forward_full` starts layer 1 at its biases and **adds the weight row of each set +input**, then adds `hand × W1[HAND]` and applies ReLU. That's why `W1` is input-major. `for_active` +walks the set bits of the board masks with `trailing_zeros`. Layers 2 and 3 are ordinary dot +products, then `tanh`. + +`forward_matches_a_plain_matrix_multiply` checks this against the textbook calculation. + +### Initialisation + +`Network::random(seed)` uses He initialisation: normal weights scaled by `sqrt(2 / fan_in)`, with +zero biases. For layer 1 the fan-in is taken as 20 rather than 52, since only about a third of the +inputs are set at once. + +### Backpropagation + +The loss for one sample is the squared error `(out - target)² / 2`. `add_gradient` runs the forward +pass, keeping each layer's activations, then works backwards: + +1. Through `tanh`: `d_out = (out - target) × (1 - out²)`. +2. Layer 3's weight gradients are `d_out × h2`. The gradient flowing into each hidden-2 unit is + `d_out × W3[k]`, or 0 where that ReLU was off. +3. The same again through layer 2 into hidden layer 1, skipping units with no gradient. +4. Layer 1: only the set inputs have non-zero gradients, so again only their rows are touched. + +`gradient_matches_finite_differences` checks every layer's gradients against numerical estimates. + +### Parallel and deterministic + +`gradient(batch)` splits a batch into chunks of `GRAD_CHUNK` = 32 samples, computes each chunk's +gradient on rayon's thread pool, then **adds the chunks up in order**. `loss` does the same in chunks +of `LOSS_CHUNK` = 1024. Floating-point addition isn't associative, so summing in a fixed order is +what makes the result identical whatever the number of threads +(`training_is_the_same_on_any_number_of_threads`). Training is therefore reproducible: the same +seed gives the same network on any machine with any `RAYON_NUM_THREADS`. + +### The optimiser: Adam + +`train_batch` averages the gradient over the batch and takes one `Adam` step. Adam keeps running +averages of each parameter's gradient (`m`, decay `β1` = 0.9) and squared gradient (`v`, decay +`β2` = 0.999), corrects their bias towards their zero start, and moves each parameter by +`learning_rate × m̂ / (√v̂ + ε)`. In effect every parameter gets its own step size, which suits a +network where some inputs (a sheep on a rarely used point) are seen far less often than others. + +### File format + +`save` and `load` use a small binary format, all little-endian: + +| Bytes | Contents | +|-------|----------| +| 0..4 | `TSNN` | +| 4..8 | version (`u32`, currently 1) | +| 8..20 | inputs, hidden 1, hidden 2 (`u32` each) | +| 20.. | every parameter as `f32`, in `params` order | + +`load` rejects files of the wrong size, magic, version or layer sizes with `InvalidData`. So +changing the layer sizes makes old weights fail to load, and changing what an input *means* without +changing the sizes calls for bumping `VERSION`. + +## Self-play training + +```bash +cargo run --release -- train [generations] [games] [out-dir] [--from ] [options] +``` + +Training runs in **generations**. Each one plays a batch of games, turns them into training samples, +trains the network on them, and saves it. + +### 1. Starting point + +`run` starts from `--from` if given, otherwise the newest `gen-NNN.bin` in the out dir, otherwise +random weights (seed `0x5EED`). Generation numbers carry on from the newest file in the out dir +either way, so a run can be stopped and restarted. The Adam state and the sample buffer aren't saved, +so they start empty on a restart. + +### 2. Self-play + +Each generation plays `games_per_generation` (500) games of the network against itself, in parallel +across all cores (`parallel`, on rayon's pool). Each game: + +- uses a `NeuralPlayer` that searches to exactly `depth` (3) plies. A depth limit rather than a time + limit keeps runs reproducible, and the game's seed is derived from the generation and game number; +- plays random moves for the first `random_plies` (10) plies, so games start from different places; +- after that, plays a random move instead of the searched one with probability `epsilon` (0.05), + to explore positions the network would never choose; +- is a draw on a threefold repetition (`play` passes the earlier boards to the search, so the + search sees repetitions too), or after `ply_cap` (200) plies, a backstop for games that wander + without repeating. + +Every position is recorded as a `Ply` with the search's score for it (clamped to `-1..1`, so forced +wins become ±1), and whether a random move was played there. + +### 3. Labelling positions: TD(λ) + +Each position needs a target, the score the network should learn to give it. Two obvious choices +both have problems: + +- **The game's result** (+1, -1 or 0) is the truth, but noisy: a position early in the game had many + moves, some of them random, between it and the result. +- **The search score** of the next position is less noisy but biased, since it comes from the + network itself. + +TD(λ) blends them, working backwards from the end of the game: + +```text +target[last] = result +target[t] = (1 - λ) × score[t+1] + λ × target[t+1] +``` + +With `λ = 1` every position is labelled with the result; with `λ = 0` each is labelled with the next +position's search score. The default `lambda` is 0.7. + +**Random moves cut the chain.** A position where a random move was played is labelled with its own +search score instead, and the positions before it then build on that, so they don't learn from the +random move's consequences. This matters because random moves aren't equally bad for both sides: a +random sheep move usually leaves a sheep to be jumped, while a random tiger move costs little. +Without the cut, the network learnt that tigers nearly always win. + +### 4. The sample buffer + +The samples of each generation are kept, split by outcome (tiger win, sheep win, draw), and the +network trains on the last `buffer_generations` (5) generations together. Training on more than the +latest games smooths out the network's swings from one generation to the next. + +### 5. Balancing outcomes + +Self-play ends mostly in tiger wins, largely because of those random sheep moves. Trained on +everything, the network would mostly learn what tiger wins look like. So with `balance_outcomes` +(on by default; `--no-balance` turns it off), `balanced` builds each epoch from: + +- as many positions from sheep-win games as from tiger-win games: their mean, so the epoch keeps the + same size. The bigger pool gives a random subset (every position at most once), and the smaller one + gives every position plus random repeats; +- every position from drawn games, once. + +If either kind of win has no positions at all there is nothing to balance, and everything is used. + +### 6. Training + +For each of `epochs` (2) epochs: build the epoch's samples, shuffle them, show each in a **random one +of the 8 symmetric orientations** (`GameBoard::transformed`), and train in batches of `batch_size` +(256) with Adam at `learning_rate` (1e-3). The random orientations are data augmentation: they teach +the network that symmetric positions are equally good, and multiply the variety of positions it sees. + +### 7. Matches + +On every generation whose number is a multiple of `match_every` (10), the network plays two matches +of `match_games` (100) games each, alternating sides, at the same depth: + +- against the generation that last played matches (N − 10), loaded from its `gen-NNN.bin`, or the + network the run started from if that file is missing; +- against `ClaudePlayer`. + +Each pair of games (one as each side) shares a seed, so both sides get the same 4 random opening +moves. The score is the share of points won, with a draw worth half. Matches are slow and only +measure progress, so other generations skip them. + +### 8. Saving + +Each generation is saved as `out_dir/gen-NNN.bin` and copied to `out_dir/latest.bin`. + +## Reading the output + +```text + gen trained tigers sheep draws T before S before T after S after vs prev vs Claude train s time s + 499 128657 460 22 18 0.0161 0.0211 0.0194 0.0165 - - 0.26 1.3 + 500 128335 461 17 22 0.0198 0.0185 0.0161 0.0229 45% 82% 0.28 2.2 +``` + +| Column | Meaning | +|--------|---------| +| `gen` | Generation number | +| `trained` | Positions in each epoch | +| `tigers`, `sheep`, `draws` | How this generation's self-play games ended | +| `T before`, `S before` | Mean error on positions from tiger-win and sheep-win games in the buffer, before training | +| `T after`, `S after` | The same after training | +| `vs prev`, `vs Claude` | Match scores (only every `match_every` generations; `-` otherwise) | +| `train s`, `time s` | Seconds spent training, and for the whole generation | + +**Judge progress by `vs Claude`.** Self-play results say little, since the random moves skew them +towards tigers, and the errors measure how well the network fits its own targets, not how well it +plays. `vs prev` above 50% means the network beats its older self. + +## Settings + +Every `train::Config` field is a command-line option (`train --help`): + +| Option | Default | Meaning | +|--------|---------|---------| +| `generations` (positional) | 50 | Generations to train | +| `games` (positional) | 500 | Self-play games per generation | +| `out_dir` (positional) | `weights` | Where weights are saved and resumed from | +| `--from` | – | Start from this weights file | +| `--depth` | 3 | Search depth in self-play and matches | +| `--ply-cap` | 200 | A game this long is a draw | +| `--random-plies` | 10 | Random opening plies in self-play | +| `--epsilon` | 0.05 | Chance of a random move after that | +| `--lambda` | 0.7 | TD(λ) blend | +| `--buffer-generations` | 5 | Generations of samples to train on | +| `--no-balance` | off | Train on all positions without balancing outcomes | +| `--epochs` | 2 | Passes over the samples per generation | +| `--batch-size` | 256 | Positions per optimiser step | +| `--learning-rate` | 1e-3 | Adam's learning rate | +| `--match-games` | 100 | Games per match | +| `--match-every` | 10 | Play matches every this many generations | + +`RAYON_NUM_THREADS` limits the number of threads; the results don't depend on it. + +Then play the result: + +```bash +cargo run --release -- -S human -T weights/latest.bin +``` -- cgit v1.3.1