path: root/src/board_representation/MOVEGEN_MIGRATION.md

# Migration plan: bitboard-backed move generation (`generate.c`)

**Status: planning only. No code written.** This is a scoping document,
drafted after `MIGRATION.md`'s `GetAttacks` work landed, to decide
whether/how to extend the same bitboard substrate (`bbPieces`,
`bbPawns`, `g_RookRayToEdge`/`g_BishopRayToEdge`/`g_RookRayAll`/
`g_BishopRayAll`, `g_KnightAttacksBB`, `g_PawnAttackOriginBB`) to move
generation itself. Deliberately kept as a **separate** document from
`MIGRATION.md`, not a new section appended to it -- same reasoning as
dropping `CountKingSafetyDefects` from that plan: this is a
substantially bigger, higher-risk surface than `GetAttacks` was, and
bundling it in would blur two very differently-shaped efforts.

## 0. Why this is a bigger project than `GetAttacks` was

`GetAttacks` was one ~150-line function answering one narrow query
("which of this side's pieces attack square X") with a single,
well-defined output (a `SEE_LIST`) and an existing reference
implementation (`SlowGetAttacks`) to diff against. Move generation
(`generate.c`, ~3400 lines) is qualitatively different:

- **Seven piece-type generator functions**, each with its own
  mailbox-walk logic: `GenerateKnight`/`GenerateWhiteKnight`,
  `GenerateBishop`, `GenerateRook`, `GenerateQueen`,
  `GenerateBlackKing`/`GenerateWhiteKing`, `GenerateWhitePawn`/
  `GenerateBlackPawn`, dispatched via `_GenerateAllMoves`'s function
  pointer `JumpTable[]` (keyed by `PIECE` value) plus a separate
  `_GenerateEscapes` path used when the side to move is in check --
  confirmed (`generate.c`, checked directly) to have its own
  independent mailbox implementation, *not* built on top of the seven
  functions this plan covers, so it's a scope gap this plan's
  per-piece-type toggle doesn't close automatically (see section 6).
  There is no single existing "reference implementation" to diff a new
  one against the way `SlowGetAttacks` served `GetAttacks` -- the
  mailbox generator *is* the only implementation, so a bitboard version
  becomes the second one, and the two must be cross-checked against
  each other from scratch (see section 4).
- **The pseudo-legal contract is load-bearing and must be preserved
  exactly, not "fixed."** `generate.c`'s own header comment is explicit:
  "[the generator] does not bother to see if moves expose their own
  king to check or if castles pass through check... it relies on
  MakeMove to throw out any illegal moves it generates." Every caller
  of `GenerateMoves` depends on this -- a bitboard rewrite that
  accidentally becomes *more* legal-aware (e.g. a pin-aware slider
  generator, which bitboard techniques make tempting) would silently
  change which moves get generated and rejected downstream, a subtle
  behavior change wearing a performance-optimization disguise. This is
  the move-generation analog of the `CountKingSafetyDefects` trap this
  session already hit once (a bitboard primitive that's *more accurate*
  than the thing it's replacing is a correctness bug here, not a free
  improvement) -- worth calling out up front since it's the most likely
  way this project goes wrong quietly.
- **Pawns are heavily special-cased** (single push, double push from
  the start rank, two capture directions, en passant, promotion to 4
  piece types, promotion-with-capture) in a way the other six
  functions aren't. `GetAttacks` sidestepped this by keeping its pawn
  check as a 2-square delta test throughout (later replaced with
  `g_PawnAttackOriginBB`, but still a bounded, simple query). Pawn
  *move* generation is not bounded the same way -- it's plausibly the
  piece type least suited to a clean bitboard win, or at least the one
  needing the most new bookkeeping (promotion-piece enumeration doesn't
  reduce to "which bits are set").
- **Correctness bugs here are more dangerous and harder to notice than
  in `GetAttacks`.** A `GetAttacks` bug shifts move-ordering/SEE
  values -- wrong numbers, but the move list itself stays correct,
  since `GetAttacks` doesn't generate moves, `generate.c` does. A move
  generator bug can silently drop a legal move (search quietly gets
  worse in some line and nobody notices) or emit an illegal one
  (`MakeMove`'s rejection is supposed to be the safety net, but that
  net was written assuming the *pseudo*-legal over-generation shape
  the mailbox generator actually produces -- an unfamiliar new
  generator could over- or under-generate in ways `MakeMove` doesn't
  expect). This raises the bar for section 4's correctness gate well
  above `GetAttacks`'s.

None of this means the project is a bad idea -- the underlying
technique (bitboards for sliding-piece move generation) is exactly
what most modern engines do, and this codebase already paid for the
hard part (ray tables, piece-location bitboards, verified against
20,000 random positions) doing `GetAttacks`. It means the plan and the
gate need to be more thorough than `GetAttacks`'s was, and that a
staged, one-piece-type-at-a-time rollout (section 3) is not optional
the way it was optional-but-recommended for `GetAttacks`.

## 1. Scope and non-goals

**In scope**: replacing the mailbox destination-square enumeration
inside each of the seven generator functions with a bitboard-driven
equivalent, built on the substrate `MIGRATION.md` already landed
(`bbPieces`, `bbPawns`, the ray/knight/pawn-origin tables). Each
replacement must produce the exact same *pseudo-legal* move set as the
function it replaces -- same over-generation behavior, same reliance
on `MakeMove` for final legality, bit for bit.

**Explicitly not in scope**:

- **Making the generator legal-aware** (pin detection, check-blocking
  awareness baked into generation itself). Tempting once bitboards are
  in play (a pinned piece's legal destinations are a bitboard AND away
  from being computed), but a behavior change, not a reimplementation
  -- see section 0. If ever wanted, it's a separate project with its
  own correctness/perf analysis, done *after* this one's pseudo-legal
  version is trusted, not bundled into it.
- **Move scoring / `_ScoreAllMoves` / dynamic move ordering.** These
  run as a separate pass after generation populates the move stack
  (`_AddNormalMove` just writes `(cFrom, cTo, pMoved, pCaptured)` into
  `MOVE_STACK`; nothing about scoring lives inside the generator
  functions this plan touches). Completely orthogonal, untouched by
  this plan.
- **`MOVE`'s `cFrom:8`/`cTo:8` encoding or `COOR`'s `0x88` numbering.**
  Same exclusion `MIGRATION.md` already made, for the same reason (a
  much bigger, separate project touching `san.c`/`ics.c`/`hash.c`/
  `book.c`/`root.c`). Still explicitly out of scope here.
- **`CountKingSafetyDefects`.** Already dropped from `MIGRATION.md`;
  not resurrected by this document either.
- **Castling move generation specifically** (inside
  `GenerateWhiteKing`/`GenerateBlackKing`). Low call-site cost already
  (at most 2 candidate moves, checked via simple square-emptiness
  tests), not ray-walk-shaped, nothing for a bitboard to speed up. Only
  the king's normal 8-adjacent-square destination enumeration is in
  scope for those two functions.

## 2. Foundation already in place (from `MIGRATION.md`)

This is the section that makes the project tractable rather than a
from-scratch undertaking:

- `POSITION.bbPieces[2][8]` and `POSITION.bbPawns[2]` -- incrementally
  maintained, zero-cost-to-read, already verified via `board.c`'s
  `VerifyPositionConsistency` DEBUG-build consistency check.
- `g_RookRayToEdge[4][128]` / `g_BishopRayToEdge[4][128]` -- per-square,
  per-direction "ray to board edge" masks, plus `g_RookRayAll[128]`/
  `g_BishopRayAll[128]` (all 4 directions pre-ORed, for the "is
  anything of mine even on this line" bulk check).
- `g_KnightAttacksBB[128]` -- per-square knight destination mask.
- `g_PawnAttackOriginBB[2][128]` -- per-square, per-side "where would
  a pawn need to stand to attack this square" mask (built for
  `GetAttacks`'s pawn-capture check; a *different* table, structured
  for the *attack* direction, would be needed for pawn move generation
  -- see section 3's pawn note).
- `FastFirstBit`/`FastLastBit` (`chess.h`, `static inline` bsf/bsr) --
  proven pattern for extracting bits out of a result bitboard into
  actual `COOR`s to hand to `_AddNormalMove`.
- The slider blocker-walk mechanism itself (`_WhoAttacksSquareBB` in
  `see.c`): nearest-blocker-per-direction via `bb & -bb` (positive
  direction) / `1ULL << (FastLastBit-1)` (negative direction), with
  per-direction early-out (`bbRay & bbSliders` before touching
  `bbOccupied`) and a bulk pre-check (`bbRookSliders & g_RookRayAll[c]`)
  before entering the direction loop at all. This is *almost* the
  right shape for rook/bishop/queen move generation already -- the
  difference is `GetAttacks` only needs the *nearest* blocker (to
  answer "does X attack Y"), while move generation needs *every*
  square from the piece up to and including the nearest blocker (all
  the empty squares are legal quiet moves, the blocker square itself
  is a legal move only if it's an enemy piece). Section 3 covers this.
- The stashed (not-committed, see `MIGRATION.md`'s section -1)
  `_EvalRookOccupancyBB` PoC from the earlier Eval bitboard work
  already solved almost exactly this "walk to nearest blocker, mark
  the whole segment" problem, including the friend/enemy/battery-piece
  classification table (`RMobCaseTable`) -- worth reading as reference
  for the segment-marking mechanism even though that PoC's own
  reader-migration work was abandoned (measured slower, for unrelated
  reasons -- see `MIGRATION.md`'s intro). The segment-marking idea
  itself isn't what made that work slow; duplicating both
  representations without removing the old one was.

## 3. Per-function plan

Ordered by expected implementation risk/complexity, cheapest and
best-precedented first. **Each function should be its own
implement-verify-benchmark-toggle cycle**, not one big-bang replacement
-- given section 0's correctness stakes, landing and gating
`GenerateKnight` alone before starting `GenerateRook` is not
extra-cautious overhead, it's the minimum viable rollout shape.

1. **Knight** (`GenerateKnight`/`GenerateWhiteKnight`) -- lowest risk,
   most precedented. `g_KnightAttacksBB[cKnight] & ~bbFriendlyOccupied`
   directly gives the full pseudo-legal destination bitboard in one
   lookup + one AND (no blocker walk needed at all, same as
   `GetAttacks`'s knight case). Extract bits, classify each as
   quiet/capture via `pos->rgSquare[c].pPiece` (already needed for
   `_AddNormalMove`'s `pCap` argument), call `_AddNormalMove`. Natural
   pilot function: reuses an already-built, already-verified table
   with zero new tables needed.
2. **King** (`GenerateBlackKing`/`GenerateWhiteKing`, normal moves
   only -- castling stays mailbox, see section 1). Needs a new
   `g_KingAttacksBB[128]` table (doesn't exist yet -- `GetAttacks`'s
   king case used a `DISTANCE(...)==1` delta check instead, since it
   only ever needs a single square's membership test, not an
   enumerable destination set; move generation needs the actual set).
   Same shape as knight otherwise: table lookup, AND off friendly
   occupancy, extract, classify, add.
3. **Rook/Bishop** (`GenerateRook`, `GenerateBishop`) -- the real test
   of the segment-marking idea from section 2. For each of the 4
   relevant ray directions: find the nearest blocker (existing
   mechanism from `_WhoAttacksSquareBB`), OR together `g_RookRayToEdge[
   u][c]` with the *complement* of "everything at-or-beyond the
   blocker" to get the empty-square segment (or, if no blocker on that
   ray, the whole ray), add the blocker itself as a capture only if
   enemy. Needs a per-direction "ray up to but not including
   `X`" mask -- either a new table (`g_RookRaySegmentTo[4][128][?]`,
   awkward since the blocker square varies per-call, not
   precomputable per-(direction, origin) pair alone) or a runtime
   computation via the existing ray + blocker bit (e.g. XOR the ray
   against the ray-from-the-blocker-in-the-same-direction, or a
   bit-masking trick -- needs actual design work, not just table
   reuse, unlike knight/king). This is where most of the real design
   effort in this project lives.
4. **Queen** (`GenerateQueen`) -- mechanically just rook-directions +
   bishop-directions combined, once 3 is solved; no new design needed,
   same caution `_EvalQueenOccupancyBB`'s PoC comment already flagged
   (a combined 8-ray table measured *slower* than reusing the rook/
   bishop tables in two passes -- don't rediscover that, reuse the
   two-pass structure).
5. **Pawns** (`GenerateWhitePawn`/`GenerateBlackPawn`) -- do last, and
   budget the most design time relative to its actual runtime cost.
   Single/double push and the two capture squares are each individually
   bitboard-friendly (a push mask shifted by rank, capture squares via
   a new `g_PawnAttackTargetBB[2][128]` -- note this is the *opposite*
   direction table from `g_PawnAttackOriginBB`, which answers "who
   could attack me", not "what can I attack"; the two are not
   interchangeable despite looking similar), but promotion enumeration
   (4 piece types x push/capture-left/capture-right, all needing
   separate `MOVE` entries) doesn't reduce to bitboard operations at
   all -- that part stays a small fixed-iteration loop regardless of
   how the destination squares were found. Realistic expected win here
   is smaller than knight/rook/bishop/queen, possibly small enough
   that it's not worth the correctness risk -- explicitly revisit
   "is this worth doing" after 1-4 land and are benchmarked, rather
   than assuming it's automatically worth doing because the others were.

## 4. Correctness verification

Two independent gates, both mandatory (stronger than `GetAttacks`
needed, per section 0):

1. **Move-set comparison harness**, new code (`testgenerate.c`),
   modeled on `TestGetAttacks`'s shape but comparing *sets of moves*
   rather than *sets of attackers*: for each of
   `GenerateRandomLegalPosition`'s existing 20,000 random positions,
   generate moves for the side to move with both the mailbox and
   bitboard generator for the specific piece type being migrated (not
   the whole board at once, while only some piece types have a
   bitboard version -- needs per-piece-type toggling, not just a
   global one, at least during rollout), and diff the resulting move
   sets as multisets of `(cFrom, cTo, pCaptured)` (promotion piece too,
   once pawns are in scope) -- order independence confirmed unnecessary
   to even think about here since `_AddNormalMove` order was never
   contractual to begin with (downstream scoring re-sorts everything
   anyway). Both generators are pseudo-legal (over-generating) by
   design, so this only requires the *pseudo-legal* sets to match, not
   a legal-move oracle.
2. **Perft node-count matching -- the harder, external-ground-truth
   gate `GetAttacks` didn't have available.** The existing `perft`
   command (`movesup.c:1273`) already reports node counts at a given
   depth from a position; perft counts for the standard starting
   position (and several well-known test positions -- "Kiwipete" and
   similar FENs are standard perft test positions in the wider chess
   programming community, worth pulling in a small fixed set of them
   rather than inventing new ones) are externally verified numbers,
   not just internally self-consistent the way `TestMoveGenerator`'s
   existing `PlyTest`/`PositionsAreEquivalent` checks are. Run `perft`
   to a moderate depth (5-6 is typically enough to catch generator
   bugs on standard test positions without taking too long) with the
   old generator, then again with the new one substituted in (per
   piece type, via the toggle in section 6), and require an *exact*
   match against both each other and the known-correct external
   number. A perft mismatch that's still internally self-consistent
   (i.e. `TestMoveGenerator`'s existing checks would pass) is exactly
   the failure mode most worth guarding against here -- a generator
   that's internally consistent but subtly wrong (missing a move type
   in some rare configuration) would sail through `PlyTest` but show
   up immediately as a perft node-count mismatch.
3. **`precommit_check.sh`** as always, for the crash/assert layer --
   unchanged from `GetAttacks`'s use of it.
4. **Full-suite behavioral check**, same reasoning and same three
   curated suites (`ecm_ringers`, `ecm_confident_quick`,
   `ecm_hard_quick`) at `sd10` against `head_reference/` as
   `MIGRATION.md` section 4 -- if anything more load-bearing here,
   since move generation feeds literally every node of every search,
   not just capture-ordering/pruning decisions the way `GetAttacks`
   did.
5. **`match_play.py` gate** (`LOWER95 >= 0.5`), same as `MIGRATION.md`.

## 5. Microbenchmarking

Same two-tier approach `MIGRATION.md` section 5 used (and that this
session's `GetAttacks` work actually executed, folded into
`TestGetAttacks` rather than a separate command):

1. **Isolated cycles/call per piece type**, interleaved old/new,
   across the same opening/middlegame/endgame density spectrum, added
   to (or modeled on) `testgenerate.c`. Gate: consistent win across
   the spectrum for a given piece type before that type's toggle is
   considered for default-on, same red-flag criterion as `GetAttacks`.
2. **Whole-engine NPS**: the existing `perft` command's `dNps` already
   gives a real, if wall-clock-based, whole-generator throughput
   number -- usable as-is for a rough before/after per piece type, but
   consider whether a `SystemReadTimeStampCounter`-based variant is
   worth adding given this box's demonstrated wall-clock noise
   (`MIGRATION.md`'s environment notes; earlier sessions saw 10x+
   run-to-run swings from unrelated load). `sd`-fixed-depth curated
   suite node counts (section 4 item 4) are the more reliable
   whole-engine signal either way, same lesson as `GetAttacks`.

## 6. Dual-support / toggle strategy

More granular than `GetAttacks`'s single `GETATTACKS_BITBOARD` switch,
given section 3's one-piece-type-at-a-time rollout requirement: one
`#define` per piece type (e.g. `GENERATE_KNIGHT_BITBOARD`,
`GENERATE_KING_BITBOARD`, `GENERATE_ROOK_BITBOARD`, ...,
`GENERATE_QUEEN_BITBOARD` implied once rook+bishop are both on),
each flipping that one entry in `_GenerateAllMoves`'s `JumpTable[]`
between the mailbox and bitboard function for that piece type,
independent of the others. This lets knight ship (and be trusted in
production) while rook/bishop/queen/pawn are still mid-development,
rather than gating all seven behind one flag the way a single combined
switch would force.

**Confirmed (not just flagged as a risk): `_GenerateEscapes` (the
in-check path) does NOT call any of the seven piece-type generator
functions.** Checked directly -- `GenerateKnight`/`GenerateRook`/
`GenerateBishop`/`GenerateQueen`/`GenerateWhitePawn`/`GenerateBlackPawn`
are referenced only from `_GenerateAllMoves`'s `JumpTable[]` and the
pawn-specific dispatch beside it; `_GenerateEscapes` has its own,
independent mailbox implementation. This means the per-piece-type
toggle above only ever covers the *not-in-check* path -- a real,
previously-unstated scope gap. Two options, not resolved by this
document:

1. Treat `_GenerateEscapes` as an eighth migration target with its own
   design/correctness/benchmark pass (likely smallest-scope-first
   candidate again, e.g. does it even have a slider-blocker-walk
   shape, or is it already simpler than the general case since it's
   specifically "moves that address a single check"?), or
2. Leave `_GenerateEscapes` on the mailbox path indefinitely even
   after the other seven functions migrate, accepting that in-check
   nodes don't get the speedup. Plausible if `_GenerateEscapes` turns
   out to be called rarely enough (most nodes aren't in check) that
   its contribution to whole-engine NPS is small regardless.

Whichever is chosen, `TestMoveGenerator`'s existing `PlyTest` already
exercises both `GENERATE_ALL_MOVES` and `GENERATE_ESCAPES` (the
`fInCheck` branch, generate.c:58) -- section 4's move-set comparison
harness needs to do the same, not just exercise the not-in-check path,
regardless of which option above is picked.

## 7. Retirement criteria

Per piece type, only delete that type's mailbox generator function
after **all** of:

- Move-set comparison harness (section 4.1) clean across the
  20,000-position sweep, for that piece type specifically.
- Perft matching (section 4.2) exact across the standard + known
  test-position set, at a depth deep enough to have exercised the
  piece type meaningfully.
- Isolated cycles/call (section 5.1) shows a consistent win across the
  density spectrum.
- Whole-engine `sd10` on all three curated suites shows no solve-count
  regression vs. `head_reference` -- run with *only* that piece type's
  toggle flipped, to attribute any regression correctly, not bundled
  with other in-flight piece-type migrations.
- `match_play.py` gate clears `LOWER95 >= 0.5`.
- `head_reference/` rebuilt as the new baseline once landed.

Given section 3's per-function rollout, this checklist runs up to
seven times (fewer if pawns end up not worth doing, or rook/bishop/
queen are gated together since queen has no independent design work).
Don't let an early piece type's clean bill of health (e.g. knight)
lower the bar for a later one -- each piece type's generator has a
different enough implementation to warrant its own full pass through
this list, same principle `MIGRATION.md` applied to why
`CountKingSafetyDefects` couldn't inherit `GetAttacks`'s clearance.