From 1cfc6859fc0dfa9d3094213e2604f791513cc278 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Fri, 4 Sep 2026 09:33:50 -0700 Subject: 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 Claude-Session: https://claude.ai/code/session_01Jntky4yGUTyQVaGCXms4F2 --- src/board_representation/MOVEGEN_MIGRATION.md | 374 ++++++++++++++++++++++++++ 1 file changed, 374 insertions(+) create mode 100644 src/board_representation/MOVEGEN_MIGRATION.md 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. -- cgit v1.3