Land bitboard move generation (Part A+B) and movesup.c bitboard queries; default on

Implements the full board_representation/MOVEGEN_MIGRATION.md scope:
bitboard-backed generators for all six not-in-check piece types plus
the JumpTable-avoiding whole-node dispatch fork (_GenerateAllMovesBB),
the in-check escape path (king flight + block/capture), and
movesup.c's ExposesCheck/FasterExposesCheck/ExposesCheckEp/IsAttacked/
InCheck bitboard equivalents. Nine toggles total
(GENERATE_{KNIGHT,KING,ROOK,BISHOP,QUEEN,PAWN}_BITBOARD,
GENERATE_ESCAPES_{KING,BLOCK}_BITBOARD, EXPOSESCHECK_BITBOARD,
ISATTACKED_BITBOARD), all now on by default in GNUmakefile --
DISABLE_BITBOARD_MOVEGEN=1 opts back into the mailbox path, which
remains fully present and compiled either way.

Correctness verified via perft (Kiwipete, Position 4), the move-set
comparison harness across 20,000 random positions, all nine toggles
combined cleanly (15/15 runs, after fixing a GenerateRandomLegalPosition
en-passant-sentinel bug in the test harness), and sd10 on all three
curated suites showing zero solve-count regression vs head_reference
(the ecm_hard_quick delta traced to unrelated intervening commits).
Speed: most individual generators land near parity by design (mailbox's
per-square walk was already close to O(destination count)); the real,
consistent wins are the dispatch-layer fork (up to 23% in dense
positions) and IsAttackedBB (0.73x-0.93x of mailbox).

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

1 files changed, 362 insertions, 0 deletions

diff --git a/src/data.c b/src/data.c
index 217f1e8..aa5ef91 100755
--- a/src/data.c
+++ b/src/data.c
@@ -738,6 +738,58 @@ Return value:
 }
 
 //
+// Per-square "all squares a king on c can step to" bitboard (normal
+// king moves only -- castling stays mailbox, see
+// board_representation/MOVEGEN_MIGRATION.md section 1's explicit
+// non-goal and section 3 step 2). Same shape as g_KnightAttacksBB:
+// GetAttacks's king case used a DISTANCE(...)==1 delta check instead,
+// since it only ever needs a single square's membership test, not an
+// enumerable destination set -- move generation needs the actual set,
+// hence this table exists where GetAttacks needed none. Built once at
+// startup by InitializeKingAttackTables().
+//
+BITBOARD g_KingAttacksBB[128];
+
+void
+InitializeKingAttackTables(void)
+/**
+
+Routine description:
+
+    One-time startup init for g_KingAttacksBB -- see its comment.
+
+Parameters:
+
+    void
+
+Return value:
+
+    void
+
+**/
+{
+    ULONG uRank, uFile, uDir;
+    COOR c, cSquare;
+
+    memset(g_KingAttacksBB, 0, sizeof(g_KingAttacksBB));
+    for (uRank = 0; uRank < 8; uRank++)
+    {
+        for (uFile = 0; uFile < 8; uFile++)
+        {
+            c = (uRank << 4) | uFile;
+            for (uDir = 0; g_iQKDeltas[uDir] != 0; uDir++)
+            {
+                cSquare = c + g_iQKDeltas[uDir];
+                if (IS_ON_BOARD(cSquare))
+                {
+                    g_KingAttacksBB[c] |= COOR_TO_BB(cSquare);
+                }
+            }
+        }
+    }
+}
+
+//
 // 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
@@ -793,3 +845,313 @@ Return value:
         }
     }
 }
+
+//
+// Magic-bitboard tables for rook/bishop move generation -- see
+// board_representation/MOVEGEN_MIGRATION.md sections 2a/3 for the
+// full design writeup. Everything here (occupancy masks, magic
+// numbers, and the attack tables they index into) is computed once at
+// startup by InitMagic(), never hardcoded -- a validation prototype
+// measured the full search+build+verify cost at ~0.22s for both piece
+// types combined, cheap enough to just pay at every process launch
+// rather than maintaining hand-pasted constants that could silently
+// drift out of sync with the ray tables or square numbering they're
+// derived from.
+//
+// g_RookOccupancyMask[c] / g_BishopOccupancyMask[c]: the "relevant
+// occupancy" bits for a slider on c -- g_RookRayToEdge/
+// g_BishopRayToEdge's full ray-to-edge, minus each direction's
+// outermost square (a piece standing on the actual board edge can't
+// hide a further blocker, so it doesn't affect which squares are
+// reachable and must be excluded to keep the occupancy-permutation
+// count, and therefore the attack table size, minimal).
+//
+// g_RookMagic[c] / g_BishopMagic[c] and g_RookMagicShift[c] /
+// g_BishopMagicShift[c]: found by InitMagic() via a random
+// sparse-candidate search, fixed-seeded (see g_MagicRngState below)
+// so a given build reproduces the exact same magics on every run --
+// deliberately NOT using libc's rand()/srand(), since main.c's
+// startup path already calls srand((unsigned int)time(0)) for
+// unrelated reasons, and piggybacking on that shared, time-seeded
+// generator would silently reintroduce the very non-determinism this
+// design is meant to avoid.
+//
+// g_RookAttackTable[c] / g_BishopAttackTable[c]: one malloc'd array
+// per square, indexed by ((occupancy & mask) * magic) >> shift,
+// giving the complete pseudo-legal destination bitboard (empty
+// squares plus the nearest blocker in every direction, regardless of
+// which side owns it -- the caller is responsible for ANDing off
+// friendly occupancy before treating the blocker square as a legal
+// destination, same convention g_KnightAttacksBB's consumer already
+// uses). Never freed -- these live for the process's lifetime, same
+// as every other table in this file.
+//
+BITBOARD g_RookOccupancyMask[128];
+BITBOARD g_BishopOccupancyMask[128];
+BITBOARD g_RookMagic[128];
+BITBOARD g_BishopMagic[128];
+ULONG g_RookMagicShift[128];
+ULONG g_BishopMagicShift[128];
+BITBOARD *g_RookAttackTable[128];
+BITBOARD *g_BishopAttackTable[128];
+
+// Private PRNG state for the magic-number search -- deliberately
+// separate from libc's rand()/srand() (see the block comment above).
+// xorshift64*, fixed literal seed: the exact value doesn't matter, but
+// it must never change to a time-based or otherwise run-varying seed,
+// or every reproducibility claim in MOVEGEN_MIGRATION.md section 2a
+// stops being true.
+static UINT64 g_MagicRngState = 88172645463325252ULL;
+
+static UINT64
+_MagicNextRandom64(void)
+{
+    UINT64 x = g_MagicRngState;
+    x ^= x << 13;
+    x ^= x >> 7;
+    x ^= x << 17;
+    g_MagicRngState = x;
+    return x;
+}
+
+// Sparse (mostly-zero-bit) candidates are known to converge faster in
+// magic-number search than uniform random 64-bit values -- standard
+// technique, matches the validation prototype this was ported from.
+static UINT64
+_MagicSparseRandom64(void)
+{
+    return _MagicNextRandom64() & _MagicNextRandom64() & _MagicNextRandom64();
+}
+
+// Slow, obviously-correct reference used both to build each magic
+// table's contents and to verify it before InitMagic() accepts it:
+// walk each of the 4 directions from c until (and including) the
+// first occupied square, given a full occupancy bitboard covering
+// both sides' pieces.
+static BITBOARD
+_MagicSlowAttacks(COOR c, BITBOARD bbOccupied, const int iDelta[4])
+{
+    BITBOARD bbResult = 0;
+    ULONG uDir;
+    COOR cSquare;
+
+    for (uDir = 0; uDir < 4; uDir++)
+    {
+        for (cSquare = c + iDelta[uDir];
+             IS_ON_BOARD(cSquare);
+             cSquare += iDelta[uDir])
+        {
+            BITBOARD bbSq = COOR_TO_BB(cSquare);
+            bbResult |= bbSq;
+            if (bbOccupied & bbSq)
+            {
+                break;
+            }
+        }
+    }
+    return bbResult;
+}
+
+// Standard "carry-rippler" occupancy-subset enumeration: the uIndex-th
+// subset of mask's set bits, treating uIndex's own bits as a
+// present/absent flag for each of mask's bits in ascending-bit order.
+static BITBOARD
+_MagicIndexToOccupancy(ULONG uIndex, ULONG uBits, BITBOARD mask)
+{
+    BITBOARD bbResult = 0;
+    ULONG i, uBit;
+
+    for (i = 0; i < uBits; i++)
+    {
+        uBit = FastFirstBit(mask) - 1;
+        mask &= mask - 1;
+        if (uIndex & (1UL << i))
+        {
+            bbResult |= (1ULL << uBit);
+        }
+    }
+    return bbResult;
+}
+
+// Builds the relevant-occupancy mask for one square: the full ray to
+// the edge in each of the 4 directions, minus that direction's
+// outermost square -- see the block comment above
+// g_RookOccupancyMask/g_BishopOccupancyMask.
+static BITBOARD
+_MagicBuildOccupancyMask(COOR c, const int iDelta[4])
+{
+    BITBOARD bbResult = 0;
+    ULONG uDir;
+    COOR cSquare;
+
+    for (uDir = 0; uDir < 4; uDir++)
+    {
+        for (cSquare = c + iDelta[uDir];
+             IS_ON_BOARD(cSquare);
+             cSquare += iDelta[uDir])
+        {
+            if (IS_ON_BOARD(cSquare + iDelta[uDir]))
+            {
+                bbResult |= COOR_TO_BB(cSquare);
+            }
+        }
+    }
+    return bbResult;
+}
+
+// Finds a collision-free magic number for one square, builds its
+// attack table from it, and verifies the whole thing against the slow
+// reference one more time before returning -- the section 2a
+// collision-freedom gate, run fresh at every startup rather than
+// trusted from a prior offline run.
+static void
+_MagicFindAndBuildForSquare(COOR c, BITBOARD mask, const int iDelta[4],
+                             BITBOARD *pMagic, ULONG *pShift,
+                             BITBOARD **ppTable)
+{
+    ULONG uBits = CountBits(mask);
+    ULONG uSize = 1UL << uBits;
+    ULONG uShift = 64 - uBits;
+    BITBOARD *rgbbOccupancy = malloc(sizeof(BITBOARD) * uSize);
+    BITBOARD *rgbbAttacks = malloc(sizeof(BITBOARD) * uSize);
+    BITBOARD *rgbbTable = malloc(sizeof(BITBOARD) * uSize);
+    FLAG *rgfFilled = malloc(sizeof(FLAG) * uSize);
+    ULONG i;
+    UINT64 uMagic;
+
+    if ((NULL == rgbbOccupancy) || (NULL == rgbbAttacks) ||
+        (NULL == rgbbTable) || (NULL == rgfFilled))
+    {
+        Bug("InitMagic: out of memory building table for square %d\n", c);
+    }
+
+    for (i = 0; i < uSize; i++)
+    {
+        rgbbOccupancy[i] = _MagicIndexToOccupancy(i, uBits, mask);
+        rgbbAttacks[i] = _MagicSlowAttacks(c, rgbbOccupancy[i], iDelta);
+    }
+
+    for (;;)
+    {
+        FLAG fCollision = FALSE;
+        ULONG uIndex;
+
+        uMagic = _MagicSparseRandom64();
+
+        // Quick reject: a magic whose high byte doesn't spread widely
+        // when multiplied against the mask rarely yields a
+        // collision-free hash -- a cheap filter to skip obviously bad
+        // candidates before paying for the full uSize-entry pass.
+        if (CountBits((UINT64)(mask * uMagic) & 0xFF00000000000000ULL) < 6)
+        {
+            continue;
+        }
+
+        memset(rgfFilled, 0, sizeof(FLAG) * uSize);
+        for (i = 0; (i < uSize) && !fCollision; i++)
+        {
+            uIndex = (ULONG)(((UINT64)rgbbOccupancy[i] * uMagic) >> uShift);
+            if (!rgfFilled[uIndex])
+            {
+                rgfFilled[uIndex] = TRUE;
+                rgbbTable[uIndex] = rgbbAttacks[i];
+            }
+            else if (rgbbTable[uIndex] != rgbbAttacks[i])
+            {
+                fCollision = TRUE;
+            }
+        }
+        if (!fCollision)
+        {
+            break;
+        }
+    }
+
+    //
+    // Belt-and-suspenders: re-verify every occupancy subset against
+    // the slow reference one more time before accepting this magic.
+    // Redundant with the search loop's own collision bookkeeping
+    // above in the common case, but this is the load-bearing
+    // correctness gate the rest of the magic-bitboard subsystem
+    // depends on (MOVEGEN_MIGRATION.md section 2a) -- worth paying
+    // for explicitly rather than trusting the search loop alone.
+    //
+    for (i = 0; i < uSize; i++)
+    {
+        BITBOARD bbOcc = _MagicIndexToOccupancy(i, uBits, mask);
+        BITBOARD bbExpected = _MagicSlowAttacks(c, bbOcc, iDelta);
+        ULONG uIndex = (ULONG)(((UINT64)bbOcc * uMagic) >> uShift);
+
+        if (rgbbTable[uIndex] != bbExpected)
+        {
+            Bug("InitMagic: verification failed for square %d, "
+                "occupancy subset %lu\n", c, i);
+        }
+    }
+
+    *pMagic = uMagic;
+    *pShift = uShift;
+    *ppTable = rgbbTable;
+    free(rgbbOccupancy);
+    free(rgbbAttacks);
+    free(rgfFilled);
+}
+
+void
+InitMagic(void)
+/**
+
+Routine description:
+
+    One-time startup init for the rook/bishop magic-bitboard tables --
+    see the block comment above g_RookOccupancyMask/g_BishopOccupancyMask
+    for the full design and board_representation/MOVEGEN_MIGRATION.md
+    sections 2a/3 for the writeup. Must run after nothing in particular
+    (no dependency on the other Initialize*Tables functions), but is
+    grouped alongside them in main.c's startup sequence for consistency.
+
+Parameters:
+
+    void
+
+Return value:
+
+    void
+
+**/
+{
+    ULONG uRank, uFile;
+
+    memset(g_RookOccupancyMask, 0, sizeof(g_RookOccupancyMask));
+    memset(g_BishopOccupancyMask, 0, sizeof(g_BishopOccupancyMask));
+    memset(g_RookMagic, 0, sizeof(g_RookMagic));
+    memset(g_BishopMagic, 0, sizeof(g_BishopMagic));
+    memset(g_RookMagicShift, 0, sizeof(g_RookMagicShift));
+    memset(g_BishopMagicShift, 0, sizeof(g_BishopMagicShift));
+    memset(g_RookAttackTable, 0, sizeof(g_RookAttackTable));
+    memset(g_BishopAttackTable, 0, sizeof(g_BishopAttackTable));
+
+    for (uRank = 0; uRank < 8; uRank++)
+    {
+        for (uFile = 0; uFile < 8; uFile++)
+        {
+            COOR c = (uRank << 4) | uFile;
+
+            g_RookOccupancyMask[c] =
+                _MagicBuildOccupancyMask(c, g_RookRayDeltas);
+            _MagicFindAndBuildForSquare(c, g_RookOccupancyMask[c],
+                                        g_RookRayDeltas,
+                                        &g_RookMagic[c],
+                                        &g_RookMagicShift[c],
+                                        &g_RookAttackTable[c]);
+
+            g_BishopOccupancyMask[c] =
+                _MagicBuildOccupancyMask(c, g_BishopRayDeltas);
+            _MagicFindAndBuildForSquare(c, g_BishopOccupancyMask[c],
+                                        g_BishopRayDeltas,
+                                        &g_BishopMagic[c],
+                                        &g_BishopMagicShift[c],
+                                        &g_BishopAttackTable[c]);
+        }
+    }
+}