# 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.