path: root/src/docs/MOVE_GUESSER.md

# Move-prediction ("policy") model -- design notes

Status: design converged enough to start implementation. Not yet begun.

## Idea

Train a small model to predict, given a position, how likely each legal
move is to be the move a strong human player would choose (the
Lc0/Maia-chess "policy head" / human-move-prediction pattern). Candidate
uses:
- Move-ordering hint at the root (`root.c`) -- reorder/bias toward
  plausible moves, cheap and low-risk: root is called once per search,
  over ~20-40 moves, so cost is a non-issue regardless of model size.
- Possibly extend to the top 1-2 plies of internal search
  (`generate.c`'s `_ScoreAllMoves`), not deeper. Cost there is
  bounded by how many ply-2 nodes alpha-beta actually visits (root
  branching factor many, not root-branching-factor^2), which is cheap
  enough for a linear model but rules out anything heavier.
- Outright root move pruning/reduction based on low policy confidence --
  explicitly flagged as the higher-risk version of this idea. A
  human-implausible move can still be objectively best (that's part of
  how engines out-play strong humans), so a hard prune here risks
  capping search quality below what plain search would find. Start with
  move-ordering use only; treat pruning as a later, carefully-gated
  experiment, not a given.
- Every-node use is explicitly ruled out -- far too expensive given
  `eval.c`'s existing sub-microsecond-per-node budget.

## Model choice

**Linear (logistic regression) model over handcrafted move features,
not a neural net, for the first version.** Rationale, by comparison
against the alternatives considered:

| | Linear/logistic (chosen) | Small MLP / NNUE-accumulator head | Conv policy head (AlphaZero/Lc0-style) |
|---|---|---|---|
| Params | hundreds | tens of thousands-~1M | millions+ |
| Root-only inference cost | microseconds total | tens of µs | hundreds of µs-ms |
| Training difficulty | trivial (sklearn, minutes) | moderate (small PyTorch job) | a real project (this is Maia's actual scope) |
| C port | dot product | matrix-vector + activation (same shape as NNUE forward pass) | not realistic hand-rolled, no ML framework at inference |

Conv-style board embeddings are off the table entirely for this codebase
(no ML framework at inference). An MLP on an NNUE-style board embedding
is a plausible *second* iteration once NNUE's accumulator exists (same
input representation, different output head) but isn't a dependency for
starting now.

**Don't encode raw move identity as one-hot from/to-square (4096
categories)** -- a linear model can't generalize across squares that
way (no shared weight helps "knight e4-f6" inform "knight e5-f7"); use
relative/derived features instead (see below). Raw square one-hot only
makes sense once there's a conv/attention architecture to generalize
across squares, which is explicitly not this version.

## Label and training objective

Label is categorical ("which legal move was played"), not a per-move
score -- this does **not** require search or eval annotation at all,
unlike the NNUE eval work. The label is extracted directly from PGN
move text.

**Variable candidate-set problem**: every position has a different
number of legal moves, so there's no fixed class space to hand to a
standard multiclass classifier (sklearn's `multi_class` machinery
assumes a fixed shared label set). Fix: flatten to one training row per
**(position, candidate move)** pair, not one row per position:
- Each legal move at a position becomes its own row with that move's
  feature vector.
- Binary label: 1 if this move is the one actually played, 0 otherwise.
- Train one shared binary logistic regression (`class_weight='balanced'`
  to handle the ~1-in-30-40 positive rate) across all rows from all
  positions pooled together.
- At inference: score every legal move at the *current* position with
  the one trained weight vector, then rank/softmax across just that
  position's candidates.

This is the standard "pointwise learning-to-rank" formulation and is
directly compatible with plain `sklearn.linear_model.LogisticRegression`
-- no custom loss, no variable-length output layer needed.

**Top-k falls out for free, no multi-label training needed.** A
softmax/logistic score is already a full relative-ranking signal over
all legal moves at a position; `argsort` the per-move scores and take
the top 3-4. No architecture change, no different label format --
exactly the single-label training above already produces this. Note
these are *relative* ranking scores, not calibrated probabilities --
fine for move-ordering, don't assume "70% confidence" literally means
70% empirical accuracy without a separate calibration check.

**Held-out validation**: hold aside a slice of positions (not used in
training) to measure model quality -- top-k coverage against the
held-out human moves is the first-pass metric (top-1 "exact match" is
the wrong metric for a move-ordering use case; top-3/top-5 coverage is
what actually matters, since the goal is getting the eventually-best
move searched early, not predicting humans exactly). Once that looks
reasonable, validate the actual move-ordering-hint use case via
`match_play.py`'s existing head-to-head gate (same `LOWER95 >= 0.5`
threshold used for DNA tuning), not just offline accuracy.

## Features

### Global (position-level, shared across all candidate moves at a position)
- material balance
- game phase, derived from material-left
- side to move
- castling rights, both sides
- king safety, both sides -- reuse `eval.c`'s `iKingSafety[]`, which is
  already computed per side after a full `Eval()` call; no new
  computation needed
- in-check flag

### Per-move (recomputed per candidate move)
Built from the `MOVE` union (`chess.h`): `cFrom`, `cTo`, `pMoved`,
`pCaptured`, `pPromoted`, `bvFlags`.

- `pMoved` (piece type)
- SEE value, if a capture
- gives-check flag (computed the same way `generate.c` does, via
  `ExposesCheck`/attack detection after making the move)
- relative square features instead of raw `cFrom`/`cTo`: file delta,
  rank delta, distance, and a centrality-table lookup on `cTo` (reuse
  whatever `eval.c` already has for this)
- **explicit disambiguated move-category, one-hot, not the raw
  `bvFlags` bit**: `{NORMAL, CAPTURE, DOUBLE_PAWN_PUSH, EN_PASSANT,
  PROMOTION, PROMOTION_CAPTURE, CASTLE_KINGSIDE, CASTLE_QUEENSIDE}`.
  The raw "special" bit's meaning is context-dependent on `pMoved`
  (special+king=castle, special+pawn=double-jump/en-passant/promotion
  depending on `pPromoted`/`pCaptured`), so it must be decoded into
  explicit disjoint categories *before* being handed to a linear model
  -- feeding the raw bit directly would conflate castle-ness with
  promotion-ness, etc. Decode mirrors the existing `IS_CASTLE`/
  `IS_PROMOTION`/`IS_ENPASSANT`/`IS_DOUBLE_JUMP` macros exactly; castle
  side (kingside/queenside) isn't in the union bits at all and must be
  derived from `cTo` (g1/g8 vs. c1/c8).

**Explicitly excluded**: dynamic move-ordering signals (history table,
countermove table, continuation-history evidence). These don't exist
in this training setting at all -- they're accumulated *during* a
single search and reset between searches, so there's no equivalent
"has this move class worked before" signal minable from a static human
PGN position with no search running. (Could become relevant again if
ever training on self-play search traces instead of human games, but
that's a different, much more expensive data source -- not planned.)

## Training data pipeline

Driven by a persistent `typhoon` subprocess via the xboard protocol --
the same `Engine` class pattern `tune_eval_dna.py` and `match_play.py`
already use (one long-lived process, many `setboard`/command round
trips over stdin/stdout, not one process spawned per position -- the
per-call overhead that pattern avoids is exactly what the earlier
`EvalCommand` persistent-context fix was about).

**New engine command, `movefeatures`**: given the current position
(after `setboard`), generates the legal move list and dumps the full
feature vector for every legal move via `Trace()` (same style as
`evaldna dump`). Critically, this calls the *same* feature-building
code that real move-ordering will eventually call -- see "Shared
feature code" below -- so there is only ever one implementation of the
`MOVE`-union decode logic, never a second hand-ported copy in Python
that can silently drift from `chess.h` if the union's bit layout ever
changes.

Python driver loop: `setboard <fen>` / `movefeatures` / parse stdout
into feature rows, across the full training position set, against one
subprocess. Source positions: `../pgn/lichess_elite_*.pgn` and
`../pgn/twic_filtered.pgn`, both directly usable as (position,
move-played) pairs with no search/eval annotation needed.

**Label extraction correctness check**: for each extracted row, verify
the label-matched move, replayed, produces the same resulting FEN as
the PGN's next recorded position -- catches silent label corruption
from castling-notation/en-passant/promotion-parsing mismatches early,
before training on volume.

## Deployment in C (no Python/ML framework at inference)

Logistic regression's output is just a weight vector + bias (dozens of
floats) -- far simpler than NNUE's eventual quantization/loader needs.
Export `sklearn`'s `.coef_`/`.intercept_` as a flat array, baked
directly into a C source file the same way `bake_dna.py` writes tuned
values into `eval.c`'s initializers (simplest option given how small
this is; a runtime-loadable file, `evaldna`-style, is a fallback if
retraining turns out to be frequent enough that recompiling each time
is annoying).

**Shared feature code is the real risk, not the weight format.** There
must be exactly one function, e.g. `BuildMoveFeatures(ctx, move) ->
float[N]`, called by both the `movefeatures` dump command (training
data generation) and the real move-ordering caller (`root.c`, and
`generate.c` if extended to ply-2). Two independent implementations of
this will eventually drift -- the same bug class this project's own
history has already hit more than once (the `command.c` eval-caching
bugs, the killer-table backfill collision). Inference is then: for
each legal move, call `BuildMoveFeatures`, dot-product against the
baked weight array, add bias, rank/softmax across this position's
legal moves.

**Guard against silent drift between retrains**: give the baked
feature-weight array a length/version check against
`BuildMoveFeatures`'s actual feature count (same defensive pattern as
`bake_dna.py`'s line-count-mismatch abort), so a future feature-vector
change that forgets to retrain fails loudly at build/startup instead of
silently scoring garbage.

## Staged implementation plan

Each stage should produce something checkable before moving to the
next -- don't bundle these into one big change.

1. **`BuildMoveFeatures` + `movefeatures` command.** Write the shared
   feature-building function in C (global features first -- material,
   phase, side to move, castling rights, `iKingSafety[]` -- then the
   per-move features, including the disambiguated move-category
   decode). Wire it into a new `movefeatures` command that dumps every
   legal move's feature vector via `Trace()`, driven by `setboard`.
   Checkable output: by hand, confirm a few known positions (a castle
   available, an en-passant-capturable position, a promotion) produce
   the expected one-hot move-category for each special move.

2. **Python extraction driver.** Persistent-subprocess `Engine` loop
   (reuse the `tune_eval_dna.py` pattern) over `lichess_elite_*.pgn` /
   `twic_filtered.pgn`: `setboard` + `movefeatures` per position, parse
   stdout into `(features, label)` rows. Run the replay-verification
   check (label-matched move, replayed, matches the PGN's next FEN) on
   a sample before trusting volume. Checkable output: a cached rows
   file (parquet/csv) plus a verification-pass rate printed at the end.

3. **Train + offline validation.** Flatten to per-(position, move) rows
   with binary labels, `sklearn.linear_model.LogisticRegression` with
   `class_weight='balanced'`, train/held-out split. Checkable output: a
   top-1/top-3/top-5 coverage number on the held-out slice. Stop here
   and reassess if top-3 coverage looks weak before building any C
   deployment path -- no point wiring up inference for a model that
   doesn't predict anything.

4. **Export + C inference wiring, root only.** Bake `.coef_`/
   `.intercept_` into a C array (`bake_dna.py`-style, with a
   length/version guard against `BuildMoveFeatures`'s feature count).
   Add the scoring loop to `root.c`: for each root move, call
   `BuildMoveFeatures`, dot-product, rank. Gate this behind a flag so it
   can be toggled off cleanly, not wired in live as the only ordering
   path on the first pass.

5. **Head-to-head validation via `match_play.py`.** Candidate = root
   ordering using the model's ranking; baseline = current root
   ordering. Gate on `LOWER95 >= 0.5`, same as DNA tuning. This is the
   real test -- offline top-k accuracy from stage 3 is a necessary
   check, not a sufficient one, since move-ordering quality and human-
   move-prediction accuracy aren't the same thing.

6. **If stage 5 clears the gate: extend to ply-2** in
   `generate.c`/`_ScoreAllMoves`, same model, same `BuildMoveFeatures`
   call, no architecture change -- just a second call site. Re-run the
   `match_play.py` gate for this extension separately; a win at root
   doesn't guarantee a win at ply-2 (different node population, deeper
   in a quiescent-ish part of the tree).

7. **Out of scope until the above lands**: root-level pruning based on
   low policy confidence (the explicitly higher-risk use case), and the
   NNUE-accumulator-based second iteration described in "Future
   direction" below.

## Future direction (not needed to start)

Once NNUE's accumulator exists (see `NNUE.md`), a second iteration
could replace the handcrafted global+per-move feature vector with a
learned board embedding (same accumulator, second output head) --
this trades interpretability (today's linear weights are individually
auditable, the way eval constants are) for potentially higher
accuracy. Not a dependency of the first version; revisit after NNUE
lands.

## Open questions, not yet resolved

- Exact `BuildMoveFeatures` signature and feature-ordering convention,
  shared between the dump command and the real move-ordering caller --
  deferred until implementation starts.
- Whether/how far to extend beyond root into ply-2 internal search --
  cost looks affordable per the analysis above but not yet measured
  against real search statistics (how many ply-2 nodes actually survive
  alpha-beta pruning in practice).
- Calibration -- not needed for ranking/move-ordering use, but would be
  needed if a future use case wants literal confidence thresholds (e.g.
  for the higher-risk pruning idea).