diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/README.md | 27 | ||||
| -rw-r--r-- | docs/adding-a-player.md | 214 | ||||
| -rw-r--r-- | docs/architecture.md | 133 | ||||
| -rw-r--r-- | docs/benchmarking.md | 79 | ||||
| -rw-r--r-- | docs/board.md | 163 | ||||
| -rw-r--r-- | docs/building.md | 114 | ||||
| -rw-r--r-- | docs/players.md | 170 | ||||
| -rw-r--r-- | docs/search.md | 204 | ||||
| -rw-r--r-- | docs/training.md | 260 |
9 files changed, 1364 insertions, 0 deletions
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<SearchReport>, +} + +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<SearchReport>) { self.last_search = report; } + + fn last_search(&self) -> Option<SearchReport> { self.last_search } +} +``` + +That's all: the blanket `impl<P: MinimaxPlayer> 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<Move> + { + // 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<TrainArgs> for Config` + converts them. Keep the two in step when adding a setting. + +`make_player` turns a `PlayerKind` into a `Box<dyn Player>`, 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<Move> { None } + fn handle_input(&mut self, _input: Input, _board: GameBoard, _turn: Turn) -> Option<Move> { 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<P: Player> 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 <move>`. +- `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<P: MinimaxPlayer> 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<SearchReport>) {} + fn last_search(&self) -> Option<SearchReport> { None } + + // The search itself; not meant to be overridden + fn minimax(…) -> Option<ScoreType>; + fn minimax_uncached(…) -> Option<(ScoreType, Option<Move>)>; +} +``` + +| 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<P: MinimaxPlayer> 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<f32>` (`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 <weights>] [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 +``` |