Add bitboard-backed GetAttacks (section 2/3), verified faster than asm

Board-representation migration, sections 2-3 (GetAttacks half):

- board.c: VerifyPositionConsistency's bbPieces consistency check
  (migration section 2), verified clean via gmake TEST=1 with the
  assert live.
- POSITION.bbPawns[2]: new incrementally-maintained per-color pawn
  location bitboard (chess.h), maintained at the same 6 move.c sites
  as bbPieces, populated from scratch in fen.c. Distinct from the
  pawn-hash-keyed bbPawnLocations; this one needs no
  SEARCHER_THREAD_CONTEXT, so it's reachable from GetAttacks's actual
  call sites (which only ever have a POSITION*).
- data.c/chess.h/main.c: g_RookRayAll/g_BishopRayAll (all 4 per-square
  ray directions pre-ORed) and g_PawnAttackOriginBB[2][128] startup
  tables, plus FastFirstBit/FastLastBit (static inline bsf/bsr
  wrappers, chess.h) -- supporting tables/helpers for the primitive
  below.
- see.c: _WhoAttacksSquareBB (bitboard "who attacks square X" query)
  and _GetAttacksBB (SEE_LIST-populating PoC wrapping it), side by
  side with the existing SlowGetAttacks/asm GetAttacks -- not wired
  into the GetAttacks macro yet (section 6), pure addition.
- testsee.c: SeeListsAreEqual made order-independent (SEE() sorts the
  list right after GetAttacks returns, so order was never semantically
  significant); TestGetAttacks extended to run _GetAttacksBB as a
  third comparison across the existing 20,000-random-position sweep;
  added an interleaved asm/Slow/BB cycles-per-call benchmark across
  opening/middlegame/endgame positions.
- testsup.c: fixed GenerateRandomLegalPosition (used by the sweep
  above) to maintain bbPieces/bbPawns at its two hand-placement sites
  -- a latent gap since section 1 that made its own
  VerifyPositionConsistency legality gate almost always reject
  generated positions, causing large, variable retry-loop slowdowns.

Verified: 20,000-position x every-square x both-colors correctness
sweep passes (gmake TEST=1), precommit_check.sh clean (self-test +
DEBUG smoke test). Benchmark: _GetAttacksBB is ~0.53-0.55x asm
GetAttacks's cycles/call (opening/middlegame) and ~0.89x (endgame) --
faster, not just equivalent, primarily from replacing bbOccupied's
up-to-16-iteration pawn loop with two bbPawns ORs, plus a
g_PawnAttackOriginBB table lookup replacing per-call pawn-delta
arithmetic and per-direction/per-side-group early-outs in the slider
walk. See board_representation/MIGRATION.md section 3 for the full
writeup, including a reverted approach that measured slower and why,
and the CountKingSafetyDefects half's re-scoped (not yet implemented)
design.

Also confirmed (not caused by this work, not fixed here): a
pre-existing non-deterministic MP-race assertion in util.c:1093's PV
printing, reproduced independently on a clean HEAD checkout.

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

1 files changed, 176 insertions, 43 deletions

diff --git a/src/board_representation/MIGRATION.md b/src/board_representation/MIGRATION.md
index 226e37e..f13aa9b 100644
--- a/src/board_representation/MIGRATION.md
+++ b/src/board_representation/MIGRATION.md
@@ -1,8 +1,13 @@
 # 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.
+**Status: sections 1-2 (bbPieces) and section 3's `GetAttacks` half
+(bbPieces/bbPawns-backed `_WhoAttacksSquareBB`/`_GetAttacksBB`, not yet
+wired into the `GetAttacks` macro) implemented and verified, ready to
+commit. `CountKingSafetyDefects`'s half of section 3 deliberately not
+started -- see its own status note below for why it needs a different
+design, not just a second consumer of the same primitive. Sections 4
+(partially done, folded into section 3's own testing)-8 otherwise 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`,
@@ -201,52 +206,180 @@ 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
+## 3. New `_WhoAttacksSquareBB` primitive -- `GetAttacks` half DONE, `CountKingSafetyDefects` half not started
 
-Everything below this point is still just the plan -- no code written yet.
+### `GetAttacks` half -- DONE, verified correct, verified faster than asm
 
-Build one shared bitboard primitive rather than two independent
-implementations, since `GetAttacks` and `CountKingSafetyDefects` are the
-same query against different target squares:
+Implemented in `see.c`: `_WhoAttacksSquareBB(pos, cSquare, uSide,
+bbOccupied)` returns a bitboard of every uSide knight/bishop/rook/
+queen/king attacking `cSquare` (pawns handled separately, see below),
+and `_GetAttacksBB` wraps it into a `SEE_LIST`-populating PoC with the
+same signature/semantics as `SlowGetAttacks`/`GetAttacks`. Not yet
+wired into the `GetAttacks` macro (section 6's toggle) -- still a
+side-by-side PoC, called only from the test/bench harness described
+below.
 
-- 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.
+Diverged from the original plan in a few ways, all discovered by
+measuring rather than guessing:
 
-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:
+- **`bbOccupied` construction dropped the `pHash->bbPawnLocations`
+  idea.** That field lives behind `PawnHashLookup(SEARCHER_THREAD_CONTEXT
+  *)`, but `GetAttacks`'s real call sites (`generate.c` x5, `see.c`,
+  `searchsup.c`) only ever have a `POSITION *`, matching `_GetAttacksBB`'s
+  signature -- threading a `ctx` through everywhere just for this
+  wasn't worth it. Added `POSITION.bbPawns[2]` instead: plain,
+  incrementally-maintained state (identical pattern to `bbPieces`,
+  same 6 `move.c` sites plus `fen.c`'s from-scratch population),
+  independent of the pawn hash. This turned out to be the single
+  biggest win in the whole section -- see benchmarks below.
+- **A precomputed `g_PawnAttackOriginBB[2][128]` table** (data.c,
+  `InitializePawnAttackOriginTable`, called from `main.c`'s startup
+  sequence) replaced the original plan's "existing 2-square delta
+  check, unchanged" for pawns. That plan text assumed the delta check
+  was already optimal since it's O(1) either way -- true
+  asymptotically, but the *fixed* per-call instruction count still
+  mattered: `g_PawnAttackOriginBB[uSide][cSquare] & pos->bbPawns[uSide]`
+  is one table lookup + one AND, entirely in bit-space (no
+  `cSquare + delta` arithmetic, no `IS_ON_BOARD` branch, no mailbox
+  load), vs. the original's add/mask/load/compare done twice. Measured
+  a further ~2-4% win from this on top of the `bbPawns` change, small
+  but real and consistent across all three density buckets tested.
+- **Per-direction and per-side-group early-outs**, not just "does
+  uSide have any rook/queen at all": `bbRookSliders & g_RookRayAll[
+  cSquare]` (a new startup-built table, all 4 `g_RookRayToEdge`
+  directions pre-ORed per square) gates entry to the direction loop at
+  all; inside it, each direction is skipped via `bbRay & bbRookSliders`
+  before touching `bbOccupied` or calling `FastFirstBit`/`FastLastBit`
+  (same idea as bishop). This is the bitboard equivalent of what
+  `CHECK_VECTOR` does per-piece in the mailbox version.
+- **`FastFirstBit`/`FastLastBit`**: `static inline` compiler-builtin
+  (`__builtin_ctzll`/`__builtin_clzll`) wrappers, moved to `chess.h`
+  (not `bitboard.c` -- a non-`static` C99 `inline` split across a .c/.h
+  pair is a link-time trap with no out-of-line instantiation anywhere;
+  caught this by testing the link, not by inspection). Same bsf/bsr
+  instruction the asm `FirstBit`/`LastBit` already use (confirmed by
+  reading the compiled asm and `x64.asm`'s `FirstBit` directly) --
+  the entire benefit is skipping `CDECL` call/return overhead by
+  inlining, not a smarter bit-trick.
+- **Blocker isolation stays in bit-space**: the slider loop isolates
+  the nearest blocker as a bitboard bit directly (`bb & -bb` for the
+  positive-direction/lowest-bit case, no `FastFirstBit` call needed at
+  all; `1ULL << (FastLastBit(bb)-1)` for the negative/highest-bit
+  case) and tests/ORs it directly against other bitboards, instead of
+  round-tripping through `BIT_NUMBER_TO_COOR`/`COOR_TO_BB` to do the
+  same test. `COOR_TO_BB`/`BIT_NUMBER_TO_COOR` are themselves cheap
+  (~1 cycle, no memory access -- confirmed via `testbitboard.c`'s
+  existing benchmark), so this wasn't about macro cost, just removing
+  otherwise-pointless conversions between two representations that
+  never needed to leave bit-space in the first place.
+- **One deliberately-reverted attempt, kept as a comment**: replacing
+  the 4-direction "check ray, skip if empty" loop with code that
+  derived the *specific* needed direction(s) directly from the aligned
+  slider bits (via `FastFirstBit` + rank/file-nibble comparison, no
+  table lookup) measured *slower* (~1.07-1.09x asm vs. ~0.96-1.00x for
+  the simple loop) -- the bit-scan-to-avoid-a-cheap-branch traded a
+  cheap AND+continue for a costlier extraction+branch. Reverted; the
+  comment in `see.c` explains why, so it isn't rediscovered and
+  retried the same way.
 
-- **`_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.
+**Benchmark** (new `TestGetAttacks` addition in `testsee.c`, interleaved
+`GetAttacks`(asm)/`SlowGetAttacks`/`_GetAttacksBB`, 200k calls each
+across opening/middlegame/endgame positions, `SystemReadTimeStampCounter`-based,
+same methodology as `testbitboard.c`'s existing benchmark):
 
-`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.
+| stage | vs. asm `GetAttacks`, final |
+|---|---|
+| opening | **0.53x** (i.e. ~1.9x faster) |
+| middlegame | **0.55x** |
+| endgame | **0.89x** |
+
+The `bbPawns`/`_BuildOccupiedBB` change alone (before the pawn-origin
+table) accounted for most of the opening/middlegame jump -- from
+~0.96-1.00x to ~0.55-0.57x -- since it replaced an up-to-16-iteration
+loop over `cPawns[2][8]` with two ORs, and opening/middlegame positions
+are exactly where that loop was longest. Endgame barely moved (fewer
+pawns = the old loop was already cheap there), which is the expected
+shape for that change and a useful cross-check that the win is coming
+from where the theory says it should.
+
+**Correctness**: `SeeListsAreEqual` (testsee.c) made order-independent
+first (sorts a scratch copy of each list by `(cLoc, pPiece)` before
+comparing -- `SEE()` sorts/heaps the list immediately after `GetAttacks`
+returns, so order was never semantically significant, just untested as
+such before). `TestGetAttacks` extended to run `_GetAttacksBB` as a
+third comparison against the same 20,000-random-position x every-square
+x both-colors sweep already exercising `SlowGetAttacks`/asm `GetAttacks`
+-- clean, `gmake TEST=1`. This is section 4's items 1-2, done here
+rather than deferred, since it was the only way to get real confidence
+in the optimization work above rather than trusting cycle counts on a
+possibly-wrong implementation.
+
+**Two real bugs found and fixed while getting the correctness sweep to
+actually run (not just to pass)**, both pre-existing, both unrelated to
+`GetAttacks` itself:
+
+1. **`GenerateRandomLegalPosition` (testsup.c)** -- used by
+   `TestGetAttacks`'s 20,000-position sweep -- builds positions via
+   direct field writes (`cNonPawns[]`, `cPawns[]`, etc.), bypassing
+   `PlacePiece`/`SlidePawn` entirely, so it never maintained `bbPieces`
+   (already true as of section 1, latent since that commit) or the new
+   `bbPawns`. Its own legality gate, `VerifyPositionConsistency(pos,
+   TRUE)`, checks `bbPieces`/`bbPawns` against the piece list and
+   silently returns `FALSE` (no panic -- `fContinue=TRUE`) for any
+   position with a non-pawn officer or any pawn on the board, so the
+   generator's outer retry loop would almost always discard the
+   position and retry -- not a deterministic hang, but a large,
+   variable slowdown (sometimes fast by luck, sometimes ran for
+   minutes) that looked exactly like a new infinite loop the first
+   time it was hit. Root-caused by instrumenting
+   `VerifyPositionConsistency`'s failure path directly (temporary
+   `fprintf` of `uReason`) rather than guessing -- confirmed reason 21
+   (`bbPieces` mismatch), not the new reason 22 (`bbPawns` mismatch).
+   Fixed by adding the same one-line-per-site `bbPieces`/`bbPawns`
+   maintenance `fen.c` already had, to `testsup.c`'s two hand-placement
+   sites.
+2. **A pre-existing, non-deterministic assertion** (`util.c:1093`,
+   inside `FinishPVTailFromHash`'s PV-tail formatting, part of the
+   original 2016 commit, untouched by this or any prior session's
+   diff) surfaced once during `precommit_check.sh`'s DEBUG smoke test
+   on an unlucky random ECM sample. Confirmed independently of this
+   session's work: replaying the exact saved failing sample
+   (`--cpus 4 --hash 64m`, matching `debug_smoke_test.sh`'s invocation)
+   against a stashed-clean `HEAD` reproduced the same crash on 1 of 3
+   runs, and passed clean on the other 2 -- an `MP=1` (4-thread) race
+   in PV printing, unrelated to `GetAttacks`/`bbPieces`/`bbPawns`.
+   **Not fixed here** -- flagged for a future session, since fixing it
+   is unrelated scope to this migration and risks masking whether a
+   real regression exists if conflated with this work's own testing.
+
+### `CountKingSafetyDefects` half -- NOT STARTED, needs a different design than planned
+
+While implementing the `GetAttacks` half, re-reading the actual
+`CountKingSafetyDefects` body (`eval.c:2325`) revealed the original
+plan's premise for this half is wrong: the plan assumed both functions
+do "a mailbox ray-walk... to answer 'does this piece attack this
+square'", making them two consumers of one shared blocked-attack
+primitive. In fact `CountKingSafetyDefects` does **no ray-walk and no
+blocker/occlusion check at all** -- it's a `CHECK_VECTOR_WITH_INDEX`
+table lookup testing whether each enemy piece's *type* geometrically
+aligns with one of three squares near the king (`cKing-1, cKing,
+cKing+1`), regardless of what's in between. It's a deliberately
+approximate proximity/alignment heuristic, not a true attack query.
+
+Feeding it `_WhoAttacksSquareBB`'s real, blocker-aware result would
+silently make it *more accurate* than today -- a behavior change (and
+one that would need eval re-tuning + re-gating), not a value-identical
+reimplementation, which breaks section 4's "identical behavior" testing
+premise for this half specifically. Decided direction (not yet
+implemented): two separate functions instead of one shared code path --
+`_WhoAttacksSquareBB` stays `GetAttacks`-only; a `_CountKingSafetyDefectsBB`
+would keep the existing unblocked `CHECK_VECTOR` logic bit-for-bit,
+just iterate `bbPieces[xside][*]` bits instead of walking `cNonPawns[
+xside][]` to get the same enemy-piece-square list -- same "share
+`bbPieces` as the substrate, not a literal ray-walk" relationship as
+`GetAttacks`, just without a shared primitive function. Not started;
+next session should implement this shape directly rather than
+revisiting the original one-primitive premise.
 
 ## 4. Correctness verification