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, 262 insertions, 1 deletions

diff --git a/src/see.c b/src/see.c
index 292cbf1..4b534bb 100755
--- a/src/see.c
+++ b/src/see.c
@@ -157,6 +157,267 @@ Return value:
     }
 }
 
+
+//
+// board_representation/MIGRATION.md section 3: bbPieces-backed
+// "who attacks square X" primitive, and a GetAttacks PoC built on
+// it. Not wired into the GetAttacks macro yet -- see MIGRATION.md
+// section 6 for the eventual toggle. Uses chess.h's FastFirstBit/
+// FastLastBit (static inline bsf/bsr wrappers) rather than the real
+// out-of-line FirstBit/LastBit -- worth avoiding call overhead in a
+// per-move-generated, per-node hot path like this one.
+//
+static BITBOARD
+_BuildOccupiedBB(IN POSITION *pos)
+/**
+
+Routine description:
+
+    Full-board occupancy (both colors, every piece including pawns
+    and kings), built from the incrementally-maintained bbPieces[2][8]
+    and bbPawns[2] fields plus the king mailbox array
+    (cNonPawns[.][0], a single square per side -- a bitboard for that
+    adds nothing). All O(1) ORs now that bbPawns exists; this used to
+    loop cPawns[2][8] (up to 16 iterations) to build the pawn portion,
+    which ran on every single call regardless of how few pawns were
+    actually relevant.
+
+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]));
+}
+
+static BITBOARD
+_WhoAttacksSquareBB(IN POSITION *pos,
+                     IN COOR cSquare,
+                     IN ULONG uSide,
+                     IN BITBOARD bbOccupied)
+/**
+
+Routine description:
+
+    Return a bitboard of every uSide knight/bishop/rook/queen/king
+    that attacks cSquare in the current position, blockers included.
+    Pawns are deliberately excluded -- see GetAttacksBB, which handles
+    them the same 2-square-delta way SlowGetAttacks always has (already
+    O(1), nothing to improve).
+
+    Knights and the king are pure O(1) table/delta lookups (no
+    blocking possible). Sliders walk outward from cSquare along each
+    of the 4 rook/4 bishop directions to the *nearest* blocker
+    (g_RookRayToEdge/g_BishopRayToEdge ANDed with bbOccupied, reduced
+    via FastFirstBit/FastLastBit), and test only that nearest
+    blocker for membership in uSide's rook/bishop/queen bitboard --
+    anything beyond the first blocker on a ray cannot be attacking
+    cSquare regardless of its type, so only one square per direction
+    is ever classified.
+
+    Each 4-direction ray-walk is skipped entirely (bbRookSliders/
+    bbBishopSliders both zero) when uSide has no piece that could
+    possibly be found by it -- cheap up front, and the case that
+    matters most: a benchmark comparing this function's original
+    unconditional version against the real (asm) GetAttacks showed a
+    consistent ~1.4x slowdown across opening/middlegame/endgame
+    positions, because the unconditional 8-ray walk pays a fixed cost
+    regardless of how few of uSide's pieces are actually sliders,
+    while the mailbox version's cost scales with uSide's live piece
+    count. This early-out targets exactly that mismatch -- see
+    board_representation/MIGRATION.md section 3 for the writeup.
+
+Parameters:
+
+    POSITION *pos,
+    COOR cSquare : target square
+    ULONG uSide : side whose attackers on cSquare we want
+    BITBOARD bbOccupied : full-board occupancy (see _BuildOccupiedBB)
+
+Return value:
+
+    BITBOARD
+
+**/
+{
+    BITBOARD bbAttackers;
+    BITBOARD bbRookSliders;
+    BITBOARD bbBishopSliders;
+    BITBOARD bbRay;
+    BITBOARD bbBlockers;
+    BITBOARD bbBlockerBit;
+    ULONG u;
+
+    bbAttackers = g_KnightAttacksBB[cSquare] & pos->bbPieces[uSide][KNIGHT];
+    if (DISTANCE(cSquare, pos->cNonPawns[uSide][0]) == 1)
+    {
+        bbAttackers |= COOR_TO_BB(pos->cNonPawns[uSide][0]);
+    }
+
+    // Measured slower: deriving the needed direction(s) directly from
+    // the aligned slider bits (via FastFirstBit + rank/file-nibble
+    // comparison) instead of the plain 4-direction loop below. The
+    // extra bit-scan and branching to *avoid* touching 2-3 empty
+    // directions cost more than just touching them via a cheap
+    // AND+continue -- reverted; keeping the note so this isn't
+    // rediscovered as "obviously better" and retried the same way.
+    //
+    // g_RookRayAll[cSquare] (all 4 directions' masks pre-ORed at
+    // startup) answers "is uSide's rook/queen bitboard aligned with
+    // cSquare in *any* rook direction at all" in one lookup+AND,
+    // before paying for even the first per-direction check -- pieces
+    // that aren't on any rook line from cSquare get rejected right
+    // here. For the direction(s) that remain possible, g_RookRayToEdge[
+    // u][cSquare] & bbRookSliders is the bitboard equivalent of what
+    // CHECK_VECTOR does per-piece in the mailbox version -- "does
+    // uSide have a rook/queen on *this* ray specifically."
+    bbRookSliders = pos->bbPieces[uSide][ROOK] | pos->bbPieces[uSide][QUEEN];
+    if (bbRookSliders & g_RookRayAll[cSquare])
+    {
+        for (u = 0; u < 4; u++)
+        {
+            bbRay = g_RookRayToEdge[u][cSquare];
+            if (!(bbRay & bbRookSliders))
+            {
+                continue;
+            }
+            bbBlockers = bbRay & bbOccupied;
+            // Isolate the nearest blocker as a bitboard bit directly,
+            // skipping the bit-index/COOR round trip entirely --
+            // bbBlockers, bbRookSliders and bbAttackers are all
+            // already bitboards, so there's nothing COOR-space adds
+            // here. Lowest-bit isolation (positive-direction rays)
+            // doesn't even need FastFirstBit's ctz -- bb & -bb is O(1)
+            // with no bit-scan instruction at all; the negative
+            // direction still needs FastLastBit (no O(1) "isolate
+            // highest bit" trick exists without counting leading
+            // zeros first).
+            bbBlockerBit = g_RookRayPositiveDir[u] ?
+                           (bbBlockers & (0ULL - bbBlockers)) :
+                           (1ULL << (FastLastBit(bbBlockers) - 1));
+            bbAttackers |= (bbRookSliders & bbBlockerBit);
+        }
+    }
+
+    bbBishopSliders = pos->bbPieces[uSide][BISHOP] | pos->bbPieces[uSide][QUEEN];
+    if (bbBishopSliders & g_BishopRayAll[cSquare])
+    {
+        for (u = 0; u < 4; u++)
+        {
+            bbRay = g_BishopRayToEdge[u][cSquare];
+            if (!(bbRay & bbBishopSliders))
+            {
+                continue;
+            }
+            bbBlockers = bbRay & bbOccupied;
+            bbBlockerBit = g_BishopRayPositiveDir[u] ?
+                           (bbBlockers & (0ULL - bbBlockers)) :
+                           (1ULL << (FastLastBit(bbBlockers) - 1));
+            bbAttackers |= (bbBishopSliders & bbBlockerBit);
+        }
+    }
+
+    return bbAttackers;
+}
+
+void CDECL
+_GetAttacksBB(IN OUT SEE_LIST *pList,
+              IN POSITION *pos,
+              IN COOR cSquare,
+              IN ULONG uSide)
+/**
+
+Routine description:
+
+    PROOF OF CONCEPT -- not called from anywhere yet, and not a
+    replacement for GetAttacks/SlowGetAttacks until section 4/5/6 of
+    board_representation/MIGRATION.md (correctness sweep, benchmark,
+    toggle) are done. Reproduces SlowGetAttacks's exact semantics
+    (same deliberately-approximate no-pin/no-en-passant contract) via
+    _WhoAttacksSquareBB instead of the O(non-pawn-piece-count) mailbox
+    walk -- pawns handled identically to SlowGetAttacks (2-square
+    delta, unchanged, already O(1)).
+
+    Attacker order is not guaranteed to match SlowGetAttacks -- see()
+    sorts/heaps the list immediately after GetAttacks returns, so only
+    the *set* of attackers needs to match, not the sequence
+    (board_representation/MIGRATION.md section 4).
+
+Parameters:
+
+    SEE_LIST *pList : list to populate
+    POSITION *pos : the board
+    COOR cSquare : square in question
+    ULONG uSide : side we are looking for attacks from
+
+Return value:
+
+    void
+
+**/
+{
+    BITBOARD bbOccupied;
+    BITBOARD bbAttackers;
+    ULONG uBitIndex;
+    COOR c;
+    PIECE p;
+    static PIECE pPawn[2] = { BLACK_PAWN, WHITE_PAWN };
+
+#ifdef DEBUG
+    ASSERT(IS_ON_BOARD(cSquare));
+    ASSERT(IS_VALID_COLOR(uSide));
+    VerifyPositionConsistency(pos, FALSE);
+#endif
+    pList->uCount = 0;
+
+    //
+    // g_PawnAttackOriginBB[uSide][cSquare] (precomputed at startup --
+    // see data.c) is "the up to 2 squares a uSide pawn would need to
+    // stand on to attack cSquare," as a bitboard. One lookup + one AND
+    // against bbPawns[uSide] answers the whole question in bit-space --
+    // no COOR arithmetic (cSquare + iSeeDelta), no IS_ON_BOARD check,
+    // no mailbox load -- entirely replacing what iSeeDelta/pPawn[]
+    // used to do at runtime; only the (0-2) actual hits still need a
+    // COOR to populate the SEE_LIST.
+    {
+        BITBOARD bbPawnHits = g_PawnAttackOriginBB[uSide][cSquare] &
+                               pos->bbPawns[uSide];
+        ULONG uPawnBit;
+
+        while (bbPawnHits)
+        {
+            uPawnBit = FastFirstBit(bbPawnHits) - 1;
+            bbPawnHits &= (bbPawnHits - 1);
+            ADD_ATTACKER(pPawn[uSide], BIT_NUMBER_TO_COOR(uPawnBit), VALUE_PAWN);
+        }
+    }
+
+    //
+    // Knights/bishops/rooks/queens/king, via the bitboard primitive.
+    //
+    bbOccupied = _BuildOccupiedBB(pos);
+    bbAttackers = _WhoAttacksSquareBB(pos, cSquare, uSide, bbOccupied);
+    while (bbAttackers)
+    {
+        uBitIndex = FastFirstBit(bbAttackers) - 1;
+        bbAttackers &= (bbAttackers - 1); // clear lowest set bit
+        c = BIT_NUMBER_TO_COOR(uBitIndex);
+        p = pos->rgSquare[c].pPiece;
+        ADD_ATTACKER(p, c, PIECE_VALUE(p));
+    }
+}
+
 #ifdef SEE_HEAPS
 //
 // SEE_HEAPS works great in principle but makes MinLegalPiece
@@ -972,7 +1233,7 @@ Return value:
         UtilPanic(TESTCASE_FAILURE,
                   NULL,
                   "See mismatch",
-                  rgiList[0], 
+                  rgiList[0],
                   iSign,
                   __FILE__, __LINE__);
     }