From be420bb8d1d5d16a4e24ab6fd706a5ae898eaa85 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Fri, 4 Sep 2026 09:22:46 -0700 Subject: 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 Claude-Session: https://claude.ai/code/session_01Jntky4yGUTyQVaGCXms4F2 --- src/see.c | 263 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 262 insertions(+), 1 deletion(-) (limited to 'src/see.c') 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__); } -- cgit v1.3