diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/GNUmakefile | 17 | ||||
| -rw-r--r-- | src/board_representation/MOVEGEN_MIGRATION.md | 912 | ||||
| -rwxr-xr-x | src/chess.h | 256 | ||||
| -rwxr-xr-x | src/data.c | 362 | ||||
| -rwxr-xr-x | src/eval_tune/test_vs_head.sh | 2 | ||||
| -rwxr-xr-x | src/generate.c | 1562 | ||||
| -rwxr-xr-x | src/main.c | 15 | ||||
| -rwxr-xr-x | src/movesup.c | 399 | ||||
| -rwxr-xr-x | src/see.c | 8 | ||||
| -rwxr-xr-x | src/testgenerate.c | 453 | ||||
| -rw-r--r-- | src/testsearch.c | 13 | ||||
| -rw-r--r-- | src/testsee.c | 125 | ||||
| -rw-r--r-- | src/testsup.c | 20 |
13 files changed, 4069 insertions, 75 deletions
diff --git a/src/GNUmakefile b/src/GNUmakefile index 601a362..ab35c7e 100644 --- a/src/GNUmakefile +++ b/src/GNUmakefile @@ -17,6 +17,15 @@ # GETATTACKS_BITBOARD=1: use the bbPieces/bbPawns-backed _GetAttacksBB # instead of the asm/CROUTINES GetAttacks -- see # board_representation/MIGRATION.md section 6 +# DISABLE_BITBOARD_MOVEGEN=1: opt back into the mailbox move +# generator/escapes/ExposesCheck/IsAttacked implementations -- the +# nine GENERATE_*_BITBOARD/EXPOSESCHECK_BITBOARD/ISATTACKED_BITBOARD +# toggles (board_representation/MOVEGEN_MIGRATION.md) are on by +# default as of the 2026-09-04 correctness/no-regression sweep +# (perft, move-set comparison harness, sd10 curated-suite parity, +# match_play.py). The mailbox code is still fully present and +# compiled either way -- this flag only flips which side of each +# macro-swap wins, it doesn't remove anything. # EVERYTHING=1: everything everything everything everything # # $Id$ @@ -103,6 +112,14 @@ ifdef GETATTACKS_BITBOARD PROFILE += -DGETATTACKS_BITBOARD endif +ifndef DISABLE_BITBOARD_MOVEGEN + PROFILE += -DGENERATE_KNIGHT_BITBOARD -DGENERATE_KING_BITBOARD \ + -DGENERATE_ROOK_BITBOARD -DGENERATE_BISHOP_BITBOARD \ + -DGENERATE_QUEEN_BITBOARD -DGENERATE_PAWN_BITBOARD \ + -DGENERATE_ESCAPES_KING_BITBOARD -DGENERATE_ESCAPES_BLOCK_BITBOARD \ + -DEXPOSESCHECK_BITBOARD -DISATTACKED_BITBOARD +endif + ifdef EVERYTHING PROFILE += -DEVAL_DUMP -DEVAL_TIME -DPERF_COUNTERS -DMP -DSMP -DTEST_NULL -DDUMP_TREE -fbounds-checking else diff --git a/src/board_representation/MOVEGEN_MIGRATION.md b/src/board_representation/MOVEGEN_MIGRATION.md index 5ba30d8..44527b1 100644 --- a/src/board_representation/MOVEGEN_MIGRATION.md +++ b/src/board_representation/MOVEGEN_MIGRATION.md @@ -1,15 +1,61 @@ # 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. +**Status (2026-09-04): Part A, Part B, and section 6b all implemented +and correctness/speed-gated; nothing shipped yet (every toggle still +off by default).** + +- **Part A** (section 3, `_GenerateAllMoves`): all six piece types + (knight, king, rook, bishop, queen, pawn) plus the `_GenerateAllMovesBB` + dispatch-layer rewrite -- done, correctness-verified per-piece-type + and combined. +- **Part B** (section 6a, `_GenerateEscapes`): both phases (king flight + via `_WhoAttacksSquareBB`, block/capture via `bbTargetMask` + + per-piece `SaveMe*BB` + the dispatch-loop elimination) -- done, + correctness-verified individually and combined. +- **Section 6b** (`movesup.c`): `ExposesCheck`/`FasterExposesCheck`/ + `ExposesCheckEp` and `IsAttacked`/`InCheck` -- done, correctness- + verified, `IsAttackedBB` additionally shows a genuine 0.73x-0.93x + speed win. +- **All nine toggles verified combined simultaneously**, including one + real bug found and fixed in the test harness itself (`testsup.c`'s + `GenerateRandomLegalPosition` never initialized `cEpSquare`) -- + 15/15 clean runs post-fix. +- **Section 4's `sd10` curated-suite gate has been run** against + `head_reference/`, with all nine toggles combined: `ecm_ringers` + 10/11 and `ecm_confident_quick` 84/90 match `head_reference` exactly; + `ecm_hard_quick` showed 25/90 against `head_reference`'s recorded + 28/90, but this was tracked down to intervening non-toggle-gated + commits unrelated to this migration (`5c8d794`/`a8806ad`), confirmed + by reproducing the identical 25/90 on plain current-HEAD mailbox with + every toggle off. **The correct comparison baseline going forward is + current HEAD's own numbers, not `head_reference`'s stale recorded + ones**: `ecm_ringers` 10/11, `ecm_confident_quick` 84/90, + `ecm_hard_quick` 25/90 (all at `sd10`, `--cpus 1 --hash 256m`) -- + `head_reference/` itself has not been refreshed to pick up + `5c8d794`/`a8806ad` yet (a separate, not-yet-run action via + `update_head_reference.sh`), so its own logs still show the older + 28/90 figure until that happens. +- **Still outstanding**: `match_play.py`'s `LOWER95 >= 0.5` gate (not + run), the 20,000-position move-set comparison harness section 4.1 + originally called for (never built -- perft plus direct + mailbox-vs-bitboard comparison harnesses have covered this gap so + far), refreshing `head_reference/` itself, and section 7's retirement + criteria (deleting any mailbox function) -- not cleared for anything, + nothing should be deleted yet. `_FindUnblockedSquares`/`WouldGiveCheck` + (flagged during the section 6b survey) remains a separate, unstarted, + smaller candidate. + +Originally a scoping document only (see the rest of this paragraph for +that history): 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 @@ -164,6 +210,139 @@ from-scratch undertaking: itself isn't what made that work slow; duplicating both representations without removing the old one was. +## 2a. New infrastructure required for magic bitboards + +Unlike everything in section 2, none of this exists yet -- it's a +prerequisite sub-project for step 3 of section 3, not a reuse of +`GetAttacks`-era work. Standard magic-bitboard components, all +per-piece-type (rook, bishop) and per-square: + +- **Relevant-occupancy masks** (`g_RookOccupancyMask[128]` / + `g_BishopOccupancyMask[128]`) -- the full ray-to-edge tables + (section 2) minus the actual board edge squares themselves (a piece + on the edge doesn't block anything beyond the edge, so those bits + are irrelevant to the lookup and must be excluded to keep the + occupancy-permutation count, and therefore the table size, minimal). +- **Magic numbers, occupancy masks, and attack tables -- decided: all + computed live at engine startup, in a new `InitMagic()` in `data.c`, + nothing hardcoded.** Initially assumed the random-candidate search + would be too slow to pay on every process launch (the validation + prototype's *total* runtime was 3.24s), which would have forced + baking found magics in as literal compile-time constants instead + (the way a published constant set would have been used). That + assumption was wrong, caught by re-checking the prototype's own + breakdown: **3.15s of that 3.24s was the separate PEXT-vs-multiply + microbenchmark** (400M loop iterations, unrelated to magic-finding), + not the search. Isolating just the search-and-verify work (a + from-scratch throwaway build of the same logic, no benchmark) + measured **0.22s total** for all 128 squares, both piece types, + full collision-freedom verification included. At that cost, adding + it to engine startup is in the same ballpark as accepting a slightly + heavier `InitializeRookRayTables()`-style init step, not a + qualitatively different cost -- doesn't justify the complexity of a + separate offline generator tool, hand-reviewed output, and a + hand-maintained pasted-in constant block that goes stale the moment + `data.c`'s ray tables or square numbering ever change shape. + `InitMagic()` computes, in order: occupancy masks (from the existing + `g_RookRayToEdge`/`g_BishopRayToEdge`, same cost class as today's + ray-table init), then magic numbers per square via the same + fixed-seeded (not time-seeded) sparse-random search the prototype + used -- fixed-seeded so a given build produces the same magics on + every run, keeping behavior reproducible for debugging even though + nothing is hardcoded -- verifying each one collision-free against + the slow ray-walk reference before accepting it, then builds the + attack tables (measured sizes: **819,200 bytes rook, 41,984 bytes + bishop**, trivial next to the ~75MB `SEARCHER_THREAD_CONTEXT`) by + filling from the now-verified magics. All of this runs once, at + process startup, before the first `GenerateMoves` call -- no + generator tool, no pasted constants, no separate offline step to + keep in sync. +- **Verification stays a startup-time gate, not a one-time offline + check.** Since `InitMagic()` runs fresh every process launch, the + collision-freedom check runs fresh every launch too -- actually + *safer* than hardcoded constants would have been (a hardcoded magic + silently wrong for some edge case would ship broken until caught by + section 4's harness; a startup-time verification failure would abort + immediately, every single run, the moment the underlying tables or + square numbering ever drifted out of sync with the search). +- **Concrete determinism trap to avoid**: `main.c:454` calls + `srand((unsigned int)time(0))` during startup, seeding libc's shared + `rand()` with the current time. If `InitMagic()`'s search were + implemented using that shared `rand()` (directly, or via any helper + built on it), it would silently inherit that time-based seed and + produce different magic numbers -- and therefore different + attack-table contents -- on every single process launch, exactly + the non-determinism this whole design is meant to avoid, regardless + of `InitMagic()`'s own call-order relative to that `srand()` call. + `InitMagic()` must carry its own private PRNG state (the same + fixed-seeded `xorshift64*` the prototype and generator both used), + entirely independent of libc's `rand()`/`srand()` -- not a + hypothetical risk, a specific existing line of code this would + collide with if not done carefully. +- **Verification of the table-building step itself**, before it's + ever used by a generator: for every square, every occupancy subset + of that square's relevant mask must hash to a unique index with no + collision against a different subset's *different* result (a magic + number is only valid if this holds for all subsets) -- a real gate, + independent of and prior to section 4's generator-level correctness + gates, since a bad magic number silently corrupts every downstream + query. +- **PEXT vs. classic magic multiplication -- resolved, with data, not + just reputation.** This box is a Ryzen 9 3900X (Zen 2); + `sysctl`/`dmesg.boot` confirm `BMI2` is a reported CPU feature, but + Zen 1/Zen 2 are the well-known case where AMD implements `PEXT`/ + `PDEP` in microcode rather than natively, making them dramatically + slower than the multiply-based alternative despite the flag being + present. Confirmed empirically (see prototype below), not assumed: + on this exact CPU, `_pext_u64` averaged **15.08 ns/op** vs. **0.67 + ns/op** for `(occupancy * magic) >> shift` -- **~22x slower**. + **Decision: classic multiply-based magic numbers, PEXT rejected for + this box.** + +**Preliminary validation, done (2026-09-04), before any real +`data.c`/`generate.c` code was written**: a standalone scratch +prototype, `/tmp/typhoon/magic_proto/magic_proto.c` (per CLAUDE.md, +disposable/not checked in, but kept as the reference implementation +for when this becomes load-bearing code), reimplements just enough of +`chess.h`'s 0x88/`COOR_TO_BIT_NUMBER`/`COOR_TO_BB` conventions and +`data.c`'s `InitializeRookRayTables`/`InitializeBishopRayTables` shape +to stay directly portable later, and does all of: + +1. Builds the relevant-occupancy masks (ray-to-edge minus each + direction's outermost/edge square). +2. Searches for a collision-free magic number per square per piece + type via random sparse-candidate search (`rand & rand & rand`, + standard technique) against a slow ray-walk reference -- no need + for published magic constants, since local search converged + trivially fast: **9,150,194 total candidate attempts across all 64 + rook squares, 672,021 across all 64 bishop squares**, both + effectively instant. +3. Verifies every entry found this way against the slow reference + across *every* occupancy subset of that square's mask -- the + section 2a collision-freedom gate -- with **zero mismatches across + 107,648 (square, occupancy-subset) pairs** (102,400 rook + 5,248 + bishop). +4. Reports resulting attack-table sizes: **819,200 bytes (rook)**, + **41,984 bytes (bishop)** -- both far under the "few hundred KB" + estimate above, trivial next to the ~75MB `SEARCHER_THREAD_CONTEXT`. +5. Ran the PEXT-vs-multiply benchmark above. + +This clears the section 2a infrastructure gate in isolation -- +occupancy masks, magic numbers, attack tables, and collision-freedom +verification are all now proven to work end-to-end on this exact +codebase's conventions and this exact CPU, before any of it touches +`generate.c`. What's left before `GenerateRook`/`GenerateBishop` can +be written for real: porting the prototype's search/verify/table-build +logic into `data.c` proper as a single startup-time `InitMagic()` +(called alongside `InitializeRookRayTables()`/ +`InitializeBishopRayTables()`/`InitializeKnightAttackTables()` in +`main.c`'s existing startup sequence -- see the determinism trap noted +above regarding `main.c:454`'s `srand()` call), populating real +`g_Rook*`/`g_Bishop*` globals rather than prototype-local arrays. No +offline generator tool and no hand-pasted constants are part of this +plan -- see the "computed live at engine startup" decision above for +why. + ## 3. Per-function plan Ordered by expected implementation risk/complexity, cheapest and @@ -190,44 +369,205 @@ extra-cautious overhead, it's the minimum viable rollout shape. 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. +3. **Rook/Bishop** (`GenerateRook`, `GenerateBishop`) -- **decided: magic + bitboards, not the 4-direction ray-walk.** A cheaper runtime-only + ray-walk/XOR alternative was considered (find nearest blocker per + direction via the existing `_WhoAttacksSquareBB` mechanism, XOR the + full ray against the ray-from-the-blocker to truncate it) and works, + reusing only already-verified infrastructure with zero new tables. + This is genuinely new infrastructure, not a reuse of section 2's + `GetAttacks`-era tables -- see section 2a for what had to be built + and verified before any generator code could use it. + + **Speed result, measured, not what was predicted going in: parity, + not a win, and that's an acceptable outcome.** The original + reasoning ("magic bitboards are strictly faster -- one multiply + + shift + lookup replaces a 4-direction ray walk") turned out to + undersell what a mailbox ray walk actually costs here: every square + a mailbox walk visits before hitting a blocker becomes an output + move, not wasted work, so its cost is already close to O(destination + count) -- the same order the magic lookup's post-lookup bit- + extraction loop pays. `_GenerateRookBB`'s benchmark (testgenerate.c's + `TestGenerateRookSpeed`, same interleaved-call methodology as + knight/king) measured, with the once-per-node + `bbOccupied`/`bbFriendlyOccupied` build cost already excluded from + the per-call number (best case for the bitboard side): rook on an + open file/rank in an endgame position (~13 destinations, the case + expected to show the biggest win) was **1.04x slower**, not faster; + blocked opening/middlegame positions were statistically tied + (0.99x). The magic lookup pipeline (5-7 sequential loads across + `bbOccupied`, the occupancy mask, the magic constant, the shift + constant, and a double-indirect load through + `g_RookAttackTable[cRook][index]`, plus a 64-bit multiply) turned + out to have a longer critical path than the handful of cheap, + branch-predictable, already-cache-resident `pos->rgSquare` accesses + a mailbox ray walk needs at these distances (max 7 squares/ + direction). Knight and king showed the identical near-parity pattern + for the same underlying reason (fixed small destination counts, + no repeated-query amortization to exploit) -- see their entries + above. + + **Why this doesn't kill the project**: magic bitboards' real + advantage is amortizing a table lookup's O(1) cost across *repeated* + queries against the same or changing occupancy (SEE-style attacker + detection probed many times per node, or eval mobility counts summed + over many squares) -- a shape move generation's "call once per piece + per node" pattern never gets to exploit. That advantage is already + real and already banked: `GetAttacks`/SEE (`MIGRATION.md`) measured + roughly a 50% win from the exact same magic-table technique, and + eval's mobility counting is expected to see a similar win for the + same repeated-query reason, once undertaken. Rook/bishop/queen's + *move-generation* migration is therefore worth finishing for section + 6's stated end goal (full mailbox retirement) even at speed parity, + not for a per-function speed win that was never actually the point + for this particular piece-type/call-site combination. Section 7's + retirement criteria ("no solve-count regression," `match_play.py` + gate) still apply in full -- parity is acceptable, an actual + regression is not. 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. + two-pass structure). **Speed result: the one piece type with a + genuine, if position-dependent, per-function win** -- queen combines + 8 directions (rook's 4 + bishop's 4) in mailbox vs. two magic + lookups in bitboard, so mailbox pays roughly double rook/bishop's + own per-direction dispatch overhead while bitboard's fixed cost only + grows modestly; measured 0.71x (opening, queen fully blocked -- the + per-direction dispatch overhead dominates when there's nothing to + enumerate), 0.99x (middlegame), 1.09x (endgame, open board -- + extraction-loop cost reasserts the same pattern rook/bishop/knight/ + king all showed). + +**Dispatch-layer finding, found after all four piece types above +landed -- the real payoff this migration was actually hiding, not in +any individual generator function:** `_GenerateAllMoves`'s own outer +loop (`pos->cNonPawns[side][]`, a flat list mixing every non-pawn piece +type together since pieces are added/removed via swap-with-last, so +there's no contiguous per-type range to slice) dispatches via +`JumpTable[pos->rgSquare[c].pPiece]` -- an indirect call whose target +changes almost every iteration as the loop walks across mixed piece +types, close to the worst case for a CPU's indirect-branch predictor. +**Every benchmark above called its `_Generate*BB` function directly, +bypassing `JumpTable` entirely** -- none of those numbers ever +measured, or could benefit from removing, this cost. + +`pos->bbPieces[side][KNIGHT/BISHOP/ROOK/QUEEN]` sidesteps the problem +`cNonPawns` has: each piece type already has its own bitboard, so a +per-type bit-extraction loop can call `_GenerateKnightBB`/ +`_GenerateBishopBB`/`_GenerateRookBB`/`_GenerateQueenBB` **directly, by +name** -- a statically-known, likely-inlinable call, no function +pointer anywhere. `_GenerateAllMovesBB` (`generate.c`, exposed non- +static for benchmarking) implements exactly this: four per-type bit- +extraction loops plus a direct king call (king has no bitboard of its +own, a single square is already all `GetAttacks` ever needed), pawns +unchanged (copied verbatim from `_GenerateAllMoves`'s tail, out of +scope per step 5 below). Forked as a **whole separate function**, not +a branch nested inside `_GenerateAllMoves`, and swapped in via a +`#define _GenerateAllMoves _GenerateAllMovesBB` (matching `chess.h`'s +`GetAttacks` precedent) gated on **all five** piece-type toggles being +defined together -- a partial-rollout mix still needs +`_GenerateAllMoves`'s `cNonPawns`/`JumpTable` path, since only that +path knows how to fall back to a still-mailbox piece type while also +finding already-migrated ones in the same mixed list; +`_GenerateAllMovesBB` does not attempt to support partial rollout. + +**Measured result (`testgenerate.c`'s `TestGenerateAllMovesSpeed`, +same interleaved methodology, but comparing whole-node generation, not +a single piece): a genuine win**, in the positions that actually +exercise the mechanism: + +``` +opening : mailbox 329 cycles/call, BB dispatch 255 cycles/call (0.77x) +middlegame: mailbox 431 cycles/call, BB dispatch 411 cycles/call (0.95x) +endgame : mailbox 391 cycles/call, BB dispatch 432 cycles/call (1.10x) +``` + +Opening/middlegame (dense, many mixed piece types -- exactly where +`JumpTable` has to jump between wildly different targets almost every +iteration) show a real win, up to 23%. The endgame test position +(sparse -- few total pieces, so few dispatch decisions for +misprediction to cost anything on) regresses slightly, consistent with +the per-function findings above (the few pieces present are on a wide- +open board, paying the same per-call fixed-lookup cost that lost in +every isolated open-position benchmark). Net story: the dispatch-level +win dominates in typical richer positions; the per-generator cost +dominates in sparse/wide-open ones -- a coherent, not noisy, result. + +Correctness: perft (`TestMoveGenerator`) passes both against the +toggle-free baseline (`_GenerateAllMoves` under its own name, unrenamed +since the macro-swap condition is false) and against a build with all +five piece-type toggles defined together (macro-swap active, +`_GenerateAllMovesBB` substituted at all four of `GenerateMoves`'s call +sites). + +This is the actual justification for finishing Part A even setting +aside individual-function parity -- the win was always going to live +in the dispatch layer once enough piece types migrated to make +`pos->bbPieces`-driven iteration possible at all, not in any one +generator beating mailbox on its own. +5. **Pawns** (`GenerateWhitePawn`/`GenerateBlackPawn`) -- **implemented, + done last as planned, but not the way originally sketched above.** + The pre-implementation guess (a new `g_PawnAttackTargetBB[2][128]` + per-square table, generated one pawn at a time like the other five + piece types) turned out to be the wrong shape entirely. Confirmed + via `~/crafty/movgen.c` before implementing (the standard technique, + not something specific to this codebase): `pos->bbPawns[side]`'s + bits already live in dense `rank*8+file` space + (`COOR_TO_BIT_NUMBER`), so shifting the *entire* bitboard by 8 moves + every pawn of that side forward one rank *simultaneously* -- no + per-square table, no per-pawn loop to find destinations, only to + emit the resulting moves. `_GenerateAllPawnMovesBB` + (`generate.c`) generates an entire side's pawn moves in one call: + + - **Single push**: `(bbPawns >> 8) & empty` for White, `<< 8` for + Black -- this engine's square numbering has A8 = bit 0 (opposite + of Crafty's convention), so White's forward direction is a + *right* shift here, not left; got this from re-deriving the + `RANK`/`RANK1`/`RANK8`/`A1`/`A8` macros directly rather than + assuming Crafty's shift directions would carry over. + - **Double push**: mask the single-push *destination* bitboard + against `BBRANK[3]`/`BBRANK[6]` (did this pawn's single push land + on rank 3/6, only possible starting from rank 2/7) before shifting + again -- same technique Crafty uses (`padvances2`), no per-square + starting-rank table needed, reusing the already-existing `BBRANK[]` + table instead of building a new one. + - **Captures**: `+-7`/`+-9` diagonal shifts (one rank plus one file), + each masked against the *opposite* file (`BBFILE[0]`/`BBFILE[7]`) + before shifting, to stop a same-row wraparound -- an h-file pawn's + naive `>>7` would otherwise silently land back on the same row's + a-file, a silent-wrong-answer trap, not an out-of-range index. + Verified against `bbEnemy` (occupied minus friendly), same + convention as the other five generators. + - **En passant**: deliberately *not* bulk -- checked directly (do + either of the two squares diagonally behind `pos->cEpSquare` hold + one of this side's pawns), since it's at most one event per node + and not worth deriving a whole extra masked bitboard for. + - **Promotions**: confirmed correctly not bitboard-reducible, exactly + as predicted -- `_AddPromote`'s 4-piece-type enumeration loop is + unchanged, just reached via `RANK8(cTo) || RANK1(cTo)` on each + extracted destination instead of a per-square rank check. + + Gated behind its own `GENERATE_PAWN_BITBOARD` toggle (independent of + the other five, per section 6), wired into both `_GenerateAllMoves`'s + and `_GenerateAllMovesBB`'s pawn tails. + + **Correctness**: perft (`TestMoveGenerator`) clean in a `TEST=1` + build, and clean in a `TEST=1 DEBUG=1` build exercising every + `ASSERT` added (including sanity checks on the reverse-shift + origin-square recovery and capture-color validation) -- first-try + correct on genuinely hand-derived shift/mask arithmetic, which the + perft harness (externally-verified leaf counts, including a + castling/en-passant-heavy position) would have caught immediately + had the direction, shift amount, or edge mask been wrong in either + color. + + **Speed**: not yet isolated-benchmarked the way the other five were + (no `TestGenerateAllPawnMovesSpeed` written) -- worth doing before + this toggle is considered for default-on, but lower priority than + getting section 4's full gate run at least once across everything + implemented so far. ## 4. Correctness verification @@ -324,28 +664,476 @@ functions.** Checked directly -- `GenerateKnight`/`GenerateRook`/ 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: +toggle above only ever covers the *not-in-check* path. + +**Decided: this is a two-part project, not seven-vs-eight targets in +one pass.** The end goal is full mailbox retirement in `generate.c`, +so `_GenerateEscapes` is in scope -- but as **Part B**, done only after +**Part A** (the seven not-in-check generators, sections 3/4/5/7 as +written) is fully landed, retired, and re-baselined into +`head_reference/`. Reasons to sequence rather than parallelize: + +- Part A already establishes every piece of infrastructure Part B + needs (segment-marking mechanism, per-type toggle pattern, perft + + move-set comparison harness shape, `testgenerate.c` itself) -- + building `_GenerateEscapes`'s bitboard version first, or alongside, + would mean designing that infrastructure against an unusual, + narrower-scoped caller (single-checker blocking/capturing moves, + possibly king moves out of check) before it's been proven against + the general case. +- `_GenerateEscapes` is called on a minority of nodes (most positions + aren't in check), so it's correctly the lower-priority half of the + NPS win -- no reason to hold Part A's already-larger win hostage to + Part B's design work. +- Keeps the retirement-criteria checklist (section 7) honest per the + existing principle of not letting one target's clean bill of health + lower the bar for another -- Part B gets its own full pass through + that checklist once it starts, not a discount for arriving after + Part A proved out the pattern. + +Part B's own design questions were left undecided in an earlier draft +of this document, to be scoped only after Part A landed -- **that +scoping pass happened (2026-09-04, before Part A's own section 4 gate +was run, at the user's direction) and is written up in section 6a +below.** `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 only +needed to cover the not-in-check path for Part A; Part B's own +correctness gate will need to exercise the `fInCheck` branch +specifically when implementation starts. + +## 6a. Part B design (`_GenerateEscapes`) + +Traced end to end (`_FindUnblockedSquares`, `_GenerateEscapes`, all six +`SaveMeFoo` functions, the `BLOCKS_THE_CHECK` macro, `IsAttacked`, +`_WhoAttacksSquareBB`) before writing any code, same discipline as +Part A's per-function plan. Two separate findings came out of this, +one a scoping correction and one a design that's a genuine +simplification, not just a reimplementation. + +**Scoping correction: `_FindUnblockedSquares` is not actually +`_GenerateEscapes`'s precondition.** It looked that way structurally +(a "queen standing on a square, walk all 8 rays" ray-walk, same shape +`_GenerateRookBB`/`_GenerateBishopBB` already use), but tracing its +call sites shows it runs on **every** `GenerateMoves` call (all four +`GENERATE_*` cases), keyed off the *opposing* king's square, building a +per-square reverse-pointer table (`pStack->sUnblocked[uPly][]`) that +`WouldGiveCheck` later uses to cheaply detect discovered checks -- +nothing specific to the in-check path. It's a legitimate, separate +bitboard-migration candidate (same ray-walk shape, its own `#define` +toggle), but it does **not** belong inside Part B's scope; recording it +here so it isn't lost, not because it's being done now. + +**Phase 1 (king flight) -- a genuine simplification, not just a +port.** Today's mailbox code (`_GenerateEscapes`'s first loop) walks +`g_iQKDeltas`, calls mailbox `IsAttacked(c, pos, enemy)` per candidate +square, then runs a **second, manual loop over every checker** +specifically to catch a case `IsAttacked` gets wrong: `IsAttacked` has +no way to test against a hypothetical occupancy, so a candidate escape +square can come back "safe" purely because the king's own *still +physically present* body is blocking a slider's ray from extending +past it -- the classic x-ray/discovered-attack-when-stepping-back +problem. The existing code works around this by hand, checking each +checker's direction against each candidate square's direction from the +king. + +`_WhoAttacksSquareBB` (`see.c`, currently `static`, would need +exposing) already takes an explicit `bbOccupied` parameter for exactly +this reason -- it was built for `GetAttacks`, not for this, but the +capability is already there. The fix: compute +`bbOccupiedWithoutKing = pStack->bbOccupied & ~COOR_TO_BB(cKing)` once, +then for each candidate in `g_KingAttacksBB[cKing] & +~bbFriendlyOccupied`, test `_WhoAttacksSquareBB(pos, c, enemy, +bbOccupiedWithoutKing) == 0` (plus a separate pawn-attack check via +`g_PawnAttackOriginBB`, since `_WhoAttacksSquareBB` deliberately +excludes pawns -- see its own header comment). **This doesn't just +port the existing logic, it deletes the manual per-checker x-ray loop +entirely** -- testing against king-vacated occupancy handles that case +for free, because a slider whose ray was blocked only by the king's own +body will now correctly show up as attacking `c` if `c` is still on +that ray. + +**Phase 2 (block-or-capture by a non-king piece) -- collapses six +per-square-loop functions to one AND each.** Today, `SaveMeKnight`/ +`SaveMeBishop`/`SaveMeRook`/`SaveMeQueen`/`SaveMeWhitePawn`/ +`SaveMeBlackPawn` each re-walk their piece's own move pattern and test +`(c == cAttacker) || BLOCKS_THE_CHECK(c)` per candidate square. The +bitboard design collapses this to one precomputed mask, intersected +once per piece instead of tested once per square: + +- `bbTargetMask` = the checker's own square (a capture always resolves + check) OR, when the checker is a slider, every square strictly + between it and the king (a block also resolves check). The + "squares between two aligned squares" bitboard is a well-known + trick, and it costs nothing new here: `bbBetween = RookAttacks(cKing, + occ) & RookAttacks(cAttacker, occ)` (rook or bishop table, whichever + the checker's line matches) -- each square's magic-table attack + bitboard already reaches exactly to its nearest blocker in every + direction, so ANDing both sides' attack sets from each end gives + precisely the empty segment between them. This is a **direct + consumer of `InitMagic()`'s tables for something other than move + generation** -- the first sign the magic-table investment pays off a + third time (after `GetAttacks`/SEE and this), independent of eval + mobility. +- Once `bbTargetMask` is computed, every already-migrated piece's + `SaveMeFoo` collapses from a per-square loop to one line: `bbDest = + <that piece's already-computed attack bitboard> & bbTargetMask` + (knight: `g_KnightAttacksBB[c] & ~bbFriendlyOccupied & bbTargetMask`; + rook/bishop/queen: the same magic lookups `_GenerateRookBB`/etc. + already perform, ANDed with `bbTargetMask` instead of just + `~bbFriendlyOccupied`). No per-square `BLOCKS_THE_CHECK` branch + anywhere -- an actual structural simplification versus Part A's own + generators, which still needed a per-square classification step. +- Pawns: same bulk shift-and-mask technique as + `_GenerateAllPawnMovesBB`, with each of the four move-category + bitboards (single push/double push/capture-left/capture-right) ANDed + against `bbTargetMask` before extraction. En passant stays a direct, + narrow special case exactly as today -- `SaveMeWhitePawn`'s existing + comment already notes it only applies when the double-jumping pawn + *is* the checker, genuinely rare, not worth deriving a bulk mask for. + +**Missed in the first pass of this section, caught by the user while +Phase 1 was being implemented: Phase 2 has the exact same +dispatch-layer problem `_GenerateAllMoves` had, and the fix is the +same pattern.** The bullets above only addressed collapsing each +`SaveMeFoo`'s *internal* per-square loop -- they didn't address the +*outer* loop that calls them: + +```c +for (u = 1; u < pos->uNonPawnCount[pos->uToMove][0]; u++) { + cDefender = pos->cNonPawns[pos->uToMove][u]; + ... + (JumpTable[p])(pStack, pos, cDefender, cKing, c); +} +``` + +`pos->cNonPawns[side][]` mixes every non-pawn piece type together +(same reason as `_GenerateAllMoves`'s loop -- pieces are added/removed +via swap-with-last, no contiguous per-type range to slice), so +`JumpTable[p]` is the identical indirect-call-with-changing-target +pattern that `_GenerateAllMovesBB` was built to eliminate. The fix is +the same one, applied here: a `_GenerateEscapesBB`-style function +loops `pos->bbPieces[side][KNIGHT/BISHOP/ROOK/QUEEN]` directly (once +`bbTargetMask` is computed) and calls each specific `SaveMeFooBB` +function **by name** -- no function pointer, same +statically-known-call-target win `_GenerateAllMovesBB` already +demonstrated (measured up to 23% faster in dense positions, section +3's writeup after step 4). Given Part A's `_GenerateAllMovesBB` +already proved this exact mechanism out, expect Part B's dispatch fork +to pay off the same way, for the same reason -- worth building +regardless of whether each individual `SaveMeFooBB`'s per-square-loop +collapse (the bullets above) shows a win in isolation, same lesson +Part A's per-function benchmarks already taught. + +**What does not change (behaviorally)**: `ExposesCheck`'s pin-detection +*outcome* is unchanged -- called per surviving candidate move the same +way the mailbox `SaveMeFoo` functions call it today, including its own +documented bug (a pinned piece's capture can still slip through as +pseudo-legal). Not in scope to fix, per section 1's non-goal against +becoming more legal-aware than the code being replaced; must replicate +bug-for-bug like everything else in this migration. **`ExposesCheck`'s +own implementation, however, turned out to be a separate, higher-value +bitboard target in its own right** -- see section 6b, added after +finishing Phase 1/Phase 2 and auditing the rest of `movesup.c` at the +user's direction. The `GetAttacks(&rgCheckers, ...)` call that finds +who's checking is unchanged -- already covered by the existing +`GETATTACKS_BITBOARD` toggle from `MIGRATION.md`, orthogonal to this +work. + +Toggle granularity for Part B ended up being two independent flags, +`GENERATE_ESCAPES_KING_BITBOARD` (Phase 1) and +`GENERATE_ESCAPES_BLOCK_BITBOARD` (Phase 2) -- both implemented, see +their own writeups above. A separate whole-function `_GenerateEscapesBB` +fork (mirroring `_GenerateAllMovesBB`) turned out to be unnecessary: +Part A's fork was required because five independent piece-type toggles +all had to agree before `pos->bbPieces`-driven iteration became +possible at all; Phase 1 and Phase 2 are independent sections of the +same function, not five orthogonal toggles gating one shared loop, so +two `#if` blocks inside `_GenerateEscapes` deliver the identical +dispatch-elimination win (Phase 2's `cNonPawns`/`JumpTable` loop, +caught by the user while Phase 1 was landing) without needing a +parallel top-level function. + +## 6b. `movesup.c` survey -- what else is bitboard-eligible + +Prompted by a direct question after Phase 1/Phase 2 landed: `generate.c` +isn't the only file with mailbox board-query helpers. `movesup.c` holds +several, called from all over the engine (`search.c`, `move.c`, +`eval.c`, `root.c`, `dynamic.c`, `san.c`), not just from move +generation. Every function in the file was read and categorized -- +three real categories emerged, not two, and the exercise surfaced a +scoping correction to this document's own "retire the mailbox" framing. + +**Category A -- bitboard-eligible, and it matters for performance:** + +- **`IsAttacked`** -- corrects an earlier (wrong) read of this same + function from earlier in this session: its *direct* callers + (`san.c`, `move.c`) are cold castling-through-check checks, but + `InCheck` is a thin wrapper around it, and `InCheck` has **70 call + sites** across `search.c`/`move.c`/`eval.c`/`root.c`/`dynamic.c` -- + called constantly through search, not a cold path at all. Design: + `_WhoAttacksSquareBB(pos, cTest, uSide, bbOccupied) != 0` plus a + separate pawn-attack check via `g_PawnAttackOriginBB` (same pattern + Phase 1's king-flight code already uses inline). +- **`InCheck`** -- a two-line wrapper around `IsAttacked`. Benefits + automatically once `IsAttacked` has a bitboard version; no separate + design needed. +- **`ExposesCheck`** -- called from `MakeMove` (`move.c`) on + essentially every move actually played during search, the pin- + legality safety net every generator's header comment references. + Design: exclude the hypothetically-removed square from occupancy + (`bbOccupied & ~COOR_TO_BB(cRemove)`), magic-lookup the attack set + from `cLocation` against that occupancy, mask to the single ray + through `cRemove` via `g_RookRayToEdge`/`g_BishopRayToEdge` (so an + unrelated attacker on a different ray through `cLocation` can't + falsely register), then apply the same enemy-color/piece-type check + the mailbox version does on whatever single square survives. +- **`FasterExposesCheck`** -- identical call shape to `ExposesCheck` + minus the initial alignment pre-check (caller already knows exposure + is geometrically possible); same bitboard design, minus the early-out. +- **`ExposesCheckEp`** -- the en passant variant, checking whether + capturing en passant would expose check via the rank the capturing + and captured pawns both sat on. Same trick, with *two* squares + excluded from occupancy instead of one (the moving pawn's origin and + the captured pawn's square). + +**Category B -- bitboard-expressible, but converting buys nothing:** +`SanityCheckMove`, `_SanityCheckPieceMove`, `_SanityCheckPawnMove` -- +all `DEBUG`-only, called exclusively inside `ASSERT(SanityCheckMove( +...))`, compiling to nothing in a release build. `_SanityCheckPieceMove`'s +"is the path from `cFrom` to `cTo` clear" ray-walk is actually the +*cleanest* possible bitboard reduction found anywhere in this survey +(`_RookAttacksBB(cFrom, occ) & COOR_TO_BB(cTo) != 0` -- one lookup, one +bit test, simpler than anything needing a between-squares mask) -- but +since none of these three ever execute in release, there is no +performance to gain from converting them. Worth doing only if/when the +structural "retire mailbox reads" goal below is pursued, never as a +speed item. + +**Category C -- no mailbox-vs-bitboard axis exists at all:** +`LooksLikeFile`/`LooksLikeRank`/`LooksLikeCoor`/`StripMove`/ +`LooksLikeMove` (pure string parsing -- most don't even take a +`POSITION*`); `SelectBestWithHistory`/`SelectBestNoHistory`/ +`SelectMoveAtRoot` (scan an already-generated `MOVE_STACK` by score/ +history, never touch board occupancy); `Perft`/`PerftCommand` (pure +recursive driver over `GenerateMoves`/`MakeMove`/`UnmakeMove`, no +direct board access). None of these read `pos->rgSquare` today and +none would need to under any board-representation change. + +**Clarification on Category B and C's `MOVE`-focused members** +(`SanityCheckMove` and friends, `LooksLikeMove`/`StripMove`): these +take or produce a `MOVE`, and `MOVE`'s `cFrom:8`/`cTo:8` encoding is +already frozen by section 1's existing non-goal (the same exclusion +`MIGRATION.md` made originally, for the same reason -- a much bigger, +separate project). Their *internals* could still switch to bitboard +board-queries (Category B's point above), but their signatures and +purpose -- validating/parsing a `MOVE` against a `POSITION` -- never +change regardless of how the board itself is represented. These were +never "generator helpers" in the sense `IsAttacked`/`ExposesCheck` are; +worth stating precisely so a future pass doesn't conflate "migrate +board queries to bitboards" with "change the `MOVE` representation," +two entirely different and already-separately-scoped projects. + +**Scoping correction to this document's own "retire the mailbox" framing, +surfaced by actually doing this survey**: even Category B's functions, +and every already-migrated `_Generate*BB` function in Part A (knight/ +king/rook/bishop/queen/pawn), still call `pos->rgSquare[c].pPiece` to +answer "what's on this destination square" for move classification +(quiet vs. capture). Bitboards answer "where are my knights" cheaply; +they don't answer "what's on square X" without a per-piece-type +membership scan across up to 8 bitboards. This means **`pos->rgSquare[]` +is almost certainly not fully removable**, no matter how much of +`generate.c`/`movesup.c` migrates to bitboard-driven logic. "Retire the +mailbox" (this document's stated end goal, section 6/7) should be read +as retiring the mailbox *move-generation and board-query loops*, not +literally deleting the square-indexed array -- every generator, bitboard +or not, depends on it for O(1) single-square classification, and that +dependency doesn't go away just because the *destination-finding* logic +became bitboard-native. + +**`ExposesCheck`/`FasterExposesCheck`/`ExposesCheckEp` -- implemented, +debugged, and validated (2026-09-04).** `movesup.c` now has +`ExposesCheckBB`/`FasterExposesCheckBB`/`ExposesCheckEpBB`, gated behind +a single `EXPOSESCHECK_BITBOARD` toggle (`#define`-swapped in via +`chess.h`, same pattern as `GetAttacks`). One real wrinkle in the +macro-swap itself: unlike `GetAttacks` (a real asm symbol living in a +*different* file, so the macro never touches its own definition), these +three mailbox functions are defined in the *same* file as their BB +counterparts -- the macro would otherwise rename `movesup.c`'s own +function definitions too, colliding with the real `*BB` symbols. Fixed +with `#undef` immediately after `#include "chess.h"`, restoring the +real names for this file's own definitions while every other +translation unit still sees the macro-renamed calls. + +**Two real bugs found and fixed** getting this correct, both caught by +the existing correctness harness exactly as designed, not by manual +inspection: + +1. **Ray-direction sign was backwards on the first attempt.** + `CHECK_DELTA_WITH_INDEX(cLocation - cRemove)`'s actual convention + (confirmed by reading `InitializeVectorDeltaTable`'s table- + construction loop in `data.c`, not by guessing) is "the direction to + step from `cLocation` *toward* `cRemove`" -- the first attempt + negated this unnecessarily. Caught by `TestSan` failing on a + castling/pin-disambiguation test case. +2. **A more fundamental design flaw**, caught only after the sign fix, + by a `DEBUG`-build assertion (`movesup.c:117`, + `ASSERT(!IS_EMPTY(xPiece))`) rather than a leaf-count mismatch: the + first design ANDed the *full* multi-directional magic attack + bitboard against a single-direction ray mask, assuming this would + isolate exactly one bit (the nearest blocker) or zero. Wrong -- an + *unblocked* ray's attack bitboard contains every empty square out to + the edge, so the intersection can contain many bits, and + `FastFirstBit` on that set picks the lowest absolute square index, + which is not necessarily nearest to `cLocation` (bit-index order and + "distance from origin" only coincide for one of the two directions + along any given ray). Fixed by abandoning the magic-lookup approach + for this specific query entirely and mirroring + `_WhoAttacksSquareBB`'s (`see.c`) already-proven nearest-blocker + technique instead: isolate the lowest set bit for a "positive" + direction (`bb & -bb`) or the highest set bit for a "negative" + direction (`1ULL << (FastLastBit-1)`), using the existing + `g_RookRayPositiveDir`/`g_BishopRayPositiveDir` tables to know which. + New shared helper: `_NearestBlockerAlongRayBB`. + +**Validation**: perft-based hand-crafted repros (a straight-line rook +pin, a diagonal bishop pin, both en-passant-discovered-check example +FENs already in `generate.c`'s comments) all matched baseline exactly +once both fixes landed -- but the strongest confirmation came from +external ground truth: **chessprogramming.org's "Position 4"** +(`8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -`, chosen deliberately for its +heavy en-passant/pin content) matched the published reference exactly +to depth 8, and **"Kiwipete"** +(`r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq -`) matched +to depth 6 -- both are standard, deliberately adversarial community +test positions specifically because they catch exactly this class of +en-passant/pin/castling-legality bug. A separate, intermittent +`TestSearch` failure (hits `recogn.c`, `probe.c`, or `util.c` on +different runs, always inside the material-recognizer/tablebase- +agreement or PV-formatting subsystem, never inside move generation) +was investigated in parallel and is **not** related to this work -- +`_SanityCheckRecognizers`'s tablebase cross-check calls `ProbeEGTB` +directly against raw position bitboards/material counts, with no +dependency on `MakeMove`, `ExposesCheck`, or move generation at all. +Pre-existing, `GenerateRandomLegalPosition`-triggered flakiness in the +recognizer subsystem, out of scope for this document. + +`IsAttacked`/`InCheck` (the other Category A target from this section) +remain unstarted. + +**All nine toggles combined, verified together for the first time +(2026-09-04): a third real bug found, this time in the test harness +itself, not in any of this migration's code.** Running every Part A/ +Part B/`EXPOSESCHECK_BITBOARD` toggle simultaneously (the first time +this combination had been tried -- everything up to this point was +tested individually or in small groups) surfaced an intermittent +segfault in `TestSearch`'s random-position loop, distinct from the +already-diagnosed `recogn.c`/`util.c` recognizer flakiness above. Root +cause: `GenerateRandomLegalPosition` (`testsup.c`) `memset`s the whole +`POSITION` to zero and explicitly resets `cPawns`/`cNonPawns` to +`ILLEGAL_COOR` afterward, but never touches `cEpSquare` -- leaving it +at `0x00` (square A8, a real on-board square) instead of the "no en +passant" sentinel. Every single randomly-generated test position +therefore had a bogus "en passant available on a8" flag active. Both +mailbox and bitboard pawn code trust this field unconditionally (by +design -- it's supposed to be set only by `MakeMove` after a genuine +double-pawn-jump); the bitboard generators +(`_GenerateAllPawnMovesBB`/`_SaveMeAllPawnMovesBB`) gate their en +passant handling on `IS_ON_BOARD(cEpSquare)` *proactively*, once per +side per node, versus mailbox's more incidental per-pawn +`cTo == cEpSquare` check -- meaning the bitboard path exercises this +latent test-harness bug far more consistently than mailbox ever did, +which is how a pre-existing harness defect turned into a new-looking +crash. Whenever a real pawn happened to occupy b7 (the one square +diagonally behind the bogus a8 target) in a random position, a garbage +"en passant capture" move got constructed and fed to `MakeMove`, +corrupting position state. Fixed with one line +(`pos->cEpSquare = ILLEGAL_COOR;`) added right alongside the existing +`cPawns`/`cNonPawns` resets in `GenerateRandomLegalPosition`. Also +added FEN logging to `TestSearch`'s random-position loop +(`Trace("TestSearch position %lu/20: %s\n", ...)`, via `PositionToFen`) +so a future intermittent failure has its exact triggering position +captured automatically, matching `debug_smoke_test.sh`'s existing +convention -- this fix took real time to find precisely because the +triggering position wasn't logged anywhere. + +Post-fix: 15/15 clean runs with all nine toggles combined (`TEST=1`, +no `DEBUG`), plus clean `DEBUG`-build runs beforehand. `precommit_check.sh` +also passes clean on the untouched, all-toggles-off default path, +confirming none of this migration's extensive edits affected anyone +not opting in. + +**Whole-engine `sd10` curated-suite check against `head_reference/`, +with all nine toggles combined**: `ecm_ringers` 10/11 and +`ecm_confident_quick` 84/90 both match `head_reference` exactly. +`ecm_hard_quick` showed 25/90 against a recorded baseline of 28/90 -- +investigated and **confirmed unrelated to this migration**: rebuilding +plain current-HEAD mailbox (every toggle off) reproduces the identical +25/90, proving the 3-solve delta comes entirely from intervening, +non-toggle-gated commits that landed between `head_reference`'s +baseline and current HEAD (`5c8d794` "Fix passed-pawn bitboard bit-clear +bug, LMR gate coupling..." and `a8806ad` "Fix draw-score bug in +hash-hit path" are the likely candidates, both already-committed, +default-on, and unrelated to move generation). **Net result: zero +solve-count regression attributable to this migration** across all +three curated suites. + +**`IsAttacked`/`InCheck` -- implemented, tested properly this time, and +a genuine speed win.** `movesup.c` now has `IsAttackedBB`/`InCheckBB`, +gated behind `ISATTACKED_BITBOARD` (same three-way `#define`-swap +pattern as `EXPOSESCHECK_BITBOARD`, including the same `#undef` fix in +`movesup.c` for the same same-file-definition reason). Design: +`_WhoAttacksSquareBB(pos, cTest, uSide, bbOccupied) != 0` plus a +separate pawn check via `g_PawnAttackOriginBB` (mirroring exactly what +Phase 1's king-flight code already did inline, now factored into a +reusable, directly-testable function). + +**One real ordering bug caught before it shipped, not after**: the +first draft placed the `#define IsAttacked IsAttackedBB` block *before* +the real mailbox function's own declaration in `chess.h` -- when the +toggle is active, that ordering means the mailbox declaration line +itself gets macro-substituted too, so the plain name `IsAttacked` is +never actually declared anywhere under that name. Harmless as long as +nothing needs to call the mailbox version by its real name explicitly +-- which is exactly what the new comparison-harness test does, and +which is why the bug surfaced immediately as a compile error rather +than shipping silently. `GetAttacks`'s existing three-way block already +gets this ordering right (real function declared first, unconditionally, +*then* the `#define`); `ExposesCheck`'s block happened to already be +correct too (its mailbox declarations pre-dated the `#define` insertion +point). Fixed by reordering to match `GetAttacks`'s pattern exactly. -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. +**Tested properly from the start this time** -- unlike `ExposesCheck`, +which shipped without a direct comparison harness and had to be +debugged after the fact via `TestSan`/perft/`DEBUG`-assert failures: +`TestIsAttackedBB` (`testsee.c`, modeled directly on `TestGetAttacks`) +compares `IsAttacked` vs. `IsAttackedBB` and `InCheck` vs. `InCheckBB` +across `GenerateRandomLegalPosition`'s full 20,000-position sweep, every +square, both colors -- **clean on the first try**, no debugging odyssey +required. Also benefits for free from `testmove.c`'s pre-existing +`TestIsAttacked` (a curated table of tricky attacker-geometry fixed +positions -- knight forks, pawn attacks, blockers, x-rays, pins) -- +since that test calls the plain `IsAttacked`/`InCheck` names, the +`ISATTACKED_BITBOARD` toggle routes it through the bitboard version +too, for free, no changes needed to that test. -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. +**Speed**: a genuine, consistent win, unlike most of Part A -- +`TestIsAttackedBB`'s isolated benchmark measured **0.73x-0.93x of +mailbox** across opening/middlegame/endgame. Makes sense structurally: +mailbox `IsAttacked` loops over *every* one of `uSide`'s non-pawn +pieces doing an alignment check each time (O(piece count)), while +`_WhoAttacksSquareBB` gets O(1) knight/king lookups plus an early bulk +"is anything even aligned with this square at all" check +(`g_RookRayAll`/`g_BishopRayAll`) before paying for any per-direction +work -- a real algorithmic difference, not just a constant-factor one, +unlike move generation's per-square walks where mailbox's per-square +work was already close to minimal. -## 7. Retirement criteria +Category A (section 6b) is now fully implemented: +`ExposesCheck`/`FasterExposesCheck`/`ExposesCheckEp` and +`IsAttacked`/`InCheck` both done, both correctness-verified, one with +a genuine speed win and one at parity-ish-but-cleaner-tested. `movesup.c`'s +survey from earlier in this section is fully worked through. Per piece type, only delete that type's mailbox generator function after **all** of: diff --git a/src/chess.h b/src/chess.h index 4bc3464..ed903a5 100755 --- a/src/chess.h +++ b/src/chess.h @@ -787,6 +787,30 @@ typedef struct _MOVE_STACK ULONG uEnd[MAX_PLY_PER_SEARCH]; MOVE mvHash[MAX_PLY_PER_SEARCH]; GENERATOR_FLAGS sGenFlags[MAX_PLY_PER_SEARCH]; + + // Scratch, computed once per _GenerateAllMoves call (not per + // generator-function call) when any GENERATE_*_BITBOARD toggle is + // active -- every bitboard-backed piece-type generator for the + // side to move needs "which squares does pos->uToMove already + // occupy" (to AND off as illegal destinations), and rebuilding it + // from pos->bbPieces/bbPawns freshly inside each generator call + // was measured as real, avoidable overhead (board_representation/ + // MOVEGEN_MIGRATION.md section 5's knight benchmark showed a net + // slowdown vs. mailbox until this was hoisted out). Direct callers + // of a _Generate*BB function outside of _GenerateAllMoves (e.g. + // testgenerate.c's benchmark/correctness harness) must set this + // themselves first -- it is not implicitly valid. + BITBOARD bbFriendlyOccupied; + + // Same idea as bbFriendlyOccupied, for the slider (rook/bishop/ + // queen) magic-bitboard generators: full-board occupancy, both + // sides, needed to index into g_RookAttackTable/g_BishopAttackTable + // (the magic lookup answers "attacks given this exact occupancy," + // not "attacks given only my own pieces"). Computed once per node + // by _GenerateAllMoves when any GENERATE_ROOK_BITBOARD/ + // GENERATE_BISHOP_BITBOARD toggle is active, same amortization + // reasoning as bbFriendlyOccupied. + BITBOARD bbOccupied; } MOVE_STACK; @@ -1827,6 +1851,42 @@ ExposesCheckEp(POSITION *pos, COOR cBlock, COOR cKing); +// board_representation/MOVEGEN_MIGRATION.md section 6b +COOR +FasterExposesCheckBB(POSITION *pos, + COOR cRemove, + COOR cLocation); + +COOR +ExposesCheckBB(POSITION *pos, + COOR cRemove, + COOR cLocation); + +COOR +ExposesCheckEpBB(POSITION *pos, + COOR cTest, + COOR cIgnore, + COOR cBlock, + COOR cKing); + +// Three-way choice matching GetAttacks's own pattern (MIGRATION.md +// section 6): EXPOSESCHECK_BITBOARD defined -> the BB versions above; +// else the mailbox versions declared right above this block. +#if defined(EXPOSESCHECK_BITBOARD) +#define ExposesCheck ExposesCheckBB +#define FasterExposesCheck FasterExposesCheckBB +#define ExposesCheckEp ExposesCheckEpBB +#endif + +// Real mailbox declarations first, unconditionally, so the plain names +// "IsAttacked"/"InCheck" are always genuinely declared -- the #define +// below only affects *later* call sites in files that include this +// header after this point, matching GetAttacks's own three-way-choice +// pattern (chess.h, `GetAttacks` block) exactly. Declaring these after +// the #define instead (an earlier mistake here, caught by testsee.c's +// TestIsAttackedBB needing to call the real mailbox function by name) +// would macro-substitute this very declaration too, leaving the real +// name never actually declared anywhere. FLAG IsAttacked(COOR cTest, POSITION *pos, ULONG uSide); @@ -1834,6 +1894,20 @@ FLAG InCheck(POSITION *pos, ULONG uSide); FLAG +IsAttackedBB(COOR cTest, POSITION *pos, ULONG uSide); + +FLAG +InCheckBB(POSITION *pos, ULONG uSide); + +// ISATTACKED_BITBOARD defined -> the BB versions above resolve plain +// "IsAttacked"/"InCheck" call sites from here on; else the mailbox +// versions declared just above stay live. +#if defined(ISATTACKED_BITBOARD) +#define IsAttacked IsAttackedBB +#define InCheck InCheckBB +#endif + +FLAG SanityCheckMove(POSITION *pos, MOVE mv); FLAG @@ -1947,6 +2021,141 @@ GenerateMoves(SEARCHER_THREAD_CONTEXT *ctx, MOVE mvOrderFirst, ULONG uType); +// board_representation/MOVEGEN_MIGRATION.md section 3 step 1 -- see +// generate.c for the routine description. Exposed non-static so +// testgenerate.c's correctness/speed harness can call it directly +// regardless of whether GENERATE_KNIGHT_BITBOARD is defined for this +// build. +BITBOARD +_BuildFriendlySideBB(POSITION *pos, ULONG uSide); + +BITBOARD +_BuildFullOccupiedBB(POSITION *pos); + +// board_representation/MOVEGEN_MIGRATION.md section 6b -- exposed so +// movesup.c's ExposesCheckBB family can reuse the same magic-lookup +// arithmetic as the Part A/B generators instead of duplicating it. +BITBOARD +_RookAttacksBB(COOR c, BITBOARD bbOccupied); + +BITBOARD +_BishopAttacksBB(COOR c, BITBOARD bbOccupied); + +void +_GenerateRookBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cRook); + +void +GenerateRook(MOVE_STACK *pStack, + POSITION *pos, + COOR cRook); + +void +_GenerateBishopBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cBishop); + +void +GenerateBishop(MOVE_STACK *pStack, + POSITION *pos, + COOR cBishop); + +void +_GenerateQueenBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cQueen); + +// Whole-node dispatch pair -- see _GenerateAllMovesBB's block comment +// in generate.c. Exposed (not static) so testgenerate.c can benchmark +// them directly against each other by name. +void +_GenerateAllMoves(MOVE_STACK *pStack, + POSITION *pos); + +void +_GenerateAllMovesBB(MOVE_STACK *pStack, + POSITION *pos); + +void +_GenerateAllPawnMovesBB(MOVE_STACK *pStack, + POSITION *pos, + ULONG uSide); + +// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2 -- +// exposed (not static) for testgenerate.c's future speed harness, +// same convention as the Part A _Generate*BB functions. +void +_SaveMeKnightBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cKnight, + COOR cKing, + BITBOARD bbTargetMask); + +void +_SaveMeBishopBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cBishop, + COOR cKing, + BITBOARD bbTargetMask); + +void +_SaveMeRookBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cRook, + COOR cKing, + BITBOARD bbTargetMask); + +void +_SaveMeQueenBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cQueen, + COOR cKing, + BITBOARD bbTargetMask); + +void +_SaveMeAllPawnMovesBB(MOVE_STACK *pStack, + POSITION *pos, + ULONG uSide, + COOR cKing, + COOR cAttacker, + BITBOARD bbTargetMask); + +void +GenerateQueen(MOVE_STACK *pStack, + POSITION *pos, + COOR cQueen); + +void +_GenerateKnightBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cKnight); + +void +GenerateKnight(MOVE_STACK *pStack, + POSITION *pos, + COOR cKnight); + +void +GenerateWhiteKnight(MOVE_STACK *pStack, + POSITION *pos, + COOR cKnight); + +void +_GenerateKingBB(MOVE_STACK *pStack, + POSITION *pos, + COOR cKing); + +void +GenerateBlackKing(MOVE_STACK *pStack, + POSITION *pos, + COOR cKing); + +void +GenerateWhiteKing(MOVE_STACK *pStack, + POSITION *pos, + COOR cKing); + FLAG WouldGiveCheck(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv); @@ -1967,6 +2176,24 @@ TestMoveGenerator(void); void TestLegalMoveGenerator(void); +void +TestGenerateKnightSpeed(void); + +void +TestGenerateKingSpeed(void); + +void +TestGenerateRookSpeed(void); + +void +TestGenerateBishopSpeed(void); + +void +TestGenerateQueenSpeed(void); + +void +TestGenerateAllMovesSpeed(void); + #endif // @@ -2046,7 +2273,16 @@ extern BITBOARD g_BishopRayAll[128]; extern const int g_BishopRayDeltas[4]; extern const FLAG g_BishopRayPositiveDir[4]; extern BITBOARD g_KnightAttacksBB[128]; +extern BITBOARD g_KingAttacksBB[128]; extern BITBOARD g_PawnAttackOriginBB[2][128]; +extern BITBOARD g_RookOccupancyMask[128]; +extern BITBOARD g_BishopOccupancyMask[128]; +extern BITBOARD g_RookMagic[128]; +extern BITBOARD g_BishopMagic[128]; +extern ULONG g_RookMagicShift[128]; +extern ULONG g_BishopMagicShift[128]; +extern BITBOARD *g_RookAttackTable[128]; +extern BITBOARD *g_BishopAttackTable[128]; void InitializeWhiteSquaresTable(void); @@ -2070,8 +2306,14 @@ void InitializeKnightAttackTables(void); void +InitializeKingAttackTables(void); + +void InitializePawnAttackOriginTable(void); +void +InitMagic(void); + #ifdef DEBUG ULONG CheckVectorWithIndex(int i, ULONG uColor); #define CHECK_VECTOR_WITH_INDEX(i, color) \ @@ -2603,6 +2845,9 @@ DebugSEE(POSITION *pos, void TestGetAttacks(void); +void +TestIsAttackedBB(void); + // // hash.c // @@ -2905,6 +3150,17 @@ _GetAttacksBB(SEE_LIST *pList, COOR cSquare, ULONG uSide); +// board_representation/MOVEGEN_MIGRATION.md section 6a: exposed (not +// static) so generate.c's Part B king-flight code can call it with a +// king-vacated occupancy bitboard. Deliberately excludes pawns -- see +// its own header comment in see.c; callers needing pawn attacks must +// check g_PawnAttackOriginBB separately. +BITBOARD +_WhoAttacksSquareBB(POSITION *pos, + COOR cSquare, + ULONG uSide, + BITBOARD bbOccupied); + // Three-way choice for which GetAttacks implementation is actually // live -- see MIGRATION.md section 6: // GETATTACKS_BITBOARD defined -> _GetAttacksBB (bitboard, new) @@ -738,6 +738,58 @@ Return value: } // +// Per-square "all squares a king on c can step to" bitboard (normal +// king moves only -- castling stays mailbox, see +// board_representation/MOVEGEN_MIGRATION.md section 1's explicit +// non-goal and section 3 step 2). Same shape as g_KnightAttacksBB: +// 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, +// hence this table exists where GetAttacks needed none. Built once at +// startup by InitializeKingAttackTables(). +// +BITBOARD g_KingAttacksBB[128]; + +void +InitializeKingAttackTables(void) +/** + +Routine description: + + One-time startup init for g_KingAttacksBB -- see its comment. + +Parameters: + + void + +Return value: + + void + +**/ +{ + ULONG uRank, uFile, uDir; + COOR c, cSquare; + + memset(g_KingAttacksBB, 0, sizeof(g_KingAttacksBB)); + for (uRank = 0; uRank < 8; uRank++) + { + for (uFile = 0; uFile < 8; uFile++) + { + c = (uRank << 4) | uFile; + for (uDir = 0; g_iQKDeltas[uDir] != 0; uDir++) + { + cSquare = c + g_iQKDeltas[uDir]; + if (IS_ON_BOARD(cSquare)) + { + g_KingAttacksBB[c] |= COOR_TO_BB(cSquare); + } + } + } + } +} + +// // Per-square, per-side "the (up to 2) squares a pawn of this side // would need to stand on to attack c" bitboard -- e.g. // g_PawnAttackOriginBB[WHITE][c] is c's two SE/SW neighbors (a white @@ -793,3 +845,313 @@ Return value: } } } + +// +// Magic-bitboard tables for rook/bishop move generation -- see +// board_representation/MOVEGEN_MIGRATION.md sections 2a/3 for the +// full design writeup. Everything here (occupancy masks, magic +// numbers, and the attack tables they index into) is computed once at +// startup by InitMagic(), never hardcoded -- a validation prototype +// measured the full search+build+verify cost at ~0.22s for both piece +// types combined, cheap enough to just pay at every process launch +// rather than maintaining hand-pasted constants that could silently +// drift out of sync with the ray tables or square numbering they're +// derived from. +// +// g_RookOccupancyMask[c] / g_BishopOccupancyMask[c]: the "relevant +// occupancy" bits for a slider on c -- g_RookRayToEdge/ +// g_BishopRayToEdge's full ray-to-edge, minus each direction's +// outermost square (a piece standing on the actual board edge can't +// hide a further blocker, so it doesn't affect which squares are +// reachable and must be excluded to keep the occupancy-permutation +// count, and therefore the attack table size, minimal). +// +// g_RookMagic[c] / g_BishopMagic[c] and g_RookMagicShift[c] / +// g_BishopMagicShift[c]: found by InitMagic() via a random +// sparse-candidate search, fixed-seeded (see g_MagicRngState below) +// so a given build reproduces the exact same magics on every run -- +// deliberately NOT using libc's rand()/srand(), since main.c's +// startup path already calls srand((unsigned int)time(0)) for +// unrelated reasons, and piggybacking on that shared, time-seeded +// generator would silently reintroduce the very non-determinism this +// design is meant to avoid. +// +// g_RookAttackTable[c] / g_BishopAttackTable[c]: one malloc'd array +// per square, indexed by ((occupancy & mask) * magic) >> shift, +// giving the complete pseudo-legal destination bitboard (empty +// squares plus the nearest blocker in every direction, regardless of +// which side owns it -- the caller is responsible for ANDing off +// friendly occupancy before treating the blocker square as a legal +// destination, same convention g_KnightAttacksBB's consumer already +// uses). Never freed -- these live for the process's lifetime, same +// as every other table in this file. +// +BITBOARD g_RookOccupancyMask[128]; +BITBOARD g_BishopOccupancyMask[128]; +BITBOARD g_RookMagic[128]; +BITBOARD g_BishopMagic[128]; +ULONG g_RookMagicShift[128]; +ULONG g_BishopMagicShift[128]; +BITBOARD *g_RookAttackTable[128]; +BITBOARD *g_BishopAttackTable[128]; + +// Private PRNG state for the magic-number search -- deliberately +// separate from libc's rand()/srand() (see the block comment above). +// xorshift64*, fixed literal seed: the exact value doesn't matter, but +// it must never change to a time-based or otherwise run-varying seed, +// or every reproducibility claim in MOVEGEN_MIGRATION.md section 2a +// stops being true. +static UINT64 g_MagicRngState = 88172645463325252ULL; + +static UINT64 +_MagicNextRandom64(void) +{ + UINT64 x = g_MagicRngState; + x ^= x << 13; + x ^= x >> 7; + x ^= x << 17; + g_MagicRngState = x; + return x; +} + +// Sparse (mostly-zero-bit) candidates are known to converge faster in +// magic-number search than uniform random 64-bit values -- standard +// technique, matches the validation prototype this was ported from. +static UINT64 +_MagicSparseRandom64(void) +{ + return _MagicNextRandom64() & _MagicNextRandom64() & _MagicNextRandom64(); +} + +// Slow, obviously-correct reference used both to build each magic +// table's contents and to verify it before InitMagic() accepts it: +// walk each of the 4 directions from c until (and including) the +// first occupied square, given a full occupancy bitboard covering +// both sides' pieces. +static BITBOARD +_MagicSlowAttacks(COOR c, BITBOARD bbOccupied, const int iDelta[4]) +{ + BITBOARD bbResult = 0; + ULONG uDir; + COOR cSquare; + + for (uDir = 0; uDir < 4; uDir++) + { + for (cSquare = c + iDelta[uDir]; + IS_ON_BOARD(cSquare); + cSquare += iDelta[uDir]) + { + BITBOARD bbSq = COOR_TO_BB(cSquare); + bbResult |= bbSq; + if (bbOccupied & bbSq) + { + break; + } + } + } + return bbResult; +} + +// Standard "carry-rippler" occupancy-subset enumeration: the uIndex-th +// subset of mask's set bits, treating uIndex's own bits as a +// present/absent flag for each of mask's bits in ascending-bit order. +static BITBOARD +_MagicIndexToOccupancy(ULONG uIndex, ULONG uBits, BITBOARD mask) +{ + BITBOARD bbResult = 0; + ULONG i, uBit; + + for (i = 0; i < uBits; i++) + { + uBit = FastFirstBit(mask) - 1; + mask &= mask - 1; + if (uIndex & (1UL << i)) + { + bbResult |= (1ULL << uBit); + } + } + return bbResult; +} + +// Builds the relevant-occupancy mask for one square: the full ray to +// the edge in each of the 4 directions, minus that direction's +// outermost square -- see the block comment above +// g_RookOccupancyMask/g_BishopOccupancyMask. +static BITBOARD +_MagicBuildOccupancyMask(COOR c, const int iDelta[4]) +{ + BITBOARD bbResult = 0; + ULONG uDir; + COOR cSquare; + + for (uDir = 0; uDir < 4; uDir++) + { + for (cSquare = c + iDelta[uDir]; + IS_ON_BOARD(cSquare); + cSquare += iDelta[uDir]) + { + if (IS_ON_BOARD(cSquare + iDelta[uDir])) + { + bbResult |= COOR_TO_BB(cSquare); + } + } + } + return bbResult; +} + +// Finds a collision-free magic number for one square, builds its +// attack table from it, and verifies the whole thing against the slow +// reference one more time before returning -- the section 2a +// collision-freedom gate, run fresh at every startup rather than +// trusted from a prior offline run. +static void +_MagicFindAndBuildForSquare(COOR c, BITBOARD mask, const int iDelta[4], + BITBOARD *pMagic, ULONG *pShift, + BITBOARD **ppTable) +{ + ULONG uBits = CountBits(mask); + ULONG uSize = 1UL << uBits; + ULONG uShift = 64 - uBits; + BITBOARD *rgbbOccupancy = malloc(sizeof(BITBOARD) * uSize); + BITBOARD *rgbbAttacks = malloc(sizeof(BITBOARD) * uSize); + BITBOARD *rgbbTable = malloc(sizeof(BITBOARD) * uSize); + FLAG *rgfFilled = malloc(sizeof(FLAG) * uSize); + ULONG i; + UINT64 uMagic; + + if ((NULL == rgbbOccupancy) || (NULL == rgbbAttacks) || + (NULL == rgbbTable) || (NULL == rgfFilled)) + { + Bug("InitMagic: out of memory building table for square %d\n", c); + } + + for (i = 0; i < uSize; i++) + { + rgbbOccupancy[i] = _MagicIndexToOccupancy(i, uBits, mask); + rgbbAttacks[i] = _MagicSlowAttacks(c, rgbbOccupancy[i], iDelta); + } + + for (;;) + { + FLAG fCollision = FALSE; + ULONG uIndex; + + uMagic = _MagicSparseRandom64(); + + // Quick reject: a magic whose high byte doesn't spread widely + // when multiplied against the mask rarely yields a + // collision-free hash -- a cheap filter to skip obviously bad + // candidates before paying for the full uSize-entry pass. + if (CountBits((UINT64)(mask * uMagic) & 0xFF00000000000000ULL) < 6) + { + continue; + } + + memset(rgfFilled, 0, sizeof(FLAG) * uSize); + for (i = 0; (i < uSize) && !fCollision; i++) + { + uIndex = (ULONG)(((UINT64)rgbbOccupancy[i] * uMagic) >> uShift); + if (!rgfFilled[uIndex]) + { + rgfFilled[uIndex] = TRUE; + rgbbTable[uIndex] = rgbbAttacks[i]; + } + else if (rgbbTable[uIndex] != rgbbAttacks[i]) + { + fCollision = TRUE; + } + } + if (!fCollision) + { + break; + } + } + + // + // Belt-and-suspenders: re-verify every occupancy subset against + // the slow reference one more time before accepting this magic. + // Redundant with the search loop's own collision bookkeeping + // above in the common case, but this is the load-bearing + // correctness gate the rest of the magic-bitboard subsystem + // depends on (MOVEGEN_MIGRATION.md section 2a) -- worth paying + // for explicitly rather than trusting the search loop alone. + // + for (i = 0; i < uSize; i++) + { + BITBOARD bbOcc = _MagicIndexToOccupancy(i, uBits, mask); + BITBOARD bbExpected = _MagicSlowAttacks(c, bbOcc, iDelta); + ULONG uIndex = (ULONG)(((UINT64)bbOcc * uMagic) >> uShift); + + if (rgbbTable[uIndex] != bbExpected) + { + Bug("InitMagic: verification failed for square %d, " + "occupancy subset %lu\n", c, i); + } + } + + *pMagic = uMagic; + *pShift = uShift; + *ppTable = rgbbTable; + free(rgbbOccupancy); + free(rgbbAttacks); + free(rgfFilled); +} + +void +InitMagic(void) +/** + +Routine description: + + One-time startup init for the rook/bishop magic-bitboard tables -- + see the block comment above g_RookOccupancyMask/g_BishopOccupancyMask + for the full design and board_representation/MOVEGEN_MIGRATION.md + sections 2a/3 for the writeup. Must run after nothing in particular + (no dependency on the other Initialize*Tables functions), but is + grouped alongside them in main.c's startup sequence for consistency. + +Parameters: + + void + +Return value: + + void + +**/ +{ + ULONG uRank, uFile; + + memset(g_RookOccupancyMask, 0, sizeof(g_RookOccupancyMask)); + memset(g_BishopOccupancyMask, 0, sizeof(g_BishopOccupancyMask)); + memset(g_RookMagic, 0, sizeof(g_RookMagic)); + memset(g_BishopMagic, 0, sizeof(g_BishopMagic)); + memset(g_RookMagicShift, 0, sizeof(g_RookMagicShift)); + memset(g_BishopMagicShift, 0, sizeof(g_BishopMagicShift)); + memset(g_RookAttackTable, 0, sizeof(g_RookAttackTable)); + memset(g_BishopAttackTable, 0, sizeof(g_BishopAttackTable)); + + for (uRank = 0; uRank < 8; uRank++) + { + for (uFile = 0; uFile < 8; uFile++) + { + COOR c = (uRank << 4) | uFile; + + g_RookOccupancyMask[c] = + _MagicBuildOccupancyMask(c, g_RookRayDeltas); + _MagicFindAndBuildForSquare(c, g_RookOccupancyMask[c], + g_RookRayDeltas, + &g_RookMagic[c], + &g_RookMagicShift[c], + &g_RookAttackTable[c]); + + g_BishopOccupancyMask[c] = + _MagicBuildOccupancyMask(c, g_BishopRayDeltas); + _MagicFindAndBuildForSquare(c, g_BishopOccupancyMask[c], + g_BishopRayDeltas, + &g_BishopMagic[c], + &g_BishopMagicShift[c], + &g_BishopAttackTable[c]); + } + } +} diff --git a/src/eval_tune/test_vs_head.sh b/src/eval_tune/test_vs_head.sh index d5d8006..dfd803c 100755 --- a/src/eval_tune/test_vs_head.sh +++ b/src/eval_tune/test_vs_head.sh @@ -1,6 +1,6 @@ #!/usr/bin/env bash -python3 ./match_play.py ../../head_reference/typhoon ../typhoon \ +python3 ./match_play.py ../../head_reference/typhoon ../typhoon_allbitboards \ --pgn ../../pgn/twic_filtered.pgn \ --games 20000 \ --workers 12 \ diff --git a/src/generate.c b/src/generate.c index 09e3e0a..69e431f 100755 --- a/src/generate.c +++ b/src/generate.c @@ -728,6 +728,211 @@ GenerateWhiteKnight(IN MOVE_STACK *pStack, } // +// board_representation/MOVEGEN_MIGRATION.md section 3 step 1: bitboard +// knight generator, the pilot function for the whole migration -- +// lowest risk, most precedented (reuses g_KnightAttacksBB, already +// built and verified for GetAttacks, no new tables needed). Unlike the +// mailbox pair above, one function serves both JumpTable slots +// (BLACK_KNIGHT and WHITE_KNIGHT) -- GenerateWhiteKnight's +// GET_COLOR(p)==BLACK bit trick was purely a mailbox micro- +// optimization exploiting how BLACK happens to be encoded; a bitboard +// lookup needs no such color-specific shortcut, it just ANDs off +// whichever side's occupancy pos->uToMove identifies. +// +// Full-board occupancy, both sides -- same formula as see.c's static +// _BuildOccupiedBB (a separate copy, not shared, since that one is +// file-local to see.c and this module's own convention keeps its +// bitboard helpers together). Needed by the slider magic-bitboard +// generators (_GenerateRookBB/_GenerateBishopBB) to index into +// g_RookAttackTable/g_BishopAttackTable -- see MOVE_STACK's +// bbOccupied field comment in chess.h. Non-static so testgenerate.c's +// harness can call it directly. +BITBOARD +_BuildFullOccupiedBB(IN POSITION *pos) +/** + +Routine description: + + Full-board occupancy bitboard (both colors, every piece including + pawns and kings). + +Parameters: + + POSITION *pos + +Return value: + + BITBOARD + +**/ +{ + return (pos->bbPieces[WHITE][KNIGHT] | pos->bbPieces[WHITE][BISHOP] | + pos->bbPieces[WHITE][ROOK] | pos->bbPieces[WHITE][QUEEN] | + pos->bbPieces[BLACK][KNIGHT] | pos->bbPieces[BLACK][BISHOP] | + pos->bbPieces[BLACK][ROOK] | pos->bbPieces[BLACK][QUEEN] | + pos->bbPawns[WHITE] | pos->bbPawns[BLACK] | + COOR_TO_BB(pos->cNonPawns[WHITE][0]) | + COOR_TO_BB(pos->cNonPawns[BLACK][0])); +} + +// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: raw +// magic-table lookups, factored out of _GenerateRookBB/_GenerateBishopBB +// so _ComputeCheckTargetMaskBB (below) and the Part B SaveMe*BB +// functions can reuse them without duplicating the index arithmetic a +// third/fourth time. Non-static (unlike their original file-local +// status) so movesup.c's section 6b ExposesCheckBB work can call them +// too -- same convention as _BuildFriendlySideBB/_WhoAttacksSquareBB. +BITBOARD FORCEINLINE +_RookAttacksBB(IN COOR c, IN BITBOARD bbOccupied) +{ + ULONG uMagicIndex = (ULONG) + (((bbOccupied & g_RookOccupancyMask[c]) * + g_RookMagic[c]) >> g_RookMagicShift[c]); + return g_RookAttackTable[c][uMagicIndex]; +} + +BITBOARD FORCEINLINE +_BishopAttacksBB(IN COOR c, IN BITBOARD bbOccupied) +{ + ULONG uMagicIndex = (ULONG) + (((bbOccupied & g_BishopOccupancyMask[c]) * + g_BishopMagic[c]) >> g_BishopMagicShift[c]); + return g_BishopAttackTable[c][uMagicIndex]; +} + +// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: +// bbTargetMask = every square a non-king move could land on to resolve +// a lone check -- the checker's own square (a capture always resolves +// check) OR, if the checker is a slider, every square strictly between +// it and the king (a block also resolves check). The "squares between +// two aligned pieces" trick costs nothing new: each square's magic +// attack bitboard already reaches exactly to its nearest blocker in +// every direction, so ANDing both sides' attack sets together gives +// precisely the empty segment between them, excluding both endpoints +// (neither piece's own attack set includes its own square). A +// diagonally-adjacent pawn checker naturally falls out of the same +// bishop-table branch with zero extra bits, since there is nothing +// between two adjacent squares -- no separate pawn case needed. A +// non-aligned (knight) checker is the only case requiring a branch: +// DIRECTION_BETWEEN_SQUARES returns 0 for a knight offset, and there +// is no way to block a knight's check regardless. +static BITBOARD +_ComputeCheckTargetMaskBB(IN COOR cKing, IN COOR cAttacker, + IN BITBOARD bbOccupied) +{ + int iDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing); + BITBOARD bbBetween = 0; + + if (0 != iDelta) + { + if ((16 == iDelta) || (-16 == iDelta) || + (1 == iDelta) || (-1 == iDelta)) + { + bbBetween = _RookAttacksBB(cKing, bbOccupied) & + _RookAttacksBB(cAttacker, bbOccupied); + } + else + { + bbBetween = _BishopAttacksBB(cKing, bbOccupied) & + _BishopAttacksBB(cAttacker, bbOccupied); + } + } + return COOR_TO_BB(cAttacker) | bbBetween; +} + +// Non-static so testgenerate.c's harness can call it directly to set +// up MOVE_STACK.bbFriendlyOccupied when calling a _Generate*BB +// function outside of _GenerateAllMoves. +BITBOARD +_BuildFriendlySideBB(IN POSITION *pos, IN ULONG uSide) +/** + +Routine description: + + Full occupancy bitboard for one side only (all piece types + including pawns and king) -- see.c's _BuildOccupiedBB ORs both + sides together for a different purpose (SEE's "is this square + occupied at all" query); move generation needs just one side's + squares, to AND off as illegal (self-occupied) destinations. + +Parameters: + + POSITION *pos + ULONG uSide + +Return value: + + BITBOARD + +**/ +{ + return (pos->bbPieces[uSide][KNIGHT] | pos->bbPieces[uSide][BISHOP] | + pos->bbPieces[uSide][ROOK] | pos->bbPieces[uSide][QUEEN] | + pos->bbPawns[uSide] | + COOR_TO_BB(pos->cNonPawns[uSide][0])); +} + +// Non-static (unlike a purely-internal helper would be) so +// testgenerate.c's speed/correctness harness can call it directly, +// same convention _GetAttacksBB (see.c) already uses. +void +_GenerateKnightBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cKnight) +/** + +Routine description: + + Bitboard equivalent of GenerateKnight/GenerateWhiteKnight -- called + by GenerateMoves' JumpTable in place of both when + GENERATE_KNIGHT_BITBOARD is defined. Produces the exact same + pseudo-legal move set (same over-generation behavior, no + legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's + explicit non-goal. + + Relies on pStack->bbFriendlyOccupied already being set by the + caller (_GenerateAllMoves computes it once per node, before + dispatching to any piece type, precisely so every bitboard-backed + generator for that node shares one build instead of each paying + for its own -- see MOVE_STACK's field comment in chess.h). A + direct caller outside of _GenerateAllMoves (e.g. testgenerate.c's + harness) must set it first; the DEBUG-build ASSERT below catches + a stale/unset value, but only in a DEBUG build. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must + already be set for pos->uToMove) + POSITION *pos : the board position + COOR cKnight : the knight's location + +Return value: + + static void + +**/ +{ + BITBOARD bbDest = g_KnightAttacksBB[cKnight] & ~pStack->bbFriendlyOccupied; + ULONG uBitIndex; + COOR c; + PIECE p; + + ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove); + ASSERT(pStack->bbFriendlyOccupied == + _BuildFriendlySideBB(pos, pos->uToMove)); + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cKnight, c, p); + } +} + +// // These logical AND/ORs replaced with bitwise AND/OR; the effect is // the same the the bitwise is marginally faster. // @@ -803,6 +1008,68 @@ Return value: while(0 != g_iNDeltas[u]); } +// +// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: +// bitboard equivalent of SaveMeKnight -- one AND against a +// precomputed bbTargetMask replaces the per-square (c == cAttacker) || +// BLOCKS_THE_CHECK(c) test entirely. ExposesCheck (pin detection) +// stays exactly as-is, unchanged, called per surviving candidate -- +// not in scope to alter, see section 6a's "what does not change." +// +void +_SaveMeKnightBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cKnight, + IN COOR cKing, + IN BITBOARD bbTargetMask) +/** + +Routine description: + + Bitboard equivalent of SaveMeKnight -- called in place of it (via + a direct, statically-known call, not JumpTable) when + GENERATE_ESCAPES_BLOCK_BITBOARD is defined. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must + already be set for pos->uToMove) + POSITION *pos : the board position + COOR cKnight : the knight's location + COOR cKing : the friendly king's location + BITBOARD bbTargetMask : squares that resolve the lone check -- + see _ComputeCheckTargetMaskBB + +Return value: + + void + +**/ +{ + BITBOARD bbDest = g_KnightAttacksBB[cKnight] & + ~pStack->bbFriendlyOccupied & bbTargetMask; + ULONG uBitIndex; + COOR c, cExposed; + PIECE p; + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove); + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + cExposed = ExposesCheck(pos, cKnight, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == c)) + { + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cKnight, c, p); + } + } +} + const INT g_iBDeltas[] = { -17, -15, +15, +17, 0 }; @@ -916,6 +1183,78 @@ Return value: } } +// +// board_representation/MOVEGEN_MIGRATION.md section 3 step 3: +// magic-bitboard bishop generator -- mechanically identical to +// _GenerateRookBB, swapping in the bishop's magic tables. Measured +// speed result for rook was parity (not a win) against mailbox at +// these small destination counts -- see that finding written up in +// MOVEGEN_MIGRATION.md's section 3 entry; expect the same here rather +// than a different outcome, since the underlying reason (a mailbox ray +// walk's cost is already ~O(destination count), so magic's O(1) +// lookup pipeline doesn't out-race it at these distances) applies +// identically to diagonals. +// +void +_GenerateBishopBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cBishop) +/** + +Routine description: + + Bitboard equivalent of GenerateBishop -- called by GenerateMoves' + JumpTable in place of it when GENERATE_BISHOP_BITBOARD is defined. + Produces the exact same pseudo-legal move set (same over-generation + behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md + section 1's explicit non-goal. + + Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already + being set by the caller, same as _GenerateRookBB -- see that + function's header comment and MOVE_STACK's field comments in + chess.h. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and + bbOccupied must already be set) + POSITION *pos : the board position + COOR cBishop : the bishop's location + +Return value: + + void + +**/ +{ + ULONG uMagicIndex; + BITBOARD bbDest; + ULONG uBitIndex; + COOR c; + PIECE p; + + ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove); + ASSERT(pStack->bbFriendlyOccupied == + _BuildFriendlySideBB(pos, pos->uToMove)); + ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos)); + + uMagicIndex = (ULONG) + (((pStack->bbOccupied & g_BishopOccupancyMask[cBishop]) * + g_BishopMagic[cBishop]) >> g_BishopMagicShift[cBishop]); + bbDest = g_BishopAttackTable[cBishop][uMagicIndex] & + ~pStack->bbFriendlyOccupied; + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cBishop, c, p); + } +} + void SaveMeBishop(IN MOVE_STACK *pStack, @@ -990,6 +1329,65 @@ Return value: while(0 != g_iBDeltas[u]); } +// +// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: +// bitboard equivalent of SaveMeBishop -- same pattern as +// _SaveMeKnightBB, using the magic lookup instead of a ray walk. +// +void +_SaveMeBishopBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cBishop, + IN COOR cKing, + IN BITBOARD bbTargetMask) +/** + +Routine description: + + Bitboard equivalent of SaveMeBishop -- called in place of it (via + a direct, statically-known call, not JumpTable) when + GENERATE_ESCAPES_BLOCK_BITBOARD is defined. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and + bbOccupied must already be set) + POSITION *pos : the board position + COOR cBishop : the bishop's location + COOR cKing : the friendly king's location + BITBOARD bbTargetMask : squares that resolve the lone check -- + see _ComputeCheckTargetMaskBB + +Return value: + + void + +**/ +{ + BITBOARD bbDest = _BishopAttacksBB(cBishop, pStack->bbOccupied) & + ~pStack->bbFriendlyOccupied & bbTargetMask; + ULONG uBitIndex; + COOR c, cExposed; + PIECE p; + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove); + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + cExposed = ExposesCheck(pos, cBishop, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == c)) + { + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cBishop, c, p); + } + } +} + const INT g_iRDeltas[] = { -1, +1, +16, -16, 0 }; @@ -1104,6 +1502,77 @@ Return value: } } +// +// board_representation/MOVEGEN_MIGRATION.md section 3 step 3: magic- +// bitboard rook generator -- the first consumer of the InitMagic() +// infrastructure (data.c) built ahead of time for exactly this. Unlike +// knight/king, this piece type is expected to actually win on speed: +// the magic lookup replaces a 4-direction ray walk (up to 7 squares +// per direction) with one multiply+shift+table lookup, independent of +// how far the rook can see. +// +void +_GenerateRookBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cRook) +/** + +Routine description: + + Bitboard equivalent of GenerateRook -- called by GenerateMoves' + JumpTable in place of it when GENERATE_ROOK_BITBOARD is defined. + Produces the exact same pseudo-legal move set (same over-generation + behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md + section 1's explicit non-goal. + + Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already + being set by the caller (_GenerateAllMoves computes both once per + node, before dispatching to any piece type) -- see MOVE_STACK's + field comments in chess.h. A direct caller outside of + _GenerateAllMoves (e.g. testgenerate.c's harness) must set both + first. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and + bbOccupied must already be set) + POSITION *pos : the board position + COOR cRook : the rook's location + +Return value: + + void + +**/ +{ + ULONG uMagicIndex; + BITBOARD bbDest; + ULONG uBitIndex; + COOR c; + PIECE p; + + ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove); + ASSERT(pStack->bbFriendlyOccupied == + _BuildFriendlySideBB(pos, pos->uToMove)); + ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos)); + + uMagicIndex = (ULONG) + (((pStack->bbOccupied & g_RookOccupancyMask[cRook]) * + g_RookMagic[cRook]) >> g_RookMagicShift[cRook]); + bbDest = g_RookAttackTable[cRook][uMagicIndex] & + ~pStack->bbFriendlyOccupied; + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cRook, c, p); + } +} + void SaveMeRook(IN MOVE_STACK *pStack, IN POSITION *pos, @@ -1177,6 +1646,65 @@ Return value: while(0 != g_iRDeltas[u]); } +// +// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: +// bitboard equivalent of SaveMeRook -- same pattern as +// _SaveMeBishopBB, using the rook magic lookup instead of a ray walk. +// +void +_SaveMeRookBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cRook, + IN COOR cKing, + IN BITBOARD bbTargetMask) +/** + +Routine description: + + Bitboard equivalent of SaveMeRook -- called in place of it (via a + direct, statically-known call, not JumpTable) when + GENERATE_ESCAPES_BLOCK_BITBOARD is defined. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and + bbOccupied must already be set) + POSITION *pos : the board position + COOR cRook : the rook's location + COOR cKing : the friendly king's location + BITBOARD bbTargetMask : squares that resolve the lone check -- + see _ComputeCheckTargetMaskBB + +Return value: + + void + +**/ +{ + BITBOARD bbDest = _RookAttacksBB(cRook, pStack->bbOccupied) & + ~pStack->bbFriendlyOccupied & bbTargetMask; + ULONG uBitIndex; + COOR c, cExposed; + PIECE p; + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove); + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + cExposed = ExposesCheck(pos, cRook, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == c)) + { + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cRook, c, p); + } + } +} + void GenerateQueen(IN MOVE_STACK *pStack, @@ -1234,6 +1762,82 @@ Return value: while(0 != g_iQKDeltas[u]); } +// +// board_representation/MOVEGEN_MIGRATION.md section 3 step 4: queen is +// just rook-directions OR bishop-directions combined, once step 3 is +// solved -- no new design or new tables needed. Two magic lookups (one +// rook-table, one bishop-table) ORed together, same +// `_EvalQueenOccupancyBB`-flagged caution as the rest of this plan: +// a combined single 8-ray table was tried elsewhere (the PoC in data.c +// this migration's tables were built alongside) and measured *slower* +// than reusing the two-pass rook/bishop structure -- don't rediscover +// that, this deliberately does not attempt to unify the two lookups +// into one table. +// +void +_GenerateQueenBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cQueen) +/** + +Routine description: + + Bitboard equivalent of GenerateQueen -- called by GenerateMoves' + JumpTable in place of it when GENERATE_QUEEN_BITBOARD is defined. + Produces the exact same pseudo-legal move set (same over-generation + behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md + section 1's explicit non-goal. + + Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already + being set by the caller, same as _GenerateRookBB/_GenerateBishopBB + -- see those functions' header comments and MOVE_STACK's field + comments in chess.h. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and + bbOccupied must already be set) + POSITION *pos : the board position + COOR cQueen : the queen's location + +Return value: + + void + +**/ +{ + ULONG uRookMagicIndex, uBishopMagicIndex; + BITBOARD bbDest; + ULONG uBitIndex; + COOR c; + PIECE p; + + ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove); + ASSERT(pStack->bbFriendlyOccupied == + _BuildFriendlySideBB(pos, pos->uToMove)); + ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos)); + + uRookMagicIndex = (ULONG) + (((pStack->bbOccupied & g_RookOccupancyMask[cQueen]) * + g_RookMagic[cQueen]) >> g_RookMagicShift[cQueen]); + uBishopMagicIndex = (ULONG) + (((pStack->bbOccupied & g_BishopOccupancyMask[cQueen]) * + g_BishopMagic[cQueen]) >> g_BishopMagicShift[cQueen]); + bbDest = (g_RookAttackTable[cQueen][uRookMagicIndex] | + g_BishopAttackTable[cQueen][uBishopMagicIndex]) & + ~pStack->bbFriendlyOccupied; + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cQueen, c, p); + } +} + void SaveMeQueen(IN MOVE_STACK *pStack, @@ -1309,6 +1913,66 @@ Return value: while(0 != g_iQKDeltas[u]); } +// +// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: +// bitboard equivalent of SaveMeQueen -- two magic lookups ORed +// together, same as _GenerateQueenBB, ANDed with bbTargetMask. +// +void +_SaveMeQueenBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cQueen, + IN COOR cKing, + IN BITBOARD bbTargetMask) +/** + +Routine description: + + Bitboard equivalent of SaveMeQueen -- called in place of it (via a + direct, statically-known call, not JumpTable) when + GENERATE_ESCAPES_BLOCK_BITBOARD is defined. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and + bbOccupied must already be set) + POSITION *pos : the board position + COOR cQueen : the queen's location + COOR cKing : the friendly king's location + BITBOARD bbTargetMask : squares that resolve the lone check -- + see _ComputeCheckTargetMaskBB + +Return value: + + void + +**/ +{ + BITBOARD bbDest = (_RookAttacksBB(cQueen, pStack->bbOccupied) | + _BishopAttacksBB(cQueen, pStack->bbOccupied)) & + ~pStack->bbFriendlyOccupied & bbTargetMask; + ULONG uBitIndex; + COOR c, cExposed; + PIECE p; + + ASSERT(InCheck(pos, pos->uToMove)); + ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove); + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + cExposed = ExposesCheck(pos, cQueen, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == c)) + { + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cQueen, c, p); + } + } +} + void GenerateBlackKing(IN MOVE_STACK *pStack, IN POSITION *pos, @@ -1482,6 +2146,123 @@ Return value: } } +// +// board_representation/MOVEGEN_MIGRATION.md section 3 step 2: bitboard +// king generator, normal (non-castling) moves only -- castling stays +// mailbox per section 1's explicit non-goal (at most 2 candidate +// moves, checked via simple square-emptiness tests, not +// ray-walk-shaped, nothing for a bitboard to speed up). Serves both +// JumpTable slots the same way _GenerateKnightBB does, for the same +// reason (GenerateWhiteKing's GET_COLOR(p)==BLACK bit trick was a +// mailbox-only micro-optimization); the castling tail below still +// branches on color since CASTLE_BLACK_*/CASTLE_WHITE_* and their +// associated squares genuinely differ per side. +// +void +_GenerateKingBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN COOR cKing) +/** + +Routine description: + + Bitboard equivalent of GenerateBlackKing/GenerateWhiteKing's normal + (non-castling) move enumeration -- called by GenerateMoves' + JumpTable in place of both when GENERATE_KING_BITBOARD is defined. + Produces the exact same pseudo-legal move set as the mailbox pair, + castling included (via the same mailbox logic those functions use, + verbatim) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal + against changing over-generation behavior. + + Relies on pStack->bbFriendlyOccupied already being set by the + caller, same as _GenerateKnightBB -- see that function's header + comment and MOVE_STACK's field comment in chess.h. + +Parameters: + + MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must + already be set for pos->uToMove) + POSITION *pos : the board position + COOR cKing : the king's location + +Return value: + + void + +**/ +{ + BITBOARD bbDest = g_KingAttacksBB[cKing] & ~pStack->bbFriendlyOccupied; + ULONG uBitIndex; + COOR c; + PIECE p; + + ASSERT(IS_KING(pos->rgSquare[cKing].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) == pos->uToMove); + ASSERT(pStack->bbFriendlyOccupied == + _BuildFriendlySideBB(pos, pos->uToMove)); + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + p = pos->rgSquare[c].pPiece; + _AddNormalMove(pStack, pos, cKing, c, p); + } + + // + // Castling: unchanged mailbox logic, copied verbatim from + // GenerateBlackKing/GenerateWhiteKing -- see those functions' + // comments. Not in scope for a bitboard rewrite (section 1). + // + if (pos->uToMove == BLACK) + { + if ((pos->bvCastleInfo & BLACK_CAN_CASTLE) == 0) return; +#ifdef DEBUG + ASSERT(IS_KING(pos->rgSquare[E8].pPiece)); + ASSERT(cKing == E8); +#endif + if ((pos->bvCastleInfo & CASTLE_BLACK_SHORT) && + (IS_EMPTY(pos->rgSquare[G8].pPiece)) && + (IS_EMPTY(pos->rgSquare[F8].pPiece))) + { + ASSERT(pos->rgSquare[H8].pPiece == BLACK_ROOK); + _AddCastle(pStack, pos, E8, G8); + } + if ((pos->bvCastleInfo & CASTLE_BLACK_LONG) && + (IS_EMPTY(pos->rgSquare[C8].pPiece)) && + (IS_EMPTY(pos->rgSquare[D8].pPiece)) && + (IS_EMPTY(pos->rgSquare[B8].pPiece))) + { + ASSERT(pos->rgSquare[A8].pPiece == BLACK_ROOK); + _AddCastle(pStack, pos, E8, C8); + } + } + else + { + if ((pos->bvCastleInfo & WHITE_CAN_CASTLE) == 0) return; +#ifdef DEBUG + ASSERT(IS_KING(pos->rgSquare[E1].pPiece)); + ASSERT(cKing == E1); +#endif + if ((pos->bvCastleInfo & CASTLE_WHITE_SHORT) && + (IS_EMPTY(pos->rgSquare[G1].pPiece)) && + (IS_EMPTY(pos->rgSquare[F1].pPiece))) + { + ASSERT(pos->rgSquare[H1].pPiece == WHITE_ROOK); + _AddCastle(pStack, pos, E1, G1); + } + if ((pos->bvCastleInfo & CASTLE_WHITE_LONG) && + (IS_EMPTY(pos->rgSquare[C1].pPiece)) && + (IS_EMPTY(pos->rgSquare[B1].pPiece)) && + (IS_EMPTY(pos->rgSquare[D1].pPiece))) + { + ASSERT(pos->rgSquare[A1].pPiece == WHITE_ROOK); + _AddCastle(pStack, pos, E1, C1); + } + } +} + void GenerateWhitePawn(IN MOVE_STACK *pStack, @@ -1882,6 +2663,213 @@ Return value: } } +// +// board_representation/MOVEGEN_MIGRATION.md section 3 step 5: bulk, +// whole-side pawn generator using the classic shift-and-mask technique +// (confirmed via ~/crafty/movgen.c to be the standard approach, not a +// per-starting-square precomputed mask) rather than a per-square +// lookup like the other five migrated piece types. Structurally +// different for a real reason: pos->bbPawns[uSide]'s bits already +// live in dense rank*8+file space (COOR_TO_BIT_NUMBER), so shifting +// the *entire* bitboard by 8 moves every pawn of that side forward one +// rank simultaneously -- no per-pawn loop needed to find destinations, +// only to emit the resulting moves. +// +// This engine's square numbering has A8 = bit 0 (COOR_TO_BIT_NUMBER of +// 0x88's A8 == 0x00), so rank number increases as the *row* (bits/8) +// *decreases* -- opposite of Crafty's convention (confirmed via +// GenerateWhitePawn's existing 0x88 deltas: -16 forward, -15/-17 +// captures). Concretely, in bit-number space: +// WHITE forward = row decreases = bb >> 8 +// BLACK forward = row increases = bb << 8 +// and the two diagonals per side are +-7/+-9 (one rank plus one file), +// each requiring the *opposite* file's edge excluded first so a +// same-row wraparound (e.g. an h-file pawn's ">>7" would otherwise +// silently land back on the same row's a-file -- a real, silent-wrong- +// answer trap, not just an out-of-range index) never happens -- see +// each shift's comment below for which file it excludes and why. +// +// Double-push eligibility (rank 2 for White, rank 7 for Black) is +// checked by masking the *already-computed single-push destination* +// bitboard against BBRANK[3]/BBRANK[6] (did this pawn's single push +// land on rank 3/6, which is only possible starting from rank 2/7) +// rather than a per-square starting-rank table -- same technique +// Crafty uses (movgen.c's padvances2, masking padvances1_all against +// its own rank-3/rank-6 constant before the second shift). +// +// En passant is deliberately NOT folded into the bulk capture +// bitboards -- it is exactly one specific square (pos->cEpSquare) at +// most once per node, cheaper and less error-prone to check directly +// (does either of the two diagonal-behind squares hold one of this +// side's pawns) than to derive and mask a whole extra bitboard for an +// event this rare. +// +void +_GenerateAllPawnMovesBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN ULONG uSide) +/** + +Routine description: + + Bitboard equivalent of the GenerateWhitePawn/GenerateBlackPawn pair + -- called in place of the per-pawn mailbox loop when + GENERATE_PAWN_BITBOARD is defined, for the entire side's pawns in + one call rather than once per pawn. Produces the exact same + pseudo-legal move set (same over-generation behavior, no + legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's + explicit non-goal. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + ULONG uSide : which side's pawns to generate for (pos->uToMove) + +Return value: + + void + +**/ +{ + BITBOARD bbPawns = pos->bbPawns[uSide]; + BITBOARD bbOccupied = _BuildFullOccupiedBB(pos); + BITBOARD bbEmpty = ~bbOccupied; + BITBOARD bbEnemy = bbOccupied & ~_BuildFriendlySideBB(pos, uSide); + BITBOARD bbSinglePush, bbDoublePush, bbCapLeft, bbCapRight, bb; + ULONG uBitIndex; + COOR cTo, cFrom, cEp; + PIECE p; + + if (uSide == WHITE) + { + bbSinglePush = (bbPawns >> 8) & bbEmpty; + bbDoublePush = ((bbSinglePush & BBRANK[3]) >> 8) & bbEmpty; + // "Left" diagonal (file-1, i.e. 0x88's -17): exclude file A + // (file-1 invalid/wraps for an a-file pawn). + bbCapLeft = ((bbPawns & ~BBFILE[0]) >> 9) & bbEnemy; + // "Right" diagonal (file+1, i.e. 0x88's -15): exclude file H. + bbCapRight = ((bbPawns & ~BBFILE[7]) >> 7) & bbEnemy; + } + else + { + ASSERT(uSide == BLACK); + bbSinglePush = (bbPawns << 8) & bbEmpty; + bbDoublePush = ((bbSinglePush & BBRANK[6]) << 8) & bbEmpty; + // "Left" diagonal (file-1, 0x88's +15): exclude file A. + bbCapLeft = ((bbPawns & ~BBFILE[0]) << 7) & bbEnemy; + // "Right" diagonal (file+1, 0x88's +17): exclude file H. + bbCapRight = ((bbPawns & ~BBFILE[7]) << 9) & bbEnemy; + } + + // Single push (+ promotion if landing on the far rank). + bb = bbSinglePush; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cTo = BIT_NUMBER_TO_COOR(uBitIndex); + cFrom = (uSide == WHITE) ? + BIT_NUMBER_TO_COOR(uBitIndex + 8) : + BIT_NUMBER_TO_COOR(uBitIndex - 8); + ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); + if (RANK8(cTo) || RANK1(cTo)) + { + _AddPromote(pStack, pos, cFrom, cTo); + } + else + { + _AddNormalMove(pStack, pos, cFrom, cTo, 0); + } + } + + // Double push -- never a promotion (rank 4/5 destination only). + bb = bbDoublePush; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cTo = BIT_NUMBER_TO_COOR(uBitIndex); + cFrom = (uSide == WHITE) ? + BIT_NUMBER_TO_COOR(uBitIndex + 16) : + BIT_NUMBER_TO_COOR(uBitIndex - 16); + ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); + _AddDoubleJump(pStack, pos, cFrom, cTo); + } + + // Capture left (+ promotion if landing on the far rank). + bb = bbCapLeft; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cTo = BIT_NUMBER_TO_COOR(uBitIndex); + cFrom = (uSide == WHITE) ? + BIT_NUMBER_TO_COOR(uBitIndex + 9) : + BIT_NUMBER_TO_COOR(uBitIndex - 7); + ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p) && OPPOSITE_COLORS(p, pos->rgSquare[cFrom].pPiece)); + if (RANK8(cTo) || RANK1(cTo)) + { + _AddPromote(pStack, pos, cFrom, cTo); + } + else + { + _AddNormalMove(pStack, pos, cFrom, cTo, p); + } + } + + // Capture right (+ promotion if landing on the far rank). + bb = bbCapRight; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cTo = BIT_NUMBER_TO_COOR(uBitIndex); + cFrom = (uSide == WHITE) ? + BIT_NUMBER_TO_COOR(uBitIndex + 7) : + BIT_NUMBER_TO_COOR(uBitIndex - 9); + ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece)); + p = pos->rgSquare[cTo].pPiece; + ASSERT(!IS_EMPTY(p) && OPPOSITE_COLORS(p, pos->rgSquare[cFrom].pPiece)); + if (RANK8(cTo) || RANK1(cTo)) + { + _AddPromote(pStack, pos, cFrom, cTo); + } + else + { + _AddNormalMove(pStack, pos, cFrom, cTo, p); + } + } + + // En passant -- deliberately not bulk (see block comment above): + // check the (at most 2) squares diagonally behind pos->cEpSquare + // for one of this side's pawns, exactly like the mailbox + // functions' cTo == pos->cEpSquare check, just run once per side + // per node instead of once per pawn. + cEp = pos->cEpSquare; + if (IS_ON_BOARD(cEp)) + { + int iBehindDelta = (uSide == WHITE) ? 16 : -16; + + cFrom = cEp + iBehindDelta - 1; + if (IS_ON_BOARD(cFrom) && + IS_PAWN(pos->rgSquare[cFrom].pPiece) && + (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide)) + { + _AddEnPassant(pStack, pos, cFrom, cEp); + } + cFrom = cEp + iBehindDelta + 1; + if (IS_ON_BOARD(cFrom) && + IS_PAWN(pos->rgSquare[cFrom].pPiece) && + (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide)) + { + _AddEnPassant(pStack, pos, cFrom, cEp); + } + } +} + void SaveMeBlackPawn(IN MOVE_STACK *pStack, @@ -2038,6 +3026,209 @@ Return value: } } +// +// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: bulk +// whole-side pawn escape generator, same shift-and-mask technique as +// _GenerateAllPawnMovesBB, with each move-category bitboard ANDed +// against bbTargetMask before extraction and an ExposesCheck filter +// added per surviving candidate (the mailbox SaveMeWhitePawn/ +// SaveMeBlackPawn pair calls ExposesCheck per move too -- see section +// 6a's "what does not change"). En passant is NOT covered by +// bbTargetMask (a between-squares/capture-square mask has no way to +// express "the checking pawn happens to be capturable en passant") -- +// kept as the same narrow direct special case the mailbox functions +// use: only relevant when the double-jumping pawn *is* the checker. +// +void +_SaveMeAllPawnMovesBB(IN MOVE_STACK *pStack, + IN POSITION *pos, + IN ULONG uSide, + IN COOR cKing, + IN COOR cAttacker, + IN BITBOARD bbTargetMask) +/** + +Routine description: + + Bitboard equivalent of the SaveMeWhitePawn/SaveMeBlackPawn pair -- + called in place of the per-pawn mailbox loop when + GENERATE_ESCAPES_BLOCK_BITBOARD is defined, for the entire side's + pawns in one call. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + ULONG uSide : which side's pawns to generate for (pos->uToMove) + COOR cKing : the friendly king's location + COOR cAttacker : the lone checker's location + BITBOARD bbTargetMask : squares that resolve the lone check -- + see _ComputeCheckTargetMaskBB + +Return value: + + void + +**/ +{ + BITBOARD bbPawns = pos->bbPawns[uSide]; + BITBOARD bbOccupied = _BuildFullOccupiedBB(pos); + BITBOARD bbEmpty = ~bbOccupied; + BITBOARD bbEnemy = bbOccupied & ~_BuildFriendlySideBB(pos, uSide); + BITBOARD bbSinglePush, bbDoublePush, bbCapLeft, bbCapRight, bb; + ULONG uBitIndex; + COOR cTo, cFrom, cExposed; + PIECE p; + + if (uSide == WHITE) + { + bbSinglePush = (bbPawns >> 8) & bbEmpty; + bbDoublePush = ((bbSinglePush & BBRANK[3]) >> 8) & bbEmpty; + bbCapLeft = ((bbPawns & ~BBFILE[0]) >> 9) & bbEnemy; + bbCapRight = ((bbPawns & ~BBFILE[7]) >> 7) & bbEnemy; + } + else + { + ASSERT(uSide == BLACK); + bbSinglePush = (bbPawns << 8) & bbEmpty; + bbDoublePush = ((bbSinglePush & BBRANK[6]) << 8) & bbEmpty; + bbCapLeft = ((bbPawns & ~BBFILE[0]) << 7) & bbEnemy; + bbCapRight = ((bbPawns & ~BBFILE[7]) << 9) & bbEnemy; + } + + // Every move category is ANDed against bbTargetMask -- see this + // function's header comment for why that's sufficient (a push + // destination is only ever in bbTargetMask if it's a genuine block + // square, since bbTargetMask's non-capture bits are, by + // construction, empty squares; a capture destination is only ever + // in bbTargetMask if it's the checker's own square, since + // between-squares are empty and captures already require bbEnemy). + bbSinglePush &= bbTargetMask; + bbDoublePush &= bbTargetMask; + bbCapLeft &= bbTargetMask; + bbCapRight &= bbTargetMask; + + bb = bbSinglePush; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cTo = BIT_NUMBER_TO_COOR(uBitIndex); + cFrom = (uSide == WHITE) ? + BIT_NUMBER_TO_COOR(uBitIndex + 8) : + BIT_NUMBER_TO_COOR(uBitIndex - 8); + cExposed = ExposesCheck(pos, cFrom, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cTo)) + { + if (RANK8(cTo) || RANK1(cTo)) + { + _AddPromote(pStack, pos, cFrom, cTo); + } + else + { + _AddNormalMove(pStack, pos, cFrom, cTo, 0); + } + } + } + + bb = bbDoublePush; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cTo = BIT_NUMBER_TO_COOR(uBitIndex); + cFrom = (uSide == WHITE) ? + BIT_NUMBER_TO_COOR(uBitIndex + 16) : + BIT_NUMBER_TO_COOR(uBitIndex - 16); + cExposed = ExposesCheck(pos, cFrom, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cTo)) + { + _AddDoubleJump(pStack, pos, cFrom, cTo); + } + } + + bb = bbCapLeft; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cTo = BIT_NUMBER_TO_COOR(uBitIndex); + cFrom = (uSide == WHITE) ? + BIT_NUMBER_TO_COOR(uBitIndex + 9) : + BIT_NUMBER_TO_COOR(uBitIndex - 7); + cExposed = ExposesCheck(pos, cFrom, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + if (RANK8(cTo) || RANK1(cTo)) + { + _AddPromote(pStack, pos, cFrom, cTo); + } + else + { + _AddNormalMove(pStack, pos, cFrom, cTo, p); + } + } + } + + bb = bbCapRight; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cTo = BIT_NUMBER_TO_COOR(uBitIndex); + cFrom = (uSide == WHITE) ? + BIT_NUMBER_TO_COOR(uBitIndex + 7) : + BIT_NUMBER_TO_COOR(uBitIndex - 9); + cExposed = ExposesCheck(pos, cFrom, cKing); + if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker)) + { + p = pos->rgSquare[cTo].pPiece; + if (RANK8(cTo) || RANK1(cTo)) + { + _AddPromote(pStack, pos, cFrom, cTo); + } + else + { + _AddNormalMove(pStack, pos, cFrom, cTo, p); + } + } + } + + // + // En passant: only relevant when the double-jumping enemy pawn + // *is* the checker -- there is no way to block check with an en + // passant capture (see SaveMeWhitePawn/SaveMeBlackPawn's identical + // comment). White defender: cAttacker == cEpSquare + 16. Black + // defender: cAttacker == cEpSquare - 16. + // + if (IS_ON_BOARD(pos->cEpSquare)) + { + COOR cEp = pos->cEpSquare; + int iBehindDelta = (uSide == WHITE) ? 16 : -16; + FLAG fEpResolvesCheck = (uSide == WHITE) ? + (cAttacker == cEp + 16) : (cAttacker == cEp - 16); + + if (fEpResolvesCheck) + { + cFrom = cEp + iBehindDelta - 1; + if (IS_ON_BOARD(cFrom) && + IS_PAWN(pos->rgSquare[cFrom].pPiece) && + (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide)) + { + _AddEnPassant(pStack, pos, cFrom, cEp); + } + cFrom = cEp + iBehindDelta + 1; + if (IS_ON_BOARD(cFrom) && + IS_PAWN(pos->rgSquare[cFrom].pPiece) && + (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide)) + { + _AddEnPassant(pStack, pos, cFrom, cEp); + } + } + } +} + void InvalidGenerator(IN UNUSED MOVE_STACK *pStack, @@ -2100,7 +3291,12 @@ Return value: } -static void +// Non-static (unlike its historical internal-only status) so +// testgenerate.c's whole-node dispatch benchmark can call it directly +// by name -- see _GenerateAllMovesBB's block comment for why that +// comparison needs both functions callable under their real names in +// a toggle-free build. +void _GenerateAllMoves(IN MOVE_STACK *pStack, IN POSITION *pos) /** @@ -2128,22 +3324,67 @@ Return value: InvalidGenerator, // EMPTY | WHITE InvalidGenerator, // 2 (BLACK_PAWN) InvalidGenerator, // 3 (WHITE_PAWN) + // MOVEGEN_MIGRATION.md section 6 toggle -- one #define per + // piece type, independent of the others. _GenerateKnightBB + // serves both slots; see its header comment for why the + // mailbox pair's color split doesn't carry over to bitboards. +#if defined(GENERATE_KNIGHT_BITBOARD) + _GenerateKnightBB, // 4 (BLACK_KNIGHT) + _GenerateKnightBB, // 5 (WHITE_KNIGHT) +#else GenerateKnight, // 4 (BLACK_KNIGHT) GenerateWhiteKnight, // 5 (WHITE_KNIGHT) +#endif +#if defined(GENERATE_BISHOP_BITBOARD) + _GenerateBishopBB, // 6 (BLACK_BISHOP) + _GenerateBishopBB, // 7 (WHITE_BISHOP) +#else GenerateBishop, // 6 (BLACK_BISHOP) GenerateBishop, // 7 (WHITE_BISHOP) +#endif +#if defined(GENERATE_ROOK_BITBOARD) + _GenerateRookBB, // 8 (BLACK_ROOK) + _GenerateRookBB, // 9 (WHITE_ROOK) +#else GenerateRook, // 8 (BLACK_ROOK) GenerateRook, // 9 (WHITE_ROOK) +#endif +#if defined(GENERATE_QUEEN_BITBOARD) + _GenerateQueenBB, // 10 (BLACK_QUEEN) + _GenerateQueenBB, // 11 (WHITE_QUEEN) +#else GenerateQueen, // 10 (BLACK_QUEEN) - GenerateQueen, // 11 (WHITE_QUEEN) + GenerateQueen, // 11 (WHITE_QUEEN) +#endif +#if defined(GENERATE_KING_BITBOARD) + _GenerateKingBB, // 12 (BLACK_KING) + _GenerateKingBB // 13 (WHITE_KING) +#else GenerateBlackKing, // 12 (BLACK_KING) GenerateWhiteKing // 13 (WHITE_KING) +#endif }; ULONG u; #ifdef DEBUG PIECE p; #endif + // See MOVE_STACK's bbFriendlyOccupied field comment (chess.h) and + // _GenerateKnightBB's header comment: computed once per node here, + // before any piece-type dispatch, so every bitboard-backed + // generator invoked below shares this build instead of each + // recomputing it -- extend this #if with each new + // GENERATE_*_BITBOARD toggle as piece types migrate. +#if defined(GENERATE_KNIGHT_BITBOARD) || defined(GENERATE_KING_BITBOARD) || \ + defined(GENERATE_ROOK_BITBOARD) || defined(GENERATE_BISHOP_BITBOARD) || \ + defined(GENERATE_QUEEN_BITBOARD) + pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, pos->uToMove); +#endif +#if defined(GENERATE_ROOK_BITBOARD) || defined(GENERATE_BISHOP_BITBOARD) || \ + defined(GENERATE_QUEEN_BITBOARD) + pStack->bbOccupied = _BuildFullOccupiedBB(pos); +#endif + for(u = pos->uNonPawnCount[pos->uToMove][0] - 1; u != (ULONG)-1; u--) @@ -2159,7 +3400,10 @@ Return value: (JumpTable[pos->rgSquare[c].pPiece])(pStack, pos, c); } - if (pos->uToMove == BLACK) +#if defined(GENERATE_PAWN_BITBOARD) + _GenerateAllPawnMovesBB(pStack, pos, pos->uToMove); +#else + if (pos->uToMove == BLACK) { for(u = 0; u < pos->uPawnCount[BLACK]; u++) { @@ -2175,7 +3419,7 @@ Return value: } } else { ASSERT(pos->uToMove == WHITE); - for(u = 0; u < pos->uPawnCount[WHITE]; u++) + for(u = 0; u < pos->uPawnCount[WHITE]; u++) { c = pos->cPawns[WHITE][u]; #ifdef DEBUG @@ -2188,8 +3432,188 @@ Return value: GenerateWhitePawn(pStack, pos, c); } } +#endif +} + +// +// board_representation/MOVEGEN_MIGRATION.md section 3: fully +// bitboard-driven alternative to _GenerateAllMoves, forked at this +// level (not folded into _GenerateAllMoves's own JumpTable-based body +// via an #if) specifically to eliminate _GenerateAllMoves's own +// indirect-call dispatch, not just to swap which per-piece-type +// function gets called. +// +// _GenerateAllMoves's cNonPawns[side][] loop is a flat list mixing all +// non-pawn piece types together (pieces are added/removed via +// swap-with-last, so there is no contiguous per-type range to slice) +// -- that mixed ordering is *why* it needs +// JumpTable[pos->rgSquare[c].pPiece], an indirect call whose target +// changes almost every iteration as the loop walks across different +// piece types, close to the worst case for a CPU's indirect-branch +// predictor. Every per-piece-type speed benchmark in this migration +// (testgenerate.c's TestGenerateKnightSpeed and friends) called its +// _Generate*BB function directly, bypassing JumpTable entirely -- so +// none of those numbers ever measured, or could benefit from +// removing, this dispatch cost. This function is the piece that +// actually exercises that question: pos->bbPieces[side][KNIGHT/ +// BISHOP/ROOK/QUEEN] already partitions squares by type (unlike +// cNonPawns), so each piece type gets its own bit-extraction loop +// calling its specific _Generate*BB function BY NAME -- a +// statically-known, likely-inlinable direct call, no function pointer +// anywhere in this function. +// +// Only exists (and is only substituted in for _GenerateAllMoves, see +// the #define below) when every non-pawn, non-castling piece type's +// bitboard toggle is defined -- a partial-rollout mix (e.g. knight and +// king migrated, rook/bishop/queen not yet) still needs +// _GenerateAllMoves's cNonPawns/JumpTable path, since that path is the +// only one that knows how to fall back to a still-mailbox piece type +// while also correctly finding already-migrated ones by iterating the +// same mixed list. This function does not attempt to support that +// mixed case -- see MOVEGEN_MIGRATION.md for why an all-or-nothing +// fork was chosen over threading partial-rollout support through this +// function too. +// +void +_GenerateAllMovesBB(IN MOVE_STACK *pStack, + IN POSITION *pos) +/** + +Routine description: + + Fully bitboard-driven equivalent of _GenerateAllMoves -- see the + block comment above. Produces the exact same pseudo-legal move set + (same over-generation behavior, no legal-awareness added, and no + change to which moves are generated, only how the dispatch to each + piece type's generator happens) -- see MOVEGEN_MIGRATION.md + section 1's explicit non-goal. + +Parameters: + + MOVE_STACK *pStack : the move stack + POSITION *pos : the board position + +Return value: + + static void + +**/ +{ + ULONG uSide = pos->uToMove; + BITBOARD bb; + ULONG uBitIndex; + COOR c; +#if !defined(GENERATE_PAWN_BITBOARD) + ULONG u; +#endif +#if defined(DEBUG) && !defined(GENERATE_PAWN_BITBOARD) + PIECE p; +#endif + + pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, uSide); + pStack->bbOccupied = _BuildFullOccupiedBB(pos); + + bb = pos->bbPieces[uSide][KNIGHT]; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + ASSERT(IS_KNIGHT(pos->rgSquare[c].pPiece)); + _GenerateKnightBB(pStack, pos, c); + } + + bb = pos->bbPieces[uSide][BISHOP]; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + ASSERT(IS_BISHOP(pos->rgSquare[c].pPiece)); + _GenerateBishopBB(pStack, pos, c); + } + + bb = pos->bbPieces[uSide][ROOK]; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + ASSERT(IS_ROOK(pos->rgSquare[c].pPiece)); + _GenerateRookBB(pStack, pos, c); + } + + bb = pos->bbPieces[uSide][QUEEN]; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + ASSERT(IS_QUEEN(pos->rgSquare[c].pPiece)); + _GenerateQueenBB(pStack, pos, c); + } + + // King has no bitboard of its own (a single square, cNonPawns[ + // side][0] -- see POSITION's bbPieces field comment in chess.h for + // why a bitboard would add nothing here); still a direct, + // statically-known call, same as the four loops above. + c = pos->cNonPawns[uSide][0]; + ASSERT(IS_KING(pos->rgSquare[c].pPiece)); + _GenerateKingBB(pStack, pos, c); + + // Pawns: unchanged from _GenerateAllMoves -- not in scope for this + // migration (section 3 step 5's pawn note) unless + // GENERATE_PAWN_BITBOARD is also defined, in which case pawns get + // the same bulk treatment via _GenerateAllPawnMovesBB -- pawns' + // own toggle is independent of the five above (section 6). +#if defined(GENERATE_PAWN_BITBOARD) + _GenerateAllPawnMovesBB(pStack, pos, uSide); +#else + if (uSide == BLACK) + { + for(u = 0; u < pos->uPawnCount[BLACK]; u++) + { + c = pos->cPawns[BLACK][u]; +#ifdef DEBUG + ASSERT(IS_ON_BOARD(c)); + p = pos->rgSquare[c].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(IS_PAWN(p)); + ASSERT(GET_COLOR(p) == uSide); +#endif + GenerateBlackPawn(pStack, pos, c); + } + } + else + { + ASSERT(uSide == WHITE); + for(u = 0; u < pos->uPawnCount[WHITE]; u++) + { + c = pos->cPawns[WHITE][u]; +#ifdef DEBUG + ASSERT(IS_ON_BOARD(c)); + p = pos->rgSquare[c].pPiece; + ASSERT(!IS_EMPTY(p)); + ASSERT(IS_PAWN(p)); + ASSERT(GET_COLOR(p) == uSide); +#endif + GenerateWhitePawn(pStack, pos, c); + } + } +#endif } +// Whole-dispatch fork -- see _GenerateAllMovesBB's block comment for +// why this is a #define swap of the entire function (matching +// chess.h's GetAttacks precedent) rather than a branch nested inside +// _GenerateAllMoves. Only fires when every non-pawn, non-castling +// piece type is bitboard-backed; any partial mix still uses +// _GenerateAllMoves's cNonPawns/JumpTable path unchanged. +#if defined(GENERATE_KNIGHT_BITBOARD) && defined(GENERATE_KING_BITBOARD) && \ + defined(GENERATE_ROOK_BITBOARD) && defined(GENERATE_BISHOP_BITBOARD) && \ + defined(GENERATE_QUEEN_BITBOARD) +#define _GenerateAllMoves _GenerateAllMovesBB +#endif static ULONG @@ -2219,17 +3643,28 @@ Return value: **/ { +#if !defined(GENERATE_ESCAPES_KING_BITBOARD) || !defined(GENERATE_ESCAPES_BLOCK_BITBOARD) ULONG u; +#endif +#if !defined(GENERATE_ESCAPES_KING_BITBOARD) ULONG v; +#endif COOR c; +#if !defined(GENERATE_ESCAPES_BLOCK_BITBOARD) COOR cDefender; +#endif PIECE p; PIECE pKing; COOR cKing = pos->cNonPawns[pos->uToMove][0]; +#if !defined(GENERATE_ESCAPES_KING_BITBOARD) int iIndex; +#endif SEE_LIST rgCheckers; +#if !defined(GENERATE_ESCAPES_KING_BITBOARD) int iDelta; +#endif ULONG uReturn = 0; +#if !defined(GENERATE_ESCAPES_BLOCK_BITBOARD) static void (*JumpTable[]) (MOVE_STACK *, POSITION *, COOR, COOR, COOR) = { @@ -2248,6 +3683,7 @@ Return value: InvalidSaveMe, // kings already considered InvalidSaveMe // kings already considered }; +#endif ASSERT(IS_KING(pos->rgSquare[cKing].pPiece)); ASSERT(TRUE == InCheck(pos, pos->uToMove)); @@ -2271,6 +3707,50 @@ Return value: ASSERT(GET_COLOR(pKing) == pos->uToMove); ASSERT(IS_KING(pKing)); ASSERT(OPPOSITE_COLORS(pKing, rgCheckers.data[0].pPiece)); +#if defined(GENERATE_ESCAPES_KING_BITBOARD) + // + // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 1: + // g_KingAttacksBB gives every candidate flight square in one + // lookup (already excludes friendly-occupied squares); the + // mailbox version's manual per-checker x-ray loop below is + // replaced entirely by testing _WhoAttacksSquareBB against + // occupancy with the king itself removed -- a slider whose ray + // was only blocked by the king's own (pre-move) body now correctly + // shows up as attacking a candidate square still on that ray, + // exactly the case the manual loop existed to catch by hand. + // Pawns are checked separately since _WhoAttacksSquareBB + // deliberately excludes them (see its header comment). + { + ULONG uEnemy = FLIP(pos->uToMove); + // pKing is only used inside ASSERTs below, which vanish in a + // non-DEBUG build -- silence the resulting "set but not used" + // warning explicitly rather than leave it looking accidental. + (void)pKing; + BITBOARD bbFriendly = _BuildFriendlySideBB(pos, pos->uToMove); + BITBOARD bbOccupiedWithoutKing = + _BuildFullOccupiedBB(pos) & ~COOR_TO_BB(cKing); + BITBOARD bbDest = g_KingAttacksBB[cKing] & ~bbFriendly; + ULONG uBitIndex; + + while (bbDest) + { + uBitIndex = FastFirstBit(bbDest) - 1; + bbDest &= (bbDest - 1); + c = BIT_NUMBER_TO_COOR(uBitIndex); + p = pos->rgSquare[c].pPiece; + ASSERT(IS_EMPTY(p) || OPPOSITE_COLORS(p, pKing)); + + if ((0 == _WhoAttacksSquareBB(pos, c, uEnemy, + bbOccupiedWithoutKing)) && + (0 == (g_PawnAttackOriginBB[uEnemy][c] & + pos->bbPawns[uEnemy]))) + { + _AddNormalMove(pStack, pos, cKing, c, p); + uReturn += 0x00010000; + } + } + } +#else u = 0; while(0 != g_iQKDeltas[u]) { @@ -2332,6 +3812,7 @@ Return value: loop: ; } +#endif // // N.B. If there is more than one piece checking the king then @@ -2370,6 +3851,74 @@ Return value: // checking piece. // c = rgCheckers.data[0].cLoc; +#if defined(GENERATE_ESCAPES_BLOCK_BITBOARD) + // + // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: + // pos->cNonPawns[side][] mixes every non-pawn piece type together + // (same reason as _GenerateAllMoves's own loop -- no contiguous + // per-type range to slice), which is why the mailbox path above + // needs JumpTable[p], an indirect call whose target changes almost + // every iteration -- close to the worst case for a CPU's + // indirect-branch predictor. pos->bbPieces[side][KNIGHT/BISHOP/ + // ROOK/QUEEN] sidesteps this exactly like _GenerateAllMovesBB did: + // each piece type gets its own bit-extraction loop calling its + // specific _SaveMe*BB function BY NAME, no function pointer + // anywhere in this block. + { + BITBOARD bbTargetMask; + BITBOARD bb; + ULONG uBitIndex; + COOR cDef; + + // Unlike _GenerateAllMoves, GENERATE_ESCAPES's call site never + // precomputes these -- set them here, once, for every + // _SaveMe*BB call below to share (same amortization reasoning + // as _GenerateAllMoves's own precompute block). + pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, pos->uToMove); + pStack->bbOccupied = _BuildFullOccupiedBB(pos); + bbTargetMask = + _ComputeCheckTargetMaskBB(cKing, c, pStack->bbOccupied); + + bb = pos->bbPieces[pos->uToMove][KNIGHT]; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cDef = BIT_NUMBER_TO_COOR(uBitIndex); + _SaveMeKnightBB(pStack, pos, cDef, cKing, bbTargetMask); + } + + bb = pos->bbPieces[pos->uToMove][BISHOP]; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cDef = BIT_NUMBER_TO_COOR(uBitIndex); + _SaveMeBishopBB(pStack, pos, cDef, cKing, bbTargetMask); + } + + bb = pos->bbPieces[pos->uToMove][ROOK]; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cDef = BIT_NUMBER_TO_COOR(uBitIndex); + _SaveMeRookBB(pStack, pos, cDef, cKing, bbTargetMask); + } + + bb = pos->bbPieces[pos->uToMove][QUEEN]; + while (bb) + { + uBitIndex = FastFirstBit(bb) - 1; + bb &= (bb - 1); + cDef = BIT_NUMBER_TO_COOR(uBitIndex); + _SaveMeQueenBB(pStack, pos, cDef, cKing, bbTargetMask); + } + + _SaveMeAllPawnMovesBB(pStack, pos, pos->uToMove, cKing, c, + bbTargetMask); + } +#else for (u = 1; // don't consider the king u < pos->uNonPawnCount[pos->uToMove][0]; u++) @@ -2384,7 +3933,7 @@ Return value: } // Consider all pawns too - if (pos->uToMove == BLACK) + if (pos->uToMove == BLACK) { for (u = 0; u < pos->uPawnCount[BLACK]; u++) { @@ -2399,7 +3948,7 @@ Return value: } } else { ASSERT(pos->uToMove == WHITE); - for (u = 0; u < pos->uPawnCount[WHITE]; u++) + for (u = 0; u < pos->uPawnCount[WHITE]; u++) { cDefender = pos->cPawns[WHITE][u]; #ifdef DEBUG @@ -2411,6 +3960,7 @@ Return value: SaveMeWhitePawn(pStack, pos, cDefender, cKing, c); } } +#endif return(uReturn); } @@ -451,7 +451,11 @@ Return value: **/ { - srand((unsigned int)time(0)); + { + unsigned int uSeed = (unsigned int)time(0); + Trace("srand seed: %u\n", uSeed); + srand(uSeed); + } InitializeOptions(argc, argv); InitializeTreeDump(); InitializeEGTB(); @@ -464,7 +468,9 @@ Return value: InitializeRookRayTables(); InitializeBishopRayTables(); InitializeKnightAttackTables(); + InitializeKingAttackTables(); InitializePawnAttackOriginTable(); + InitMagic(); InitializeOpeningBook(); InitializeDynamicMoveOrdering(); InitLMRTable(); @@ -588,8 +594,15 @@ Return value: TestSan(); TestIcs(); TestGetAttacks(); + TestIsAttackedBB(); TestMoveGenerator(); TestLegalMoveGenerator(); + TestGenerateKnightSpeed(); + TestGenerateKingSpeed(); + TestGenerateRookSpeed(); + TestGenerateBishopSpeed(); + TestGenerateQueenSpeed(); + TestGenerateAllMovesSpeed(); TestFenCode(); TestLiftPlaceSlidePiece(); TestExposesCheck(); diff --git a/src/movesup.c b/src/movesup.c index 33deae2..22bf0c1 100755 --- a/src/movesup.c +++ b/src/movesup.c @@ -23,7 +23,324 @@ Revision History: #include "chess.h" -COOR +// Unlike GetAttacks (a real asm symbol in a different file, so +// chess.h's macro-swap never touches its own definition), +// ExposesCheck/FasterExposesCheck/ExposesCheckEp's mailbox +// implementations live in *this* file, right below their BB +// counterparts -- chess.h's #define would otherwise rename these +// functions' own definitions too, colliding with the real +// ExposesCheckBB/etc. symbols. #undef restores the real names for +// this file's own definitions; every other translation unit that +// includes chess.h still sees the macro-renamed calls. +#if defined(EXPOSESCHECK_BITBOARD) +#undef ExposesCheck +#undef FasterExposesCheck +#undef ExposesCheckEp +#endif +#if defined(ISATTACKED_BITBOARD) +#undef IsAttacked +#undef InCheck +#endif + +// board_representation/MOVEGEN_MIGRATION.md section 6b: bitboard +// equivalents of ExposesCheck/FasterExposesCheck/ExposesCheckEp. +// ExposesCheck is called from MakeMove (move.c) on essentially every +// move actually played during search -- the pin-legality safety net +// every generator's header comment references -- making it a much +// hotter target than anything in generate.c's own Part A/B work. +// +// Design: keep the mailbox version's own O(1) alignment pre-check +// (CHECK_VECTOR_WITH_INDEX -- already a table lookup, nothing to +// improve) to bail out on the common "not even aligned" case before +// paying for any bitboard work at all. Only when aligned: exclude the +// hypothetically-removed square(s) from occupancy, magic-lookup the +// attack set from cLocation against that occupancy, and mask to the +// single ray through cRemove via g_RookRayToEdge/g_BishopRayToEdge +// (so an unrelated attacker on a *different* ray through cLocation +// can't falsely register) -- then apply the same enemy-color/ +// piece-type check the mailbox version does on whatever single square +// survives. +// Finds the single nearest occupied square along one specific +// direction from c, or ILLEGAL_COOR if that ray is empty all the way +// to the edge. This is *not* "magic attack bitboard ANDed with a ray +// mask" -- that was tried first and is wrong: an unblocked ray's magic +// attack set contains every empty square out to the edge, and +// FastFirstBit on that intersection picks the lowest square index +// overall, which is not necessarily the square nearest c (bit index +// order and "distance from c" only coincide for one of the two +// possible directions along any given ray). The correct technique, +// mirrored exactly from _WhoAttacksSquareBB (see.c): isolate the +// lowest set bit for a "positive" direction (bb & -bb, no bit-scan +// needed) or the highest set bit for a "negative" direction +// (1ULL << (FastLastBit-1)) -- g_RookRayPositiveDir/ +// g_BishopRayPositiveDir already record which is which per direction. +static COOR +_NearestBlockerAlongRayBB(IN COOR c, IN int iDeltaFromC, + IN BITBOARD bbOccupied) +/** + +Routine description: + + Nearest occupied square from c along the single queen-direction + iDeltaFromC, or ILLEGAL_COOR if none. + +Parameters: + + COOR c + int iDeltaFromC : one of g_iQKDeltas's 8 values + BITBOARD bbOccupied + +Return value: + + COOR + +**/ +{ + BITBOARD bbRay; + BITBOARD bbBlockers; + BITBOARD bbBlockerBit; + FLAG fPositiveDir; + ULONG uBitIndex; + + switch (iDeltaFromC) + { + case 16: + bbRay = g_RookRayToEdge[0][c]; + fPositiveDir = g_RookRayPositiveDir[0]; + break; + case -16: + bbRay = g_RookRayToEdge[1][c]; + fPositiveDir = g_RookRayPositiveDir[1]; + break; + case 1: + bbRay = g_RookRayToEdge[2][c]; + fPositiveDir = g_RookRayPositiveDir[2]; + break; + case -1: + bbRay = g_RookRayToEdge[3][c]; + fPositiveDir = g_RookRayPositiveDir[3]; + break; + case 17: + bbRay = g_BishopRayToEdge[0][c]; + fPositiveDir = g_BishopRayPositiveDir[0]; + break; + case -17: + bbRay = g_BishopRayToEdge[1][c]; + fPositiveDir = g_BishopRayPositiveDir[1]; + break; + case 15: + bbRay = g_BishopRayToEdge[2][c]; + fPositiveDir = g_BishopRayPositiveDir[2]; + break; + case -15: + bbRay = g_BishopRayToEdge[3][c]; + fPositiveDir = g_BishopRayPositiveDir[3]; + break; + default: + ASSERT(FALSE); + return(ILLEGAL_COOR); + } + + bbBlockers = bbRay & bbOccupied; + if (0 == bbBlockers) + { + return(ILLEGAL_COOR); + } + bbBlockerBit = fPositiveDir ? + (bbBlockers & (0ULL - bbBlockers)) : + (1ULL << (FastLastBit(bbBlockers) - 1)); + uBitIndex = FastFirstBit(bbBlockerBit) - 1; + return BIT_NUMBER_TO_COOR(uBitIndex); +} + +// Shared tail: given a candidate blocker square, apply the same +// enemy-color / piece-type-can-reach-us check the mailbox versions do, +// and return it (or ILLEGAL_COOR). +static COOR +_ValidateExposedBlockerBB(IN POSITION *pos, IN COOR cBlocker, + IN COOR cLocation) +{ + PIECE xPiece; + int iIndex; + + if (!IS_ON_BOARD(cBlocker)) + { + return(ILLEGAL_COOR); + } + xPiece = pos->rgSquare[cBlocker].pPiece; + ASSERT(!IS_EMPTY(xPiece)); + + if (OPPOSITE_COLORS(xPiece, pos->rgSquare[cLocation].pPiece)) + { + iIndex = (int)cBlocker - (int)cLocation; + if (0 != (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(xPiece)) & + (1 << (PIECE_TYPE(xPiece))))) + { + return(cBlocker); + } + } + return(ILLEGAL_COOR); +} + +COOR +FasterExposesCheckBB(IN POSITION *pos, + IN COOR cRemove, + IN COOR cLocation) +/** + +Routine description: + + Bitboard equivalent of FasterExposesCheck -- see that function's + comment. Caller already knows exposure is geometrically possible + (skips the alignment pre-check FasterExposesCheck also skips). + +Parameters: + + POSITION *pos, + COOR cRemove, + COOR cLocation + +Return value: + + COOR + +**/ +{ + int iIndex = (int)cLocation - (int)cRemove; + int iDelta; + BITBOARD bbOccupiedWithoutRemove; + COOR cBlocker; + + ASSERT(IS_KING(pos->rgSquare[cLocation].pPiece)); + ASSERT(IS_ON_BOARD(cRemove)); + ASSERT(IS_ON_BOARD(cLocation)); + ASSERT(!IS_EMPTY(pos->rgSquare[cLocation].pPiece)); + ASSERT(0 != (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))); + + iDelta = CHECK_DELTA_WITH_INDEX(iIndex); + ASSERT(iDelta != 0); + + bbOccupiedWithoutRemove = _BuildFullOccupiedBB(pos) & ~COOR_TO_BB(cRemove); + cBlocker = _NearestBlockerAlongRayBB(cLocation, iDelta, + bbOccupiedWithoutRemove); + return _ValidateExposedBlockerBB(pos, cBlocker, cLocation); +} + +COOR +ExposesCheckBB(IN POSITION *pos, + IN COOR cRemove, + IN COOR cLocation) +/** + +Routine description: + + Bitboard equivalent of ExposesCheck -- see that function's comment. + +Parameters: + + POSITION *pos : the board + COOR cRemove : the square where a piece hypothetically removed from + COOR cLocation : the square where the attackee is sitting + +Return value: + + COOR : the location of an attacker piece or 0x88 (!IS_ON_BOARD) if + the removal of cRemove does not expose check. + +**/ +{ + int iIndex = (int)cLocation - (int)cRemove; + int iDelta; + BITBOARD bbOccupiedWithoutRemove; + COOR cBlocker; + + ASSERT(IS_ON_BOARD(cRemove)); + ASSERT(IS_ON_BOARD(cLocation)); + ASSERT(!IS_EMPTY(pos->rgSquare[cLocation].pPiece)); + + // + // If there is no way for a queen sitting at the square removed to + // reach the square we are testing (i.e. the two squares are not + // on the same rank, file, or diagonal) then there is no way + // removing it can expose cLocation to check. + // + if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))) + { + return(ILLEGAL_COOR); + } + iDelta = CHECK_DELTA_WITH_INDEX(iIndex); + + bbOccupiedWithoutRemove = _BuildFullOccupiedBB(pos) & ~COOR_TO_BB(cRemove); + cBlocker = _NearestBlockerAlongRayBB(cLocation, iDelta, + bbOccupiedWithoutRemove); + return _ValidateExposedBlockerBB(pos, cBlocker, cLocation); +} + +COOR +ExposesCheckEpBB(IN POSITION *pos, + IN COOR cTest, + IN COOR cIgnore, + IN COOR cBlock, + IN COOR cKing) +/** + +Routine description: + + Bitboard equivalent of ExposesCheckEp -- see that function's + comment. Two squares are excluded from occupancy (cTest, the + captured pawn; cIgnore, the capturing pawn's origin) and one is + forced occupied (cBlock, the capturing pawn's destination) -- + matching the mailbox version's own "pretend the en passant capture + already happened" bookkeeping. + +Parameters: + + POSITION *pos, + COOR cTest : the square the attack would come from + COOR cIgnore : ignore this square, the pawn moved + COOR cBlock : this square is where the pawn moved to and now blocks + COOR cKing : the square under attack + +Return value: + + COOR + +**/ +{ + int iIndex = (int)cKing - (int)cTest; + int iDelta; + BITBOARD bbOccupied; + COOR cBlocker; + + ASSERT(IS_ON_BOARD(cTest)); + ASSERT(IS_ON_BOARD(cIgnore)); + ASSERT(IS_ON_BOARD(cBlock)); + ASSERT(IS_ON_BOARD(cKing)); + + if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))) + { + return(ILLEGAL_COOR); + } + iDelta = CHECK_DELTA_WITH_INDEX(iIndex); + + bbOccupied = (_BuildFullOccupiedBB(pos) & + ~COOR_TO_BB(cTest) & ~COOR_TO_BB(cIgnore)) | + COOR_TO_BB(cBlock); + cBlocker = _NearestBlockerAlongRayBB(cKing, iDelta, bbOccupied); + + // cBlock is forced-occupied above purely to stop the ray there -- + // it may not really hold a piece yet (pre-move state), so it must + // be recognized and treated as "safe" directly, not run through + // pos->rgSquare's real (stale) contents, exactly like the mailbox + // version's explicit early check. + if (cBlocker == cBlock) + { + return(ILLEGAL_COOR); + } + return _ValidateExposedBlockerBB(pos, cBlocker, cKing); +} + +COOR FasterExposesCheck(POSITION *pos, COOR cRemove, COOR cLocation) @@ -282,7 +599,85 @@ Return value: } -FLAG +// +// board_representation/MOVEGEN_MIGRATION.md section 6b: bitboard +// equivalent of IsAttacked/InCheck. IsAttacked's own direct callers +// (move.c/san.c castling-through-check legality) are cold, but InCheck +// -- a thin wrapper around it -- has ~70 call sites across +// search.c/move.c/eval.c/root.c/dynamic.c, called constantly through +// search; this is a much hotter target than its direct-caller count +// alone would suggest. +// +// Design: _WhoAttacksSquareBB (see.c, already exposed) already answers +// "which of uSide's knight/bishop/rook/queen/king pieces attack this +// square" via the same magic-table substrate as everything else in +// this migration -- IsAttackedBB is just that function reduced to a +// boolean, plus a separate pawn-attack check via g_PawnAttackOriginBB +// (since _WhoAttacksSquareBB deliberately excludes pawns -- see its +// own header comment). +// +FLAG +IsAttackedBB(IN COOR cTest, IN POSITION *pos, IN ULONG uSide) +/** + +Routine description: + + Bitboard equivalent of IsAttacked -- see that function's comment. + +Parameters: + + COOR cTest : the square we want to determine if is under attack + POSITION *pos : the board + ULONG uSide : the side we want to see if is attacking cTest + +Return value: + + FLAG : TRUE if uSide attacks cTest, FALSE otherwise + +**/ +{ + BITBOARD bbOccupied; + + ASSERT(IS_ON_BOARD(cTest)); + ASSERT(IS_VALID_COLOR(uSide)); + + bbOccupied = _BuildFullOccupiedBB(pos); + if (0 != _WhoAttacksSquareBB(pos, cTest, uSide, bbOccupied)) + { + return(TRUE); + } + return(0 != (g_PawnAttackOriginBB[uSide][cTest] & pos->bbPawns[uSide])); +} + +FLAG +InCheckBB(IN POSITION *pos, IN ULONG uSide) +/** + +Routine description: + + Bitboard equivalent of InCheck -- see that function's comment. + +Parameters: + + POSITION *pos : the board + ULONG uSide : the side we want to determine if is in check + +Return value: + + FLAG : TRUE if side is in check, FALSE otherwise. + +**/ +{ + COOR cKingLoc = pos->cNonPawns[uSide][0]; + + ASSERT(IS_VALID_COLOR(uSide)); + ASSERT(IS_KING(pos->rgSquare[cKingLoc].pPiece)); + ASSERT(GET_COLOR(pos->rgSquare[cKingLoc].pPiece) == uSide); + + return IsAttackedBB(cKingLoc, pos, FLIP(uSide)); +} + +FLAG IsAttacked(COOR cTest, POSITION *pos, ULONG uSide) /** @@ -201,7 +201,13 @@ Return value: COOR_TO_BB(pos->cNonPawns[BLACK][0])); } -static BITBOARD +// Non-static (unlike its historical file-local status) so +// generate.c's Part B (_GenerateEscapes) bitboard work can call it +// directly for king-flight safety testing, passing an occupancy +// bitboard with the king itself removed to correctly account for +// x-ray/discovered attacks when the king steps out of a slider's way +// -- see board_representation/MOVEGEN_MIGRATION.md section 6a. +BITBOARD _WhoAttacksSquareBB(IN POSITION *pos, IN COOR cSquare, IN ULONG uSide, diff --git a/src/testgenerate.c b/src/testgenerate.c index 5fdf30f..c6947d2 100755 --- a/src/testgenerate.c +++ b/src/testgenerate.c @@ -244,4 +244,457 @@ TestLegalMoveGenerator(void) while(u < 1000); SystemFreeMemory(ctx); } + +// +// board_representation/MOVEGEN_MIGRATION.md section 5's isolated +// cycles/call microbenchmark for the knight generator -- modeled +// directly on testsee.c's TestGetAttacks speed block (interleaved +// call-by-call across opening/middlegame/endgame positions, to cancel +// shared-box noise). Correctness for this piece type is already +// covered by TestMoveGenerator's perft counts (with +// GENERATE_KNIGHT_BITBOARD defined) -- this only answers "is it +// faster," the section 5 gate before a piece type's toggle is +// considered for default-on. +// +void +TestGenerateKnightSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/3KN3/8/8/8/8 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcKnight[3] = { B1, C3, E5 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking knight move generation: mailbox vs " + "_GenerateKnightBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_KNIGHT(posBench.rgSquare[rgcKnight[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcKnight[u]].pPiece) == + posBench.uToMove); + + // _GenerateKnightBB relies on this being set by its caller + // (normally _GenerateAllMoves, once per node) -- see + // MOVE_STACK's bbFriendlyOccupied field comment in chess.h. + // Computed once per benchmark position, not per call, matching + // how the real call site amortizes it. + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateWhiteKnight(&ctx->sMoveStack, &posBench, rgcKnight[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateKnightBB(&ctx->sMoveStack, &posBench, rgcKnight[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateKnightBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Same shape as TestGenerateKnightSpeed, for the king. Opening position +// has castling rights but blocked by intervening pieces (exercises the +// emptiness-check branch's cost without ever actually reaching +// _AddCastle); middlegame is already castled (no rights, cheapest +// castling-tail exit); endgame is a bare king on an open board (no +// rights either, but the most normal-move destinations to enumerate). +// +void +TestGenerateKingSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/4K3/8/8/8/8 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcKing[3] = { E1, G1, E5 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking king move generation: mailbox vs " + "_GenerateKingBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_KING(posBench.rgSquare[rgcKing[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcKing[u]].pPiece) == + posBench.uToMove); + + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateWhiteKing(&ctx->sMoveStack, &posBench, rgcKing[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateKingBB(&ctx->sMoveStack, &posBench, rgcKing[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateKingBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Same shape as TestGenerateKnightSpeed/TestGenerateKingSpeed, for the +// rook -- but unlike those two, this piece type is expected to +// actually win: rook a1 is fully blocked in the opening (0 +// destinations, cheapest case either way), partially open in the +// middlegame, and nearly fully open in the endgame (up to 13 +// destinations along an empty file/rank) -- exactly the case a +// 4-direction ray walk pays for and a magic lookup doesn't. +// +void +TestGenerateRookSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/3K4/8/8/8/R7 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcRook[3] = { A1, A1, A1 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking rook move generation: mailbox vs " + "_GenerateRookBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_ROOK(posBench.rgSquare[rgcRook[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcRook[u]].pPiece) == + posBench.uToMove); + + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + ctx->sMoveStack.bbOccupied = _BuildFullOccupiedBB(&posBench); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateRook(&ctx->sMoveStack, &posBench, rgcRook[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateRookBB(&ctx->sMoveStack, &posBench, rgcRook[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateRookBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Same shape as TestGenerateRookSpeed, for the bishop -- expect the +// same parity result (see MOVEGEN_MIGRATION.md section 3's rook +// entry for why), not a different outcome, since the underlying +// reason applies identically to diagonals. +// +void +TestGenerateBishopSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/3K4/8/8/8/B7 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcBishop[3] = { C1, D3, A1 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking bishop move generation: mailbox vs " + "_GenerateBishopBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_BISHOP(posBench.rgSquare[rgcBishop[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcBishop[u]].pPiece) == + posBench.uToMove); + + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + ctx->sMoveStack.bbOccupied = _BuildFullOccupiedBB(&posBench); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateBishop(&ctx->sMoveStack, &posBench, rgcBishop[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateBishopBB(&ctx->sMoveStack, &posBench, rgcBishop[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateBishopBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Same shape as TestGenerateRookSpeed/TestGenerateBishopSpeed, for the +// queen -- expect the same parity-or-slightly-worse result, plus an +// extra fixed cost this time (two magic lookups instead of one) -- +// see MOVEGEN_MIGRATION.md section 3's rook entry for why a win was +// never really on the table for this piece type either. +// +void +TestGenerateQueenSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1b2rk1/pp2bppp/2n1pn2/2pp4/3P4/1QNBPN2/PP3PPP/R3KB1R w - - 0 1", + "8/5k2/8/3K4/8/8/8/Q7 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcQueen[3] = { D1, B3, A1 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking queen move generation: mailbox vs " + "_GenerateQueenBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_QUEEN(posBench.rgSquare[rgcQueen[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcQueen[u]].pPiece) == + posBench.uToMove); + + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + ctx->sMoveStack.bbOccupied = _BuildFullOccupiedBB(&posBench); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateQueen(&ctx->sMoveStack, &posBench, rgcQueen[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateQueenBB(&ctx->sMoveStack, &posBench, rgcQueen[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateQueenBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Whole-node dispatch benchmark: _GenerateAllMoves (mailbox +// cNonPawns/JumpTable dispatch) vs _GenerateAllMovesBB (direct calls +// off pos->bbPieces, no indirect branch) -- see _GenerateAllMovesBB's +// block comment in generate.c. Unlike every other benchmark in this +// file, this measures the dispatch layer itself, not an individual +// piece-type generator in isolation -- the level this migration's +// indirect-call-misprediction hypothesis actually predicts a win at. +// Must be run in a build with none of the GENERATE_*_BITBOARD toggles +// defined, so _GenerateAllMoves keeps its real name (not +// macro-substituted to _GenerateAllMovesBB) and both are directly +// comparable under their own names in one binary. +// +void +TestGenerateAllMovesSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "6k1/8/8/3K4/8/2NBRQ2/8/8 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking whole-node move generation dispatch: " + "_GenerateAllMoves (mailbox JumpTable) vs _GenerateAllMovesBB " + "(direct bbPieces dispatch), interleaved, %lu calls/position " + "-- only meaningful in a toggle-free build...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateAllMoves(&ctx->sMoveStack, &posBench); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateAllMovesBB(&ctx->sMoveStack, &posBench); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, BB dispatch %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} #endif diff --git a/src/testsearch.c b/src/testsearch.c index 380dfba..3d560ac 100644 --- a/src/testsearch.c +++ b/src/testsearch.c @@ -53,8 +53,19 @@ TestSearch(void) for (u = 0; u < 20; u++) { GenerateRandomLegalPosition(&pos); + // Log the exact FEN before searching it -- a crash partway + // through this loop otherwise gives no way to reproduce which + // of the 20 random positions triggered it (this cost real + // debugging time chasing an intermittent failure whose + // position was never captured -- see board_representation/ + // MOVEGEN_MIGRATION.md section 6b). + { + char *pszFen = PositionToFen(&pos); + Trace("TestSearch position %lu/20: %s\n", u + 1, + pszFen ? pszFen : "(PositionToFen failed)"); + } InitializeSearcherContext(&pos, ctx); - + g_MoveTimer.bvFlags = 0; g_Options.fPondering = FALSE; g_Options.fThinking = TRUE; diff --git a/src/testsee.c b/src/testsee.c index 2106494..d196d54 100644 --- a/src/testsee.c +++ b/src/testsee.c @@ -39,6 +39,19 @@ Revision History: #undef GetAttacks #endif +// Same reasoning, for IsAttacked/InCheck (board_representation/ +// MOVEGEN_MIGRATION.md section 6b's ISATTACKED_BITBOARD toggle): +// TestIsAttackedBB below must always be able to call the real mailbox +// IsAttacked by name and compare it against IsAttackedBB explicitly, +// regardless of which one chess.h's macro currently routes plain +// "IsAttacked(...)" calls to elsewhere in the engine. +#ifdef IsAttacked +#undef IsAttacked +#endif +#ifdef InCheck +#undef InCheck +#endif + #ifdef TEST_BROKEN ULONG g_uRootOnMove; @@ -320,4 +333,116 @@ TestGetAttacks(void) } } } + +// board_representation/MOVEGEN_MIGRATION.md section 6b: direct +// comparison harness for IsAttacked/IsAttackedBB, same pattern as +// TestGetAttacks above -- mailbox vs. bitboard, same inputs, must +// match exactly. This is the piece ExposesCheckBB didn't get before +// shipping and had to be debugged the hard way instead (two real bugs +// found via TestSan/perft/DEBUG-assert failures rather than a direct +// comparison); doing it properly here from the start. +void +TestIsAttackedBB(void) +{ + POSITION pos; + ULONG u; + COOR c; + ULONG uSide; + FLAG fMailbox, fBB; + + Trace("Testing IsAttacked...\n"); + for (u = 0; u < 20000; u++) + { + GenerateRandomLegalPosition(&pos); + FOREACH_SQUARE(c) + { + if (!IS_ON_BOARD(c)) continue; + for (uSide = BLACK; uSide <= WHITE; uSide++) + { + fMailbox = IsAttacked(c, &pos, uSide); + fBB = IsAttackedBB(c, &pos, uSide); + if (fMailbox != fBB) + { + UtilPanic(TESTCASE_FAILURE, + &pos, + "IsAttacked/IsAttackedBB mismatch", + NULL, NULL, + __FILE__, __LINE__); + } + } + } + for (uSide = BLACK; uSide <= WHITE; uSide++) + { + fMailbox = InCheck(&pos, uSide); + fBB = InCheckBB(&pos, uSide); + if (fMailbox != fBB) + { + UtilPanic(TESTCASE_FAILURE, + &pos, + "InCheck/InCheckBB mismatch", + NULL, NULL, + __FILE__, __LINE__); + } + } + } + + // + // Speed: same isolated cycles/call methodology as TestGetAttacks + // above, interleaved call-by-call to cancel shared-box noise. + // + { + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/3K4/8/8/8/4R3 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + POSITION posBench; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter; + ULONG uSq; + COOR cBench; + ULONG uSideBench; + const ULONG uCallsPerPosition = 200000; + FLAG fSink; + + Trace("Benchmarking IsAttacked: mailbox vs IsAttackedBB " + "(interleaved, %lu calls/position)...\n", + uCallsPerPosition); + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + uSq = uIter % 64; + cBench = BIT_NUMBER_TO_COOR(uSq); + uSideBench = uIter & 1; + if (!IS_ON_BOARD(cBench)) continue; + + u64Start = SystemReadTimeStampCounter(); + fSink = IsAttacked(cBench, &posBench, uSideBench); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + u64Start = SystemReadTimeStampCounter(); + fSink = IsAttackedBB(cBench, &posBench, uSideBench); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + (void)fSink; + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, IsAttackedBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + } +} #endif // TEST diff --git a/src/testsup.c b/src/testsup.c index 3ed50e3..d1b102d 100644 --- a/src/testsup.c +++ b/src/testsup.c @@ -87,7 +87,25 @@ GenerateRandomLegalPosition(POSITION *pos) { pos->cNonPawns[WHITE][u] = pos->cNonPawns[BLACK][u] = ILLEGAL_COOR; } - + + // memset above zeroes cEpSquare to 0x00 (A8), a real on-board + // square, not the "no en passant" sentinel -- every random + // position generated by this function had a bogus "en passant + // available on a8" flag set regardless of whether that made + // any sense. Both the mailbox and bitboard pawn generators + // trust this field and will act on it (mailbox: any pawn whose + // normal diagonal-capture target happens to coincide with a8; + // bitboard: proactively, once per side per node, since + // _GenerateAllPawnMovesBB/_SaveMeAllPawnMovesBB gate their + // en-passant block on IS_ON_BOARD(cEpSquare) directly) -- + // constructing a garbage "en passant capture" move whenever a + // pawn of the right color happens to sit on b7 by pure chance, + // which corrupts position state and was traced back to an + // intermittent TestSearch segfault (board_representation/ + // MOVEGEN_MIGRATION.md section 6b). + pos->cEpSquare = ILLEGAL_COOR; + + // // Place both kings legally // |