diff options
| -rwxr-xr-x | src/board.c | 16 | ||||
| -rw-r--r-- | src/board_representation/MIGRATION.md | 403 | ||||
| -rwxr-xr-x | src/chess.h | 43 | ||||
| -rwxr-xr-x | src/data.c | 157 | ||||
| -rwxr-xr-x | src/fen.c | 1 | ||||
| -rwxr-xr-x | src/main.c | 3 | ||||
| -rwxr-xr-x | src/move.c | 24 | ||||
| -rw-r--r-- | src/testbitboard.c | 31 |
8 files changed, 665 insertions, 13 deletions
diff --git a/src/board.c b/src/board.c index 5ad0d17..0c5f4df 100755 --- a/src/board.c +++ b/src/board.c @@ -168,6 +168,7 @@ Return value: "More pieces on board than accounted for in piece material", "Extra pieces on board that are not accounted for", "Fifty move counter is too high", + "bbPieces bitboard doesn't match piece list", }; ULONG u, v; COOR c; @@ -175,6 +176,7 @@ Return value: ULONG uPawnCount[2] = {0, 0}; ULONG uNonPawnMaterial[2] = {0, 0}; ULONG uNonPawnCount[2][7]; + BITBOARD bbPieces[2][8]; ULONG uSigmaNonPawnCount[2] = {0, 0}; ULONG uWhiteSqBishopCount[2] = {0, 0}; UINT64 u64Computed; @@ -183,6 +185,7 @@ Return value: ULONG uReason = (ULONG)-1; memset(uNonPawnCount, 0, sizeof(uNonPawnCount)); + memset(bbPieces, 0, sizeof(bbPieces)); u64Computed = ComputeSig(pos); if (pos->u64NonPawnSig != u64Computed) { @@ -305,6 +308,10 @@ Return value: goto end; } uNonPawnCount[u][PIECE_TYPE(p)]++; + if (!IS_KING(p)) + { + bbPieces[u][PIECE_TYPE(p)] |= COOR_TO_BB(c); + } uNonPawnMaterial[u] += PIECE_VALUE(p); if ((IS_BISHOP(p)) && (IS_WHITE_SQUARE_COOR(c))) @@ -348,6 +355,15 @@ Return value: uSigmaNonPawnCount[u] += pos->uNonPawnCount[u][v]; } + for (v = KNIGHT; v < KING; v++) + { + if (pos->bbPieces[u][v] != bbPieces[u][v]) + { + uReason = 21; + goto end; + } + } + // // Note: the 0th spot in the array is the sum of all non pawns // diff --git a/src/board_representation/MIGRATION.md b/src/board_representation/MIGRATION.md new file mode 100644 index 0000000..226e37e --- /dev/null +++ b/src/board_representation/MIGRATION.md @@ -0,0 +1,403 @@ +# Migration plan: bitboard-backed `GetAttacks` and `CountKingSafetyDefects` + +**Status: section 1 (and its correctness gate, section 2) implemented, +verified, uncommitted on disk. Sections 3-8 not started.** See the +per-section status notes below for specifics. + +Context: a prior pass of this session added occupancy-bitboard-driven +mobility/attack-presence bitboards (`bbPawnAttacks`, `bbMinorAttacks`, +`bbRookAttacks`, `bbQueenAttacks`, `bbKingAttacks`, plus xray variants) to +`POSITION`, rebuilt from scratch inside every `Eval()` call, additive +alongside the pre-existing per-square `rgSquare[c|8].bvAttacks` mailbox +struct. Measured via a dedicated `evalcycles` command (rdtsc-based, +compared against a `git worktree` build of pre-migration HEAD, since none +of this work was committed): the new code is **17-41% slower per `Eval()` +call**, consistently, across 5 representative positions. Root cause: pure +duplication -- every mobility function still does the original mailbox +ray-walk *and* now also writes the bitboards, so every position pays for +both representations and nothing was ever removed to pay for it. + +That result reframed the question: the win isn't "add more bitboards to +Eval," it's picking the *right* bitboards in the *right* place. This +document is the plan for that -- two functions sharing one new bitboard +primitive: + +1. **`GetAttacks`** (the SEE support routine in `see.c` / `x86.asm` / + `x64.asm`), called far more often per node than `Eval()` -- every + capture move considered in move ordering, at every node, via + `generate.c`'s 5 call sites and `searchsup.c:365`. +2. **`CountKingSafetyDefects`** (`eval.c:2408`), which turns out to be an + even more pervasive case of the same problem: it's called not just + from `Eval()` (`eval.c:7386-7387`, `eval.c:2549-2550`) but directly + from search-tree pruning/extension decisions -- `search.c:1252`, + `searchsup.c:484`, `searchsup.c:902,905` -- meaning it runs at search + nodes regardless of whether `Eval()` is even reached at that node. + +Both do the exact same thing algorithmically: walk every one of a side's +non-pawn pieces with a geometry-table lookup (`CHECK_VECTOR`) and, for +sliders, a manual mailbox ray-walk, to answer "does this piece attack (or +point at) this particular square" -- `GetAttacks`'s target is the move's +destination square, `CountKingSafetyDefects`'s target is the king's +square. O(pieces) candidates x O(ray length), every call, regardless of +how close any given piece actually is to the target square. Both are +strong candidates for the same fix, because both reduce to the same +underlying query: "which of this side's pieces attack square X." + +## -1. Current repo state: what's committed, what's stashed + +As of this writing, `HEAD` (`5c8d794`) has the keep-worthy pieces from +the abandoned attack-presence-bitboard work already committed on their +own: the `bitboard.c` passed-pawn bit-clear fix, the `search.c`/ +`searchsup.c` LMR-gate-to-caller refactor plus its matching `split.c` +fix, and *only* the `CountBits`/`CoorFromBitBoardRank8ToRank1`/ +`CoorFromBitBoardRank1ToRank8` inlining block in `eval.c` (the +`_FastFirstBit`/`_FastLastBit` pair from the same block was PoC-only -- +no production call sites -- and was left out, since keeping it would +leave an unused-function warning once the PoC code it served is gone). + +Everything else from that work -- the `bbPawnAttacks`/etc. `POSITION` +fields, all the `eval.c` reader-migration and mobility-function +production code built on them, the `RunEval{Rook,Bishop,Queen,Knight}AB` +PoC harnesses and their `command.c` entries -- is **not on disk**. It's +sitting in `git stash@{0}` ("eval bitboard reader-migration work +(measured 17-41% slower) + PoC harnesses + reusable data.c ray tables + +command.c evalcycles"), deliberately left there rather than popped back, +since most of it isn't wanted. + +Two things were wanted out of that stash for this plan, and **have now +been pulled** (done, not just planned): + +- **`data.c`** (clean, additions-only diff): `g_RookRayToEdge`/ + `g_BishopRayToEdge`/`g_KnightAttacksBB` + their `Initialize*` functions + -- pulled whole-file via `git checkout stash@{0} -- data.c`, builds + clean. +- **`main.c`**'s 3-line addition calling those three `Initialize*` + functions from the startup sequence -- pulled the same way, alongside + `data.c`. +- **`chess.h`**'s `extern` declarations for the above (7 lines: the two + ray-to-edge tables + their delta/direction arrays, `g_KnightAttacksBB`, + and the three `Initialize*` prototypes) -- hand-copied rather than + checked out, since `chess.h`'s stashed diff also carries the unwanted + `bbPawnAttacks`/etc. `POSITION` fields and PoC function prototypes. Only + the 7 wanted lines were added, next to the existing `BBADJACENT_RANKS` + externs. +- `command.c`'s `evalcycles` command was **not** pulled yet -- still + sitting in the stash, still wanted eventually (section 5 needs the same + shape for `getattacksbench`/`kingdefectsbench`), just not needed until + that section starts. Extraction instructions unchanged from before: + `git diff stash@{0}^ stash@{0} -- command.c`, take only + `EvalCyclesCommand` and its command-table entry, leave + `evalrookab`/etc. behind. + +`eval.c` was correctly left alone -- its stashed diff includes the +inlining block already committed, so pulling it would conflict. Nothing +from section 3 onward has touched `eval.c`/`see.c` yet; when it does, +use the stashed `eval.c` only as *reference* for the ray-walk pattern +(already proven correct there -- `RunEvalRookAB` et al. verified 0 +mismatches), not as something to check out. + +Also present in the stash, independent of all of the above and not +needed for this plan: a small `uNumSplits`/`uNumSplitsTerminated` +split-statistics counter/reporting addition spanning `chess.h`, +`root.c`, and `script.c`. Harmless and separable, but tangential -- +leave it in the stash unless it's wanted on its own merits later. + +## 0. Scope and non-goals + +In scope: add incrementally-maintained per-color, per-piece-type location +bitboards to `POSITION`, and a bitboard-driven "who attacks square X" +primitive that both `GetAttacks` and `CountKingSafetyDefects` consume. + +Explicitly not in scope: changing `MOVE`'s `cFrom:8`/`cTo:8` encoding or +`COOR`'s `0x88` numbering. That would shrink `g_HistoryCounters`, +`g_iPSQT`, `g_ContinuationHistory`, and the countermove table +(`COUNTER_MOVE_TABLE_SIZE`) since they're all keyed directly off raw +`COOR`/`MOVE` bits sized to `0x88`'s wasted range -- a real win if it ever +happens, but a much bigger, separate project (touches `san.c`/`ics.c` +notation, `hash.c`'s packed move encoding, `book.c`'s format, `root.c`'s +PV printing). Ruled out for this pass; noted here only so it isn't +rediscovered and reconsidered mid-migration. + +Also out of scope for this pass: touching `Eval()`'s existing +(measured-slower) attack-presence bitboards -- that's a separate +decision, addressed in section 8, not bundled with this one. Keeping +these independent means a bad result here doesn't force a revert of the +Eval work and vice versa. + +## 1. New state: `bbPieces[2][8]` -- DONE + +Implemented as planned, with one correction found while implementing: +there's no existing `NUM_PIECE_TYPES` constant, so it's sized `[2][8]` +to exactly match `uNonPawnCount[2][8]`'s existing convention (indices +0/1 unused for this field, 2..6 are `PIECE_TYPE`-indexed +KNIGHT/BISHOP/ROOK/QUEEN/KING, KING's slot always zero by construction). +Added to `POSITION` (`chess.h`) right after `uNonPawnCount`. + +Pawns excluded (`pHash->bbPawnLocations[2]` already covers them). King +excluded (`cNonPawns[color][0]`, single square, a bitboard adds nothing) +-- enforced by only ever writing indices `KNIGHT..QUEEN` (i.e. `< KING`), +never `KING` itself. + +**Maintained incrementally in `move.c`**, at all 6 non-pawn +piece-movement functions (more than the original plan's 2 sites -- +`SlidePiece`/`LiftPiece`/`PlacePiece` each turned out to have a second, +`WithoutSigs` sibling used by `UnmakeMove`, not found until reading the +actual call graph): + +- `SlidePiece` / `SlidePieceWithoutSigs` (simple non-capture move, and + its unmake counterpart -- also what castling uses, twice per call, for + king and rook) -- clear from-bit, set to-bit. +- `LiftPiece` / `LiftPieceWithoutSigs` (piece leaves the board: capture, + or the pawn side of a promotion, or unmake-removing a + promoted/just-placed piece) -- clear the bit. Both already branch on + `IS_PAWN`/`!IS_KING` for other bookkeeping, so the new line drops + straight into the existing non-pawn branch, no new conditional needed. +- `PlacePiece` / `PlacePieceWithoutSigs` (piece appears on the board: + promotion result, or unmake-restoring a captured piece) -- set the bit. + Same existing-branch placement as above. + +Confirmed via the actual call sites (`move.c:811-828`, `:960-993`, +`:1249-1339`) that every move type -- normal, capture, both-side +castling, promotion (with or without capture), en passant, and every +undo -- routes through one of these 6 functions; nothing bypasses them +with a direct `rgSquare[].pPiece` write. + +O(1) extra work per move, next to array bookkeeping already happening +there. No rebuild-from-scratch anywhere. + +**From-scratch population**: `fen.c`'s piece-placement loop (the +non-king branch that already sets `cNonPawns[uColor][uIndex]`), one line +added. Zeroing is free -- `fen.c`'s `memset(p, 0, sizeof(POSITION))` +covers the new field automatically, no separate zeroing code needed. + +## 2. Correctness gate on the *maintenance* side -- DONE, verified clean + +Implemented in `board.c`'s existing `VerifyPositionConsistency` +(`board.c:129`), not new bespoke code, as planned: a local `bbPieces[2][8]` +accumulated in the same non-pawn piece-list walk that already builds +`uNonPawnCount[2][7]` (`|= COOR_TO_BB(c)` guarded by `!IS_KING(p)`, +right next to the existing `uNonPawnCount[u][PIECE_TYPE(p)]++`), +compared against `pos->bbPieces` in a loop next to the existing count +comparison (`KNIGHT` to `< KING`, matching `move.c`'s own range +convention), and one new `szExplainations[]` entry ("bbPieces bitboard +doesn't match piece list", reason index 21). + +**Verified clean**, not just added: `gmake DEBUG=1` build has zero +warnings, and `precommit_check.sh` (`gmake TEST=1` self-test + +`debug_smoke_test.sh`) passed with the assert live. Specifically checked +that `TEST=1`'s `TestMakeUnmakeMove` (`testmove.c:454`) exercises the +edge cases that would most likely expose a missed `move.c` update site -- +en passant, promotion-with-capture, and both-side castling, each +round-tripped through make+unmake with `VerifyPositionConsistency` +firing on every `Slide`/`Lift`/`Place` call in `DEBUG` builds -- and the +`bbPieces` check stayed silent throughout. Also confirmed the release +build (`GENETIC=1 PERF_COUNTERS=1 MP=1 SIXTYFOUR=1`) compiles clean and +runs a normal search correctly (the maintenance code has no `#ifdef +DEBUG` guard, matching section 6's "always on" toggle strategy). + +Nothing reads `bbPieces` yet (confirmed: it's write-only outside the +`DEBUG` consistency check), so this remains pure addition with zero +behavioral risk, exactly as planned. **Not yet committed** -- sitting on +disk, verified, ready to commit whenever section 1 is considered a good +checkpoint. + +## 3. New `_WhoAttacksSquareBB` primitive, consumed by two PoCs -- NOT STARTED + +Everything below this point is still just the plan -- no code written yet. + +Build one shared bitboard primitive rather than two independent +implementations, since `GetAttacks` and `CountKingSafetyDefects` are the +same query against different target squares: + +- Pawns: existing 2-square delta check, unchanged (already O(1), nothing + to improve). +- Knights/king: `g_KnightAttacksBB[cSquare] & bbPieces[side][KNIGHT]` + (and the equivalent king delta check) -- O(1), reusing + `g_KnightAttacksBB` already built and verified this session. +- Sliders (bishop/rook/queen): reuse `g_RookRayToEdge`/`g_BishopRayToEdge` + + `_FastFirstBit`/`_FastLastBit`, walking outward from the target + square along each ray to the nearest blocker, testing it against + `bbPieces[side][ROOK]`/`[BISHOP]`/`[QUEEN]` (queens checked on both ray + sets). Needs `bbOccupied` (both colors, all pieces) to find the + blocker -- construct as `bbPieces[WHITE][*] | bbPieces[BLACK][*] | + pHash->bbPawnLocations[*] | king bits`, now cheap (all pre-maintained) + rather than a `cNonPawns` walk. + +Two call-site wrappers, each a PoC alongside the real thing (same pattern +as this session's earlier `_EvalRookOccupancyBB` PoC work), gated so old +and new are both callable side by side: + +- **`_GetAttacksBB`** (`see.c`): calls the primitive against the move's + destination square, populates a `SEE_LIST` exactly like `GetAttacks` + does today. No pin-detection, no en-passant handling -- matching + `GetAttacks`'s exact (deliberately approximate) semantics. Not + introducing new behavior, just recomputing the same answer differently. +- **`_CountKingSafetyDefectsBB`** (`eval.c`): calls the primitive against + the king's square, feeding the same `CHECK_VECTOR`-derived defect-count + logic `CountKingSafetyDefects` already has (`uPiecesPointingAtKing` + bookkeeping included) -- only the "which enemy pieces bear on this + square" step changes, the counting/scoring logic downstream of it + doesn't. + +`CountKingSafetyDefects` doesn't build a `SEE_LIST` at all (it just +counts and classifies), so it isn't a second consumer of `_GetAttacksBB` +directly -- it's a second consumer of the lower-level per-piece-type +bitboard scan the two share. Structure the primitive so it can return +either "the raw attacker bitboard per piece type" (what +`CountKingSafetyDefects` wants, to test `CHECK_VECTOR`-equivalent +conditions itself) or "a populated `SEE_LIST`" (what `GetAttacks` wants), +rather than forcing one call shape on both. + +## 4. Correctness verification + +Confirmed before writing this plan: `SEE()` sorts/heaps the attacker list +immediately after `GetAttacks` returns (`see.c:872-878`, +`_BuildHeap`/`_SortList`), so a bitboard-based `GetAttacks` returning +attackers in a different order than the mailbox version is fine -- +correctness only requires the *set* of attackers to match, not the +sequence. + +1. **Fix `SeeListsAreEqual` to be order-independent first** + (`testsee.c:139`) -- sort both lists by `(cLoc, pPiece)` before the + field-by-field compare, or compare as multisets. Do this as its own + tiny commit; verify it still passes against the existing + Slow-vs-asm comparison (order shouldn't change there, so this change + should be provably a no-op in isolation before it's relied on for + anything new). +2. **Extend `TestGetAttacks`** (`testsee.c:154`) to add `_GetAttacksBB` + as a third comparison against the same 20,000 random-position x + every-square x both-colors sweep already in place + (`GenerateRandomLegalPosition`). This is the primary correctness + gate -- cheap to run (`gmake TEST=1`), already wired into the batch + self-test startup path. +3. **Add an equivalent random-position test for + `_CountKingSafetyDefectsBB`**, same 20,000-position generator, both + colors, comparing its returned defect count *and* the + `uPiecesPointingAtKing` side-effect against `CountKingSafetyDefects`. + No existing harness to extend here (unlike `GetAttacks`), so this is + new test code in the `TEST=1` build, following `TestGetAttacks`'s + shape. +4. **`precommit_check.sh`** as always, for the crash/assert layer. +5. **SEE-value diffing at the position level**: since `SEE()` returns a + single integer per move (not a board eval), the equivalent of the + Eval work's "150-position score-identity diff" is a diagnostic + command (`seescores`, analogous to the batch `eval` dumps used + earlier) that computes `SEE()` for every legal capture in a batch of + ECM/random positions, run once per `GetAttacksBB` toggle state, + diffed. Catches any behavioral drift `TestGetAttacks`'s raw-list + comparison might miss once results feed into `_MinLegalPiece`'s + exchange simulation. Do the same for `CountKingSafetyDefects`: a + `kingdefects` diagnostic command dumping the defect count for both + kings across the same position batch, diffed the same way -- this one + matters more than it sounds, since the count feeds directly into + `Eval()`'s king-safety score term (`eval.c:2549-2550`), not just + pruning gates. +6. **Full-suite behavioral check is mandatory here, not optional** -- + this is the one place this migration is *riskier* than the Eval + constant work: `GetAttacks` feeds move ordering and pruning decisions + (`generate.c`'s 5 call sites, `searchsup.c:365`), and + `CountKingSafetyDefects` feeds pruning/extension decisions directly + (`search.c:1252`, `searchsup.c:484,902,905`) *in addition to* an + Eval() score term -- so even value-for-value-identical results can + shift which move gets tried first or which lines get pruned/extended, + changing node counts and occasionally search results at the margins. + Run all three curated suites (`ecm_ringers`, `ecm_confident_quick`, + `ecm_hard_quick`) at `sd10` against `head_reference/`, and don't treat + a clean `TestGetAttacks`/`_CountKingSafetyDefectsBB` unit-level pass + as sufficient sign-off by itself -- `CountKingSafetyDefects`'s direct + search-code call sites make this the higher-risk of the two changes, + despite being the simpler one to implement. +7. **`match_play.py` gate** (`LOWER95 >= 0.5`) before calling this done + -- same reasoning: this is closer to a search-behavior change than a + pure eval-magnitude change, so the existing eval-tuning gate criteria + apply. Run once with both migrations landed together (they share the + same underlying primitive, so testing them jointly is representative + of how they'll actually ship) plus, if the combined match shows a + problem, one more isolating each toggle independently to attribute it. + +## 5. Microbenchmarking + +The Eval cycle measurement earlier this session is the cautionary tale: +an isolated PoC can look plausible and still lose once integrated, +because integration costs (dual maintenance, extra indirection) aren't +visible in isolation. Two tiers, both required before wiring in: + +1. **Isolated cycles/call**, same `SystemReadTimeStampCounter` pattern + as `evalcycles`/`RunEvalRookAB`: a `getattacksbench [iterations]` + command looping old vs. new `GetAttacks` on the *current* + position/square, and a `kingdefectsbench [iterations]` command doing + the same for `CountKingSafetyDefects`, interleaved (old/new/old/new) + to cancel shared-box noise, run across a battery of positions spanning + piece density -- opening (~30 pieces), middlegame (~20), endgame + (~8) -- since the algorithmic win should scale *with* piece count, and + a flat or inverted result across that spectrum is a red flag before + proceeding further, exactly like the rook/bishop Eval win that didn't + hold up once integrated. +2. **Whole-engine cycles-per-node / NPS**, not just the isolated call: + `sd`-fixed-depth comparison against `head_reference` on the three + curated suites, using the engine's own self-reported `Searched for N + seconds, M nodes` (not `ps` sampling -- noisy on this shared box per + earlier sessions). This is the check that would have caught the Eval + regression earlier if it had been run before the reader-migration + work proceeded -- don't skip straight from isolated-cycles-looks-good + to production wiring again. Given `CountKingSafetyDefects`'s search-code + call sites, this whole-engine number is where its win (or lack of one) + will actually show up -- its isolated per-call cycle count matters + less than `GetAttacks`'s does, precisely because it's called from more + places than just move ordering. + +## 6. Dual-support / toggle strategy + +Same `#define` pattern already established for the Eval occupancy work +(`ROOK_OCCUPANCY_EVAL` et al.): `GETATTACKS_BITBOARD`, flipping which +implementation `chess.h`'s `GetAttacks` macro/prototype resolves to +(alongside the existing `CROUTINES` old/new(asm) switch -- this becomes a +three-way choice: `SlowGetAttacks` (C mailbox), asm `GetAttacks` (x86/x64 +mailbox), `_GetAttacksBB` (new)). A second, independent toggle, +`KINGSAFETY_BITBOARD`, does the same for `CountKingSafetyDefects` vs. +`_CountKingSafetyDefectsBB` -- independent so each can be measured, +gated, and (if needed) rolled back on its own, even though they share the +underlying `_WhoAttacksSquareBB` primitive. + +`bbPieces` maintenance itself is **always on** regardless of either +toggle -- it's cheap enough that gating it adds complexity for no +benefit, and other future work (see section 8) can build on it once +trusted. + +## 7. Retirement criteria for the old mailbox implementations + +Only delete `SlowGetAttacks`/asm `GetAttacks` after **all** of: + +- Extended `TestGetAttacks` clean across the 20,000-position sweep. +- Isolated cycles/call shows a consistent win across the piece-density + spectrum (not just one favorable position). +- Whole-engine `sd10` on all three curated suites shows no solve-count + regression vs. `head_reference`. +- `match_play.py` gate clears `LOWER95 >= 0.5`. +- `head_reference/` rebuilt as the new baseline once landed. + +Only delete the old `CountKingSafetyDefects` mailbox body after the same +five criteria, evaluated against *its* test/bench additions -- do not +retire it just because `GetAttacks`'s migration cleared its own bar; they +share a primitive but are independently gated per section 6, and +`CountKingSafetyDefects`'s wider call-site footprint (search-code pruning +gates, not just move ordering) makes it the one more likely to surface a +problem only visible in full search behavior, not in the unit-level +correctness test. + +One easy win to check first, independent of all this: confirm whether +`x86.asm`'s `GetAttacks` is even compiled into the `SIXTYFOUR=1` release +profile at all (`GNUmakefile`) -- if it's already dead on this 64-bit-only +box, that's a zero-risk deletion to do up front, separate from the +migration. + +## 8. What this means for the existing (measured-slower) Eval bitboards + +Not bundling a decision here, but flagging it: once `bbPieces` exists and +is trusted, it's a cheaper substrate than what the current +`bbPawnAttacks`/`bbMinorAttacks`/`bbRookAttacks`/`bbQueenAttacks`/ +`bbKingAttacks` work does today (rebuild-from-scratch per `Eval()` call). +Worth revisiting *after* this migration lands -- either reimplementing +the attack-presence bitboards on top of `bbPieces` + ray tables cheaply, +or reverting them if `bbPieces` alone doesn't end up mattering for Eval. +Separate decision, separate correctness/benchmark cycle, not this one. diff --git a/src/chess.h b/src/chess.h index 5e1d4a5..1f874b9 100755 --- a/src/chess.h +++ b/src/chess.h @@ -647,6 +647,17 @@ typedef struct _POSITION // 0 and 1 are the sum, // 2..6 are per PIECE_TYPE + // Per-color, per-piece-type location bitboards -- "where are my + // knights/bishops/rooks/queens" -- indexed by PIECE_TYPE exactly + // like uNonPawnCount above (slots 0/1/PAWN/KING unused, same + // convention). Maintained incrementally in move.c at every site + // that already updates cNonPawns[]/uNonPawnCount[] (see + // board_representation/MIGRATION.md), not rebuilt -- O(1) per + // move. Pawns use pHash->bbPawnLocations[2] (pawn-hash-keyed, + // already established) instead; king is a single square + // (cNonPawns[color][0]), a bitboard adds nothing. + BITBOARD bbPieces[2][8]; + ULONG uWhiteSqBishopCount[2]; // num bishops on white squares SCORE iMaterialBalance[2]; // material balance @@ -1318,7 +1329,16 @@ _assert(CHAR *szFile, ULONG uLine); #define TO64(x) ((x) & 0x7) + ((0x7 - ((x)>>4)) << 3) #define COOR_TO_BIT_NUMBER(c) (((((c) & 0x70) >> 1) | ((c) & 0x7))) #define SLOWCOOR_TO_BB(c) (1ULL << COOR_TO_BIT_NUMBER(c)) -#define COOR_TO_BB(c) (BBSQUARE[COOR_TO_BIT_NUMBER(c)]) +// Was BBSQUARE[COOR_TO_BIT_NUMBER(c)] (an L1 load off a 64-entry table) +// -- measured (testbitboard.c's TestBitboards, fixed to use a volatile +// sink so the comparison isn't dead-code-eliminated) consistently ~5-7% +// slower than the pure-ALU shift on this hardware, so switched to match +// SLOWCOOR_TO_BB's expression. "SLOW" in that macro's name reflects a +// stale assumption (variable-count shifts being slow) that doesn't hold +// on modern silicon; BBSQUARE itself stays -- still used directly (not +// via this macro) where callers already have a bit index in hand and +// indexing it avoids recomputing COOR_TO_BIT_NUMBER redundantly. +#define COOR_TO_BB(c) (1ULL << COOR_TO_BIT_NUMBER(c)) #define SLOW_BIT_NUMBER_TO_COOR(b) ((((b) / 8) << 4) + ((b) & 7)) #define BIT_NUMBER_TO_COOR(b) ((((b) & 0xF8) << 1) | ((b) & 7)) @@ -2002,6 +2022,18 @@ extern BITBOARD BBPRECEEDING_RANKS[8][2]; extern BITBOARD BBADJACENT_FILES[8]; extern BITBOARD BBADJACENT_RANKS[9]; +// Ray-to-edge / knight-attack occupancy tables (data.c) -- built once +// at startup, consumed by ray-walk mobility code and (per +// board_representation/MIGRATION.md) the planned bbPieces-backed +// GetAttacks/CountKingSafetyDefects primitive. +extern BITBOARD g_RookRayToEdge[4][128]; +extern const int g_RookRayDeltas[4]; +extern const FLAG g_RookRayPositiveDir[4]; +extern BITBOARD g_BishopRayToEdge[4][128]; +extern const int g_BishopRayDeltas[4]; +extern const FLAG g_BishopRayPositiveDir[4]; +extern BITBOARD g_KnightAttacksBB[128]; + void InitializeWhiteSquaresTable(void); @@ -2014,6 +2046,15 @@ InitializeSwapTable(void); void InitializeDistanceTable(void); +void +InitializeRookRayTables(void); + +void +InitializeBishopRayTables(void); + +void +InitializeKnightAttackTables(void); + #ifdef DEBUG ULONG CheckVectorWithIndex(int i, ULONG uColor); #define CHECK_VECTOR_WITH_INDEX(i, color) \ @@ -563,3 +563,160 @@ InitializeDistanceTable(void) } #endif } + +// +// Per-square, per-direction "ray to board edge" bitboards for the +// rook, indexed [direction][c] with direction matching +// g_RookRayDeltas below (N, S, E, W). Only entries for real board +// squares (IS_ON_BOARD(c)) are ever populated/queried; off-board +// indices are left zeroed and unused. Built once at startup by +// InitializeRookRayTables() -- part of eval.c's occupancy-bitboard +// PoC (_EvalRookOccupancyBB et al.), turning a per-call +// walk-to-the-edge loop into an O(1) table lookup. +// +BITBOARD g_RookRayToEdge[4][128]; +const int g_RookRayDeltas[4] = { 16, -16, 1, -1 }; // N, S, E, W (0x88) +const FLAG g_RookRayPositiveDir[4] = { TRUE, FALSE, TRUE, FALSE }; + +void +InitializeRookRayTables(void) +/** + +Routine description: + + One-time startup init for g_RookRayToEdge -- see its comment. + +Parameters: + + void + +Return value: + + void + +**/ +{ + ULONG uRank, uFile, uDir; + COOR c, cSquare; + + memset(g_RookRayToEdge, 0, sizeof(g_RookRayToEdge)); + for (uRank = 0; uRank < 8; uRank++) + { + for (uFile = 0; uFile < 8; uFile++) + { + c = (uRank << 4) | uFile; + for (uDir = 0; uDir < 4; uDir++) + { + for (cSquare = c + g_RookRayDeltas[uDir]; + IS_ON_BOARD(cSquare); + cSquare += g_RookRayDeltas[uDir]) + { + g_RookRayToEdge[uDir][c] |= COOR_TO_BB(cSquare); + } + } + } + } +} + +// +// Same idea as g_RookRayToEdge, for the bishop's 4 diagonal directions. +// +BITBOARD g_BishopRayToEdge[4][128]; +const int g_BishopRayDeltas[4] = { 17, -17, 15, -15 }; // NE, SW, NW, SE (0x88) +const FLAG g_BishopRayPositiveDir[4] = { TRUE, FALSE, TRUE, FALSE }; + +void +InitializeBishopRayTables(void) +/** + +Routine description: + + One-time startup init for g_BishopRayToEdge -- see its comment. + +Parameters: + + void + +Return value: + + void + +**/ +{ + ULONG uRank, uFile, uDir; + COOR c, cSquare; + + memset(g_BishopRayToEdge, 0, sizeof(g_BishopRayToEdge)); + for (uRank = 0; uRank < 8; uRank++) + { + for (uFile = 0; uFile < 8; uFile++) + { + c = (uRank << 4) | uFile; + for (uDir = 0; uDir < 4; uDir++) + { + for (cSquare = c + g_BishopRayDeltas[uDir]; + IS_ON_BOARD(cSquare); + cSquare += g_BishopRayDeltas[uDir]) + { + g_BishopRayToEdge[uDir][c] |= COOR_TO_BB(cSquare); + } + } + } + } +} + +// A combined 8-ray queen table (rook's 4 directions + bishop's 4, +// concatenated) was tried here and measured SLOWER than +// _EvalQueenOccupancyBB's two-pass version reusing g_RookRayToEdge/ +// g_BishopRayToEdge directly -- see that function's comment for why +// (probable lost constant-folding on the orthogonal-ray flag). Removed +// rather than left around unused. + +// +// Per-square "all squares a knight on c can hop to" bitboard. Unlike +// the rook/bishop ray tables, a knight has no blocking to account for +// -- there's nothing "in between" a knight and its landing square -- +// so this is the complete, final answer for a given square, not a +// ray-to-edge that still needs an occupancy AND to find blockers. +// Built once at startup by InitializeKnightAttackTables(). +// +BITBOARD g_KnightAttacksBB[128]; + +void +InitializeKnightAttackTables(void) +/** + +Routine description: + + One-time startup init for g_KnightAttacksBB -- see its comment. + +Parameters: + + void + +Return value: + + void + +**/ +{ + ULONG uRank, uFile, uDir; + COOR c, cSquare; + + memset(g_KnightAttacksBB, 0, sizeof(g_KnightAttacksBB)); + for (uRank = 0; uRank < 8; uRank++) + { + for (uFile = 0; uFile < 8; uFile++) + { + c = (uRank << 4) | uFile; + for (uDir = 0; g_iNDeltas[uDir] != 0; uDir++) + { + cSquare = c + g_iNDeltas[uDir]; + if (IS_ON_BOARD(cSquare)) + { + g_KnightAttacksBB[c] |= COOR_TO_BB(cSquare); + } + } + } + } +} @@ -329,6 +329,7 @@ Return value: uIndex = uNumNonPawns[uColor] + 1; pos->cNonPawns[uColor][uIndex] = cSquare; uNumNonPawns[uColor]++; + pos->bbPieces[uColor][PIECE_TYPE(p)] |= COOR_TO_BB(cSquare); } pos->rgSquare[cSquare].pPiece = p; pos->rgSquare[cSquare].uIndex = uIndex; @@ -461,6 +461,9 @@ Return value: InitializeVectorDeltaTable(); InitializeSwapTable(); InitializeDistanceTable(); + InitializeRookRayTables(); + InitializeBishopRayTables(); + InitializeKnightAttackTables(); InitializeOpeningBook(); InitializeDynamicMoveOrdering(); InitLMRTable(); @@ -62,6 +62,8 @@ Return value: ASSERT(IS_VALID_COLOR(c)); ASSERT(pos->cNonPawns[c][uIndex] == cFrom); pos->cNonPawns[c][uIndex] = cTo; + pos->bbPieces[c][PIECE_TYPE(p)] &= ~COOR_TO_BB(cFrom); + pos->bbPieces[c][PIECE_TYPE(p)] |= COOR_TO_BB(cTo); pos->u64NonPawnSig ^= g_u64SigSeeds[cFrom][PIECE_TYPE(p)][c]; pos->u64NonPawnSig ^= g_u64SigSeeds[cTo][PIECE_TYPE(p)][c]; #ifdef DEBUG @@ -171,6 +173,8 @@ Return value: ASSERT(IS_VALID_COLOR(c)); ASSERT(pos->cNonPawns[c][uIndex] == cFrom); pos->cNonPawns[c][uIndex] = cTo; + pos->bbPieces[c][PIECE_TYPE(p)] &= ~COOR_TO_BB(cFrom); + pos->bbPieces[c][PIECE_TYPE(p)] |= COOR_TO_BB(cTo); pos->rgSquare[cTo].pPiece = p; pos->rgSquare[cTo].uIndex = uIndex; #ifdef DEBUG @@ -345,11 +349,12 @@ Return value: pos->u64NonPawnSig ^= g_u64SigSeeds[cSquare][u][color]; pos->uNonPawnCount[color][u]--; ASSERT(pos->uNonPawnCount[color][u] <= 9); + pos->bbPieces[color][u] &= ~COOR_TO_BB(cSquare); pos->uWhiteSqBishopCount[color] -= (IS_BISHOP(pLifted) & IS_SQUARE_WHITE(cSquare)); ASSERT(pos->uWhiteSqBishopCount[color] <= 9); } - + #ifdef DEBUG VerifyPositionConsistency(pos, FALSE); #endif @@ -477,11 +482,12 @@ Return value: ASSERT((u >= KNIGHT) && (u < KING)); pos->uNonPawnCount[color][u]--; ASSERT(pos->uNonPawnCount[color][u] <= 9); - pos->uWhiteSqBishopCount[color] -= (IS_BISHOP(pLifted) & + pos->bbPieces[color][u] &= ~COOR_TO_BB(cSquare); + pos->uWhiteSqBishopCount[color] -= (IS_BISHOP(pLifted) & IS_SQUARE_WHITE(cSquare)); ASSERT(pos->uWhiteSqBishopCount[color] <= 9); } - + return(pLifted); } @@ -556,7 +562,8 @@ Return value: pos->u64NonPawnSig ^= g_u64SigSeeds[cSquare][u][color]; pos->uNonPawnCount[color][u]++; ASSERT(pos->uNonPawnCount[color][u] <= 10); - + pos->bbPieces[color][u] |= COOR_TO_BB(cSquare); + pos->uWhiteSqBishopCount[color] += (IS_BISHOP(pPiece) & IS_SQUARE_WHITE(cSquare)); ASSERT(pos->uWhiteSqBishopCount[color] <= 10); @@ -564,17 +571,17 @@ Return value: // // Place the piece on the board - // + // pos->rgSquare[cSquare].pPiece = pPiece; pos->rgSquare[cSquare].uIndex = uIndex; - + #ifdef DEBUG VerifyPositionConsistency(pos, FALSE); #endif } -void +void PlacePieceWithoutSigs(POSITION *pos, COOR cSquare, PIECE pPiece) /** @@ -645,7 +652,8 @@ Return value: ASSERT((u >= KNIGHT) && (u < KING)); pos->uNonPawnCount[color][u]++; ASSERT(pos->uNonPawnCount[color][u] <= 10); - + pos->bbPieces[color][u] |= COOR_TO_BB(cSquare); + pos->uWhiteSqBishopCount[color] += (IS_BISHOP(pPiece) & IS_SQUARE_WHITE(cSquare)); ASSERT(pos->uWhiteSqBishopCount[color] <= 10); diff --git a/src/testbitboard.c b/src/testbitboard.c index 7d2bfeb..c91f87c 100644 --- a/src/testbitboard.c +++ b/src/testbitboard.c @@ -42,6 +42,22 @@ Return value: COOR c; ULONG b; BITBOARD bb; + // volatile, separate from bb (which is reused below for unrelated + // correctness checks and gets passed by address -- making it + // volatile there breaks those calls): without a volatile sink, the + // SLOWCOOR_TO_BB/COOR_TO_BB benchmark loops just below compute a + // value and never use it again, so the optimizer proves they have + // no effect and deletes them entirely -- this used to silently + // report "0 cycles/op" for both, an obviously impossible number + // that was never actually measuring anything (same class of bug + // documented in eval.c's RunEvalRookAB comment: "the first time + // this was written it produced 0.000s / inf calls/sec"). Other + // loops below (CountBits/LastBit/FirstBit etc.) happened to + // survive because those are real out-of-line/opaque calls the + // optimizer can't prove are side-effect-free; the COOR_TO_BB + // macros expand to plain visible expressions with nothing + // stopping them from being optimized away. + volatile BITBOARD bbSink; BITBOARD bbSpeed[1000]; ULONG u, v, w, z; UINT64 u64; @@ -74,20 +90,27 @@ Return value: for (u = 0; u < 1000000; u++) { b = u % 64; - bb = SLOWCOOR_TO_BB(b); + bbSink = SLOWCOOR_TO_BB(b); } - printf(" SLOWCOOR_TO_BB: %" COMPILER_LONGLONG_UNSIGNED_FORMAT + printf(" SLOWCOOR_TO_BB: %" COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/op\n", (SystemReadTimeStampCounter() - u64) / 1000000); u64 = SystemReadTimeStampCounter(); for (u = 0; u < 1000000; u++) { b = u % 64; - bb = COOR_TO_BB(b); + bbSink = COOR_TO_BB(b); } - printf(" COOR_TO_BB: %" COMPILER_LONGLONG_UNSIGNED_FORMAT + printf(" COOR_TO_BB: %" COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/op\n", (SystemReadTimeStampCounter() - u64) / 1000000); + // bbSink's individual writes are never dead-code-eliminated + // (that's what volatile guarantees) regardless of whether anything + // reads it afterward, but nothing did until this line -- report it + // so the compiler doesn't flag it as unused, same pattern the + // evalcycles command uses for its own timing-loop sink. + printf(" (bbSink final value, just to use it: %#llx)\n", + (unsigned long long)bbSink); u64 = SystemReadTimeStampCounter(); for (v = 1; v < 1000; v++) |