Add move-generation bitboard migration scoping doc (planning only)

Drafted after GetAttacks's migration landed, to evaluate extending the
same bbPieces/bbPawns/ray-table substrate to generate.c's seven
piece-type move generators. Kept as a separate document from
MIGRATION.md rather than a new section there, same reasoning as
dropping CountKingSafetyDefects from that plan: this is a
substantially bigger, higher-risk surface (7 functions, ~3400 lines,
no existing reference implementation to diff against, and the
pseudo-legal over-generation contract is load-bearing -- a bitboard
rewrite that accidentally becomes more legal-aware is a silent
behavior change, not a free improvement).

Covers: per-function rollout plan (knight/king first as
lowest-risk/best-precedented, rook/bishop as the real segment-marking
design work, queen mechanical once those land, pawns last and
possibly not worth it), a stronger correctness gate than GetAttacks
had (perft node-count matching against externally-known-correct
numbers, not just internal self-consistency), and a confirmed (not
just flagged) scope gap: _GenerateEscapes, the in-check move
generation path, has its own independent mailbox implementation and
is not covered by the seven piece-type functions this plan targets.

No code changes -- planning only.

Co-Authored-By: Claude Sonnet 5 <[email protected]>
Claude-Session: https://claude.ai/code/session_01Jntky4yGUTyQVaGCXms4F2

1 files changed, 374 insertions, 0 deletions

diff --git a/src/board_representation/MOVEGEN_MIGRATION.md b/src/board_representation/MOVEGEN_MIGRATION.md
new file mode 100644
index 0000000..5ba30d8
--- /dev/null
+++ b/src/board_representation/MOVEGEN_MIGRATION.md
@@ -0,0 +1,374 @@
+# 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.