diff options
| -rwxr-xr-x | src/bitboard.c | 2 | ||||
| -rwxr-xr-x | src/board.c | 10 | ||||
| -rw-r--r-- | src/board_representation/MIGRATION.md | 219 | ||||
| -rwxr-xr-x | src/chess.h | 50 | ||||
| -rwxr-xr-x | src/data.c | 73 | ||||
| -rwxr-xr-x | src/fen.c | 1 | ||||
| -rwxr-xr-x | src/main.c | 1 | ||||
| -rwxr-xr-x | src/move.c | 14 | ||||
| -rwxr-xr-x | src/see.c | 263 | ||||
| -rw-r--r-- | src/testsee.c | 136 | ||||
| -rw-r--r-- | src/testsup.c | 2 |
11 files changed, 712 insertions, 59 deletions
diff --git a/src/bitboard.c b/src/bitboard.c index 9e9df48..ad45ea6 100755 --- a/src/bitboard.c +++ b/src/bitboard.c @@ -322,7 +322,7 @@ Return value: return(0); } -COOR +COOR CoorFromBitBoardRank8ToRank1(BITBOARD *pbb) /** diff --git a/src/board.c b/src/board.c index 0c5f4df..0b195be 100755 --- a/src/board.c +++ b/src/board.c @@ -169,6 +169,7 @@ Return value: "Extra pieces on board that are not accounted for", "Fifty move counter is too high", "bbPieces bitboard doesn't match piece list", + "bbPawns bitboard doesn't match pawn list", }; ULONG u, v; COOR c; @@ -177,6 +178,7 @@ Return value: ULONG uNonPawnMaterial[2] = {0, 0}; ULONG uNonPawnCount[2][7]; BITBOARD bbPieces[2][8]; + BITBOARD bbPawns[2]; ULONG uSigmaNonPawnCount[2] = {0, 0}; ULONG uWhiteSqBishopCount[2] = {0, 0}; UINT64 u64Computed; @@ -186,6 +188,7 @@ Return value: memset(uNonPawnCount, 0, sizeof(uNonPawnCount)); memset(bbPieces, 0, sizeof(bbPieces)); + memset(bbPawns, 0, sizeof(bbPawns)); u64Computed = ComputeSig(pos); if (pos->u64NonPawnSig != u64Computed) { @@ -268,6 +271,7 @@ Return value: } uPawnMaterial[u] += VALUE_PAWN; uPawnCount[u]++; + bbPawns[u] |= COOR_TO_BB(c); } } @@ -364,6 +368,12 @@ Return value: } } + if (pos->bbPawns[u] != bbPawns[u]) + { + uReason = 22; + 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 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 diff --git a/src/chess.h b/src/chess.h index 1f874b9..5c5bbf2 100755 --- a/src/chess.h +++ b/src/chess.h @@ -658,6 +658,17 @@ typedef struct _POSITION // (cNonPawns[color][0]), a bitboard adds nothing. BITBOARD bbPieces[2][8]; + // Per-color pawn location bitboard -- same incremental-maintenance + // idea as bbPieces above, but for pawns (which bbPieces + // deliberately excludes). Exists so _BuildOccupiedBB (see.c) can + // build full-board occupancy via two ORs instead of looping + // cPawns[2][8] (up to 16 iterations) on every call -- see + // board_representation/MIGRATION.md section 3. Distinct from + // pHash->bbPawnLocations[2] (pawn-hash-keyed, tied to pawn-eval + // caching); this one is plain POSITION state, reachable without a + // SEARCHER_THREAD_CONTEXT. + BITBOARD bbPawns[2]; + ULONG uWhiteSqBishopCount[2]; // num bishops on white squares SCORE iMaterialBalance[2]; // material balance @@ -2027,12 +2038,15 @@ extern BITBOARD BBADJACENT_RANKS[9]; // board_representation/MIGRATION.md) the planned bbPieces-backed // GetAttacks/CountKingSafetyDefects primitive. extern BITBOARD g_RookRayToEdge[4][128]; +extern BITBOARD g_RookRayAll[128]; extern const int g_RookRayDeltas[4]; extern const FLAG g_RookRayPositiveDir[4]; extern BITBOARD g_BishopRayToEdge[4][128]; +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_PawnAttackOriginBB[2][128]; void InitializeWhiteSquaresTable(void); @@ -2055,6 +2069,9 @@ InitializeBishopRayTables(void); void InitializeKnightAttackTables(void); +void +InitializePawnAttackOriginTable(void); + #ifdef DEBUG ULONG CheckVectorWithIndex(int i, ULONG uColor); #define CHECK_VECTOR_WITH_INDEX(i, color) \ @@ -2797,6 +2814,31 @@ SlowFirstBit(BITBOARD bb); ULONG CDECL SlowLastBit(BITBOARD bb); +// Compiler-builtin (__builtin_ctzll/__builtin_clzll) bsf/bsr -- same +// 1-based/0-for-empty contract as FirstBit/LastBit below, and the +// exact same bsf/bsr instruction the asm FirstBit/LastBit use (this +// build passes no -mbmi, so __builtin_ctzll still lowers to bsf, not +// tzcnt) -- but static inline, so a call site pays for the +// instruction itself and nothing else, no CDECL call/ret/arg-marshal +// overhead. That overhead is exactly what makes it worth having a +// second copy instead of just calling FirstBit/LastBit everywhere: +// worthwhile in a per-move-generated, per-search-node hot path, +// pointless as a blanket replacement elsewhere. static (not extern) +// deliberately -- a plain non-static C99 "inline" definition with no +// out-of-line instantiation anywhere is a link-time trap, not just a +// style choice. +static ULONG INLINE +FastFirstBit(IN BITBOARD bb) +{ + return bb ? ((ULONG)__builtin_ctzll(bb) + 1) : 0; +} + +static ULONG INLINE +FastLastBit(IN BITBOARD bb) +{ + return bb ? (ULONG)(64 - __builtin_clzll(bb)) : 0; +} + #ifdef CROUTINES #define CountBits SlowCountBits #define FirstBit SlowFirstBit @@ -2856,6 +2898,14 @@ SlowGetAttacks(SEE_LIST *pList, #define GetAttacks SlowGetAttacks #endif +// board_representation/MIGRATION.md section 3: bbPieces-backed +// GetAttacks PoC -- not wired into the GetAttacks macro above yet. +void CDECL +_GetAttacksBB(SEE_LIST *pList, + POSITION *pos, + COOR cSquare, + ULONG uSide); + #ifdef _X86_ // // Note: this is most of the stuff that x86.asm assumes about the @@ -578,6 +578,15 @@ 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 }; +// Per-square OR of all 4 g_RookRayToEdge directions -- "every square a +// rook on c could reach on an empty board, regardless of direction." +// One lookup (+ AND against a slider bitboard) to answer "is uSide's +// rook/queen bitboard aligned with c *at all*", vs. 4 separate +// g_RookRayToEdge lookups to discover the same "no" -- see +// _WhoAttacksSquareBB (see.c) for the consumer and +// board_representation/MIGRATION.md section 3 for the writeup. +BITBOARD g_RookRayAll[128]; + void InitializeRookRayTables(void) /** @@ -600,6 +609,7 @@ Return value: COOR c, cSquare; memset(g_RookRayToEdge, 0, sizeof(g_RookRayToEdge)); + memset(g_RookRayAll, 0, sizeof(g_RookRayAll)); for (uRank = 0; uRank < 8; uRank++) { for (uFile = 0; uFile < 8; uFile++) @@ -612,6 +622,7 @@ Return value: cSquare += g_RookRayDeltas[uDir]) { g_RookRayToEdge[uDir][c] |= COOR_TO_BB(cSquare); + g_RookRayAll[c] |= COOR_TO_BB(cSquare); } } } @@ -625,6 +636,9 @@ 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 }; +// g_RookRayAll's counterpart for the bishop's 4 diagonal directions. +BITBOARD g_BishopRayAll[128]; + void InitializeBishopRayTables(void) /** @@ -647,6 +661,7 @@ Return value: COOR c, cSquare; memset(g_BishopRayToEdge, 0, sizeof(g_BishopRayToEdge)); + memset(g_BishopRayAll, 0, sizeof(g_BishopRayAll)); for (uRank = 0; uRank < 8; uRank++) { for (uFile = 0; uFile < 8; uFile++) @@ -659,6 +674,7 @@ Return value: cSquare += g_BishopRayDeltas[uDir]) { g_BishopRayToEdge[uDir][c] |= COOR_TO_BB(cSquare); + g_BishopRayAll[c] |= COOR_TO_BB(cSquare); } } } @@ -720,3 +736,60 @@ Return value: } } } + +// +// 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 +// pawn attacks diagonally forward, so it must stand behind-and-beside +// c to hit it). Same idea as g_KnightAttacksBB: a single lookup+AND +// against bbPawns[side] answers "does uSide have a pawn attacking c" +// entirely in bit-space, no COOR arithmetic/IS_ON_BOARD check at +// runtime -- see _GetAttacksBB (see.c) for the consumer. +// +BITBOARD g_PawnAttackOriginBB[2][128]; + +void +InitializePawnAttackOriginTable(void) +/** + +Routine description: + + One-time startup init for g_PawnAttackOriginBB -- see its comment. + +Parameters: + + void + +Return value: + + void + +**/ +{ + static const int iSeeDelta[2] = { -17, +15 }; // BLACK, WHITE + ULONG uRank, uFile, uSide; + COOR c, cOrigin; + + memset(g_PawnAttackOriginBB, 0, sizeof(g_PawnAttackOriginBB)); + for (uRank = 0; uRank < 8; uRank++) + { + for (uFile = 0; uFile < 8; uFile++) + { + c = (uRank << 4) | uFile; + for (uSide = 0; uSide < 2; uSide++) + { + cOrigin = c + iSeeDelta[uSide]; + if (IS_ON_BOARD(cOrigin)) + { + g_PawnAttackOriginBB[uSide][c] |= COOR_TO_BB(cOrigin); + } + cOrigin += 2; + if (IS_ON_BOARD(cOrigin)) + { + g_PawnAttackOriginBB[uSide][c] |= COOR_TO_BB(cOrigin); + } + } + } + } +} @@ -300,6 +300,7 @@ Return value: // location to the list and point from the pawn to the list. // pos->cPawns[uColor][uPieceCounters[uPieceIndex]] = cSquare; + pos->bbPawns[uColor] |= COOR_TO_BB(cSquare); pos->rgSquare[cSquare].uIndex = uPieceCounters[uPieceIndex]; pos->rgSquare[cSquare].pPiece = p; pos->uPawnMaterial[uColor] += VALUE_PAWN; @@ -464,6 +464,7 @@ Return value: InitializeRookRayTables(); InitializeBishopRayTables(); InitializeKnightAttackTables(); + InitializePawnAttackOriginTable(); InitializeOpeningBook(); InitializeDynamicMoveOrdering(); InitLMRTable(); @@ -121,6 +121,8 @@ Return value: ASSERT(IS_VALID_COLOR(c)); ASSERT(pos->cPawns[c][uIndex] == cFrom); pos->cPawns[c][uIndex] = cTo; + pos->bbPawns[c] &= ~COOR_TO_BB(cFrom); + pos->bbPawns[c] |= COOR_TO_BB(cTo); pos->u64PawnSig ^= g_u64PawnSigSeeds[cFrom][c]; pos->u64PawnSig ^= g_u64PawnSigSeeds[cTo][c]; pos->rgSquare[cTo].pPiece = p; @@ -224,6 +226,8 @@ Return value: ASSERT(IS_VALID_COLOR(c)); ASSERT(pos->cPawns[c][uIndex] == cFrom); pos->cPawns[c][uIndex] = cTo; + pos->bbPawns[c] &= ~COOR_TO_BB(cFrom); + pos->bbPawns[c] |= COOR_TO_BB(cTo); pos->rgSquare[cTo].pPiece = p; pos->rgSquare[cTo].uIndex = uIndex; #ifdef DEBUG @@ -293,10 +297,11 @@ Return value: ASSERT(pos->uPawnMaterial[color] <= (7 * VALUE_PAWN)); pos->u64PawnSig ^= g_u64PawnSigSeeds[cSquare][color]; + pos->bbPawns[color] &= ~COOR_TO_BB(cSquare); // // Remove this pawn from the pawn list. - // + // pos->uPawnCount[color]--; ASSERT(pos->uPawnCount[color] < 8); uLastIndex = pos->uPawnCount[color]; @@ -426,10 +431,11 @@ Return value: pos->uPawnMaterial[color] -= pv; ASSERT(pos->uPawnMaterial[color] <= (7 * VALUE_PAWN)); - + pos->bbPawns[color] &= ~COOR_TO_BB(cSquare); + // // Remove this pawn from the pawn list. - // + // pos->uPawnCount[color]--; ASSERT(pos->uPawnCount[color] < 8); uLastIndex = pos->uPawnCount[color]; // optimized... @@ -542,6 +548,7 @@ Return value: pos->uPawnCount[color]++; ASSERT(pos->uPawnCount[color] <= 8); pos->cPawns[color][uIndex] = cSquare; + pos->bbPawns[color] |= COOR_TO_BB(cSquare); pos->u64PawnSig ^= g_u64PawnSigSeeds[cSquare][color]; } else @@ -634,6 +641,7 @@ Return value: pos->uPawnCount[color]++; ASSERT(pos->uPawnCount[color] <= 8); pos->cPawns[color][uIndex] = cSquare; + pos->bbPawns[color] |= COOR_TO_BB(cSquare); } else { @@ -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__); } diff --git a/src/testsee.c b/src/testsee.c index da7df59..77fd706 100644 --- a/src/testsee.c +++ b/src/testsee.c @@ -134,16 +134,36 @@ DebugSEE(POSITION *pos, #endif #ifdef TEST -FLAG +static int +_SeeListEntryCompare(const void *pA, const void *pB) +{ + const SEE_THREESOME *a = (const SEE_THREESOME *)pA; + const SEE_THREESOME *b = (const SEE_THREESOME *)pB; + if (a->cLoc != b->cLoc) return ((int)a->cLoc - (int)b->cLoc); + return ((int)a->pPiece - (int)b->pPiece); +} + +FLAG SeeListsAreEqual(SEE_LIST *pA, SEE_LIST *pB) { + // Order-independent: GetAttacks's caller (SEE()) sorts/heaps the + // list immediately after it's populated, so a bitboard-based + // GetAttacks returning the same *set* of attackers in a different + // order is a correct match, not a bug (board_representation/ + // MIGRATION.md section 4). Sort a scratch copy of each by + // (cLoc, pPiece) before comparing field-by-field. + SEE_LIST sA = *pA; + SEE_LIST sB = *pB; ULONG u; - if (pA->uCount != pB->uCount) return FALSE; - for (u = 0; u < pA->uCount; u++) + + if (sA.uCount != sB.uCount) return FALSE; + qsort(sA.data, sA.uCount, sizeof(sA.data[0]), _SeeListEntryCompare); + qsort(sB.data, sB.uCount, sizeof(sB.data[0]), _SeeListEntryCompare); + for (u = 0; u < sA.uCount; u++) { - if ((pA->data[u].pPiece != pB->data[u].pPiece) || - (pA->data[u].cLoc != pB->data[u].cLoc) || - (pA->data[u].uVal != pB->data[u].uVal)) + if ((sA.data[u].pPiece != sB.data[u].pPiece) || + (sA.data[u].cLoc != sB.data[u].cLoc) || + (sA.data[u].uVal != sB.data[u].uVal)) { return FALSE; } @@ -159,20 +179,21 @@ TestGetAttacks(void) COOR c; SEE_LIST rgSlowList; SEE_LIST rgAsmList; + SEE_LIST rgBBList; ULONG color; - + #if !defined(_X86_) && !defined(_X64_) return; #endif - + Trace("Testing GetAttacks...\n"); for (u = 0; u < 20000; u++) { GenerateRandomLegalPosition(&pos); - FOREACH_SQUARE(c) + FOREACH_SQUARE(c) { if (!IS_ON_BOARD(c)) continue; - for (color = BLACK; color <= WHITE; color++) + for (color = BLACK; color <= WHITE; color++) { SlowGetAttacks(&rgSlowList, &pos, @@ -185,11 +206,104 @@ TestGetAttacks(void) if (!SeeListsAreEqual(&rgSlowList, &rgAsmList)) { UtilPanic(TESTCASE_FAILURE, - &pos, + &pos, "SEE_LIST mismatch", &rgSlowList, &rgAsmList, __FILE__, __LINE__); } + + // board_representation/MIGRATION.md section 3/4: + // bbPieces-backed GetAttacks PoC, same correctness + // gate as the asm/C comparison above. + _GetAttacksBB(&rgBBList, + &pos, + c, + color); + if (!SeeListsAreEqual(&rgSlowList, &rgBBList)) + { + UtilPanic(TESTCASE_FAILURE, + &pos, + "SEE_LIST mismatch (_GetAttacksBB)", + &rgSlowList, &rgBBList, + __FILE__, __LINE__); + } + } + } + } + + // + // Speed: board_representation/MIGRATION.md section 5's isolated + // cycles/call microbenchmark, pulled forward here since it's cheap + // to add right alongside the correctness gate that just proved the + // two implementations equivalent. Three positions spanning piece + // density (opening/middlegame/endgame), SlowGetAttacks vs + // _GetAttacksBB interleaved call-by-call (not phase-by-phase) to + // cancel shared-box noise -- a red flag (flat or inverted result) + // here would mean stopping before wiring this in any further, same + // as the Eval occupancy-bitboard work that motivated this file. + { + 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; + SEE_LIST rgList; + UINT64 u64SlowTotal, u64AsmTotal, u64BBTotal, u64Start; + ULONG uIter; + ULONG uSq; + COOR cBench; + ULONG uSide; + const ULONG uCallsPerPosition = 200000; + + // GetAttacks (unqualified) is the real production entry point -- + // the hand-tuned x86/x64 asm routine, not SlowGetAttacks (the C + // reference used only for correctness comparison above). That's + // the actual competitor _GetAttacksBB has to beat; SlowGetAttacks + // is included only as a third data point, not the bar to clear. + Trace("Benchmarking GetAttacks: asm GetAttacks vs SlowGetAttacks " + "vs _GetAttacksBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + u64SlowTotal = 0; + u64AsmTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + uSq = uIter % 64; + cBench = BIT_NUMBER_TO_COOR(uSq); + uSide = uIter & 1; + if (!IS_ON_BOARD(cBench)) continue; + + u64Start = SystemReadTimeStampCounter(); + GetAttacks(&rgList, &posBench, cBench, uSide); + u64AsmTotal += (SystemReadTimeStampCounter() - u64Start); + + u64Start = SystemReadTimeStampCounter(); + SlowGetAttacks(&rgList, &posBench, cBench, uSide); + u64SlowTotal += (SystemReadTimeStampCounter() - u64Start); + + u64Start = SystemReadTimeStampCounter(); + _GetAttacksBB(&rgList, &posBench, cBench, uSide); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); } + printf(" %s: asm GetAttacks %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, SlowGetAttacks %" + COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GetAttacksBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx asm)\n", + rgszLabel[u], + u64AsmTotal / uCallsPerPosition, + u64SlowTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64AsmTotal); } } } diff --git a/src/testsup.c b/src/testsup.c index 43e39e9..3ed50e3 100644 --- a/src/testsup.c +++ b/src/testsup.c @@ -161,6 +161,7 @@ GenerateRandomLegalPosition(POSITION *pos) pos->rgSquare[c].pPiece = p; pos->uPawnCount[uColor]++; pos->uPawnMaterial[uColor] += VALUE_PAWN; + pos->bbPawns[uColor] |= COOR_TO_BB(c); break; } else if (!IS_KING(p) && @@ -173,6 +174,7 @@ GenerateRandomLegalPosition(POSITION *pos) pos->rgSquare[c].pPiece = p; pos->rgSquare[c].uIndex = uIndex; pos->uNonPawnMaterial[uColor] += PIECE_VALUE(p); + pos->bbPieces[uColor][PIECE_TYPE(p)] |= COOR_TO_BB(c); if (IS_BISHOP(p)) { if (IS_WHITE_SQUARE_COOR(c)) |