/** Copyright (c) Scott Gasch Module Name: data.c Abstract: Large data structures and the code that creates/verifies them. Author: Scott Gasch (scott.gasch@gmail.com) 10 May 2004 Revision History: $Id: data.c 345 2007-12-02 22:56:42Z scott $ **/ #include "chess.h" // Distance between two squares lookup table ULONG g_uDistance[256]; ULONG *g_pDistance = &(g_uDistance[128]); // Who controls the square lookup table CHAR g_SwapTable[14][32][32]; // Vector (bitvector indicating which pieces can move between squares) and // Delta (direction to travel to get from square a to square b) lookup table. VECTOR_DELTA g_VectorDelta[256]; VECTOR_DELTA *g_pVectorDelta = &(g_VectorDelta[128]); // Hardcoded move patterns to terminate PVs with MOVE NULLMOVE = {0}; MOVE HASHMOVE = {0x11118888}; MOVE RECOGNMOVE = {0x22228888}; MOVE DRAWMOVE = {0x33338888}; MOVE MATEMOVE = {0x44448888}; // Is a square white? FLAG g_fIsWhiteSquare[128]; #ifdef DEBUG COOR DistanceBetweenSquares(COOR a, COOR b) { int i = (int)a - (int)b + 128; int j = (int)b - (int)a + 128; ASSERT(IS_ON_BOARD(a)); ASSERT(IS_ON_BOARD(b)); ASSERT((i >= 0) && (i < 256)); ASSERT(g_uDistance[i] == REAL_DISTANCE(a, b)); ASSERT(g_pDistance[(int)a - (int)b] == g_uDistance[i]); ASSERT(g_pDistance[(int)b - (int)a] == g_uDistance[i]); ASSERT(g_uDistance[j] == REAL_DISTANCE(a, b)); return(REAL_DISTANCE(a, b)); } #define VALID_VECTOR(x) \ (((x) == 0) || \ ((x) == (1 << KNIGHT)) || \ ((x) == ( (1 << BISHOP) | (1 << QUEEN))) || \ ((x) == ( (1 << ROOK) | (1 << QUEEN))) || \ ((x) == ( (1 << BISHOP) | (1 << QUEEN) | (1 << KING))) || \ ((x) == ( (1 << ROOK) | (1 << QUEEN) | (1 << KING))) || \ ((x) == ( (1 << BISHOP) | (1 << QUEEN) | (1 << KING) | (1 << PAWN)))) #define VALID_INDEX(x) \ (((x) >= -128) && ((x) <= 127)) ULONG CheckVectorWithIndex(int i, ULONG uColor) { ULONG u; ASSERT(VALID_INDEX(i)); ASSERT(IS_VALID_COLOR(uColor)); u = g_pVectorDelta[i].iVector[uColor]; ASSERT(VALID_VECTOR(u)); ASSERT(u == g_VectorDelta[i + 128].iVector[uColor]); ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128])); return(u); } #define VALID_DELTA(x) \ (((x) == 0) || \ ((x) == +1) || ((x) == -1) || \ ((x) == +16) || ((x) == -16) || \ ((x) == +15) || ((x) == -15) || \ ((x) == +17) || ((x) == -17)) int DirectionBetweenSquaresWithIndex(int i) { int iDir; ASSERT(VALID_INDEX(i)); iDir = g_pVectorDelta[i].iDelta; ASSERT(iDir == g_VectorDelta[i + 128].iDelta); ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128])); ASSERT(VALID_DELTA(iDir)); ASSERT(iDir == -g_pVectorDelta[i].iNegDelta); return(iDir); } int DirectionBetweenSquaresFromTo(COOR from, COOR to) { int i = (int)from - (int)to; return DirectionBetweenSquaresWithIndex(i); } int NegativeDirectionBetweenSquaresWithIndex(int i) { int iDir; ASSERT(VALID_INDEX(i)); iDir = g_pVectorDelta[i].iNegDelta; ASSERT(iDir == g_VectorDelta[i + 128].iNegDelta); ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128])); ASSERT(VALID_DELTA(iDir)); ASSERT(iDir == -g_pVectorDelta[i].iDelta); return(iDir); } int DirectionBetweenSquares(COOR cFrom, COOR cTo) { int i = (int)cFrom - (int)cTo; return(DirectionBetweenSquaresWithIndex(i)); } FLAG IsSquareWhite(COOR c) { BITBOARD bb; FLAG f = IS_WHITE_SQUARE_COOR(c); ASSERT(IS_ON_BOARD(c)); ASSERT(f == g_fIsWhiteSquare[c]); bb = COOR_TO_BB(c); ASSERT(f == ((bb & BBWHITESQ) != 0)); ASSERT(f == ((bb & BBBLACKSQ) == 0)); return(f); } #endif void VerifyVectorDelta(void) { int iIndex; int iChecksum = 0; for (iIndex = 0; iIndex < 256; iIndex++) { ASSERT(VALID_VECTOR(g_VectorDelta[iIndex].iVector[BLACK])); ASSERT(VALID_VECTOR(g_VectorDelta[iIndex].iVector[WHITE])); ASSERT(VALID_DELTA(g_VectorDelta[iIndex].iDelta)); ASSERT(VALID_DELTA(g_VectorDelta[iIndex].iNegDelta)); ASSERT(-g_VectorDelta[iIndex].iDelta == g_VectorDelta[iIndex].iNegDelta); iChecksum += g_VectorDelta[iIndex].iVector[BLACK] * iIndex; iChecksum += g_VectorDelta[iIndex].iVector[WHITE] * iIndex; iChecksum += g_VectorDelta[iIndex].iDelta * iIndex; } if (iChecksum != 0xb1b58) { UtilPanic(DETECTED_INCORRECT_INITIALIZATION, NULL, "vector/delta", (void *)(size_t)iChecksum, (void *)(size_t)0xb1b58, __FILE__, __LINE__); } } void InitializeWhiteSquaresTable(void) { COOR c; FOREACH_SQUARE(c) { g_fIsWhiteSquare[c] = FALSE; if (!IS_ON_BOARD(c)) { continue; } g_fIsWhiteSquare[c] = IS_WHITE_SQUARE_COOR(c); } } void InitializeVectorDeltaTable(void) { COOR cStart; COOR cNew; COOR cRay; int iIndex; PIECE p; int iDir; ULONG u; static const BYTE _LOCATIONS[] = { D4, A5, A3, G3, C1, B5, H4, E5, E3, A6, C5, A5, A5, G5, A6, D3, D2, A5, E1, E1, A6, H4, B2, D1, D2, E5 }; static int iNumDirs[7] = { 0, 0, 8, 4, 4, 8, 8 }; static int iDelta[7][8] = { { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { -33, -31, -18, -14, +14, +18, +31, +33 }, { -17, -15, +15, +17, 0, 0, 0, 0 }, { -16, -1, +1, +16, 0, 0, 0, 0 }, { -17, -16, -15, -1, +1, +15, +16, +17 }, { -17, -16, -15, -1, +1, +15, +16, +17 } }; memset(g_VectorDelta, 0, sizeof(g_VectorDelta)); FOREACH_SQUARE(cStart) { if (!IS_ON_BOARD(cStart)) continue; for (u = 0; u < ARRAY_LENGTH(_LOCATIONS); u++) { if (cStart == _LOCATIONS[u]) { iIndex = 0; } } // // Do the pawn bits // iIndex = (int)cStart - ((int)cStart - 17) + 128; g_VectorDelta[iIndex].iVector[WHITE] |= (1 << PAWN); iIndex = (int)cStart - ((int)cStart - 15) + 128; g_VectorDelta[iIndex].iVector[WHITE] |= (1 << PAWN); iIndex = (int)cStart - ((int)cStart + 17) + 128; g_VectorDelta[iIndex].iVector[BLACK] |= (1 << PAWN); iIndex = (int)cStart - ((int)cStart + 15) + 128; g_VectorDelta[iIndex].iVector[BLACK] |= (1 << PAWN); // // Do the piece bits // for (p = KNIGHT; p <= KING; p++) { for (iDir = 0; iDir < iNumDirs[p]; iDir++) { cRay = cStart; cNew = cRay + iDelta[p][iDir]; while (IS_ON_BOARD(cNew)) { iIndex = (int)cStart - (int)cNew + 128; // // Fill in the vector // g_VectorDelta[iIndex].iVector[WHITE] |= (1 << p); g_VectorDelta[iIndex].iVector[BLACK] |= (1 << p); // // Fill in the delta // if (FILE(cStart) == FILE(cNew)) { if (cStart < cNew) { g_VectorDelta[iIndex].iDelta = 16; g_VectorDelta[iIndex].iNegDelta = -16; } else { g_VectorDelta[iIndex].iDelta = -16; g_VectorDelta[iIndex].iNegDelta = 16; } } else if (RANK(cStart) == RANK(cNew)) { if (cStart < cNew) { g_VectorDelta[iIndex].iDelta = 1; g_VectorDelta[iIndex].iNegDelta = -1; } else { g_VectorDelta[iIndex].iDelta = -1; g_VectorDelta[iIndex].iNegDelta = 1; } } else if ((cStart % 15) == (cNew % 15)) { if (cStart < cNew) { g_VectorDelta[iIndex].iDelta = +15; g_VectorDelta[iIndex].iNegDelta = -15; } else { g_VectorDelta[iIndex].iDelta = -15; g_VectorDelta[iIndex].iNegDelta = 15; } } else if ((cStart % 17) == (cNew % 17)) { if (cStart < cNew) { g_VectorDelta[iIndex].iDelta = +17; g_VectorDelta[iIndex].iNegDelta = -17; } else { g_VectorDelta[iIndex].iDelta = -17; g_VectorDelta[iIndex].iNegDelta = 17; } } cNew += iDelta[p][iDir]; if ((KING == p) || (KNIGHT == p)) { break; } } } } } (void)VerifyVectorDelta(); #ifdef OSX // // nasm under OSX/macho has a nasty bug that causes the addresses // of extern symbols to be screwed up. I only use two extern data // structs in the x86.asm code: the vector delta table and the // piece data table. My workaround to the nasm bug is to copy // these tables into a symbol in the asm module and access them // locally on OSX. // extern VECTOR_DELTA *g_NasmVectorDelta; extern PIECE_DATA *g_NasmPieceData; memcpy(&g_NasmVectorDelta, &g_VectorDelta, sizeof(g_VectorDelta)); memcpy(&g_NasmPieceData, &g_PieceData, sizeof(g_PieceData)); #endif } // // TODO: fix this to use attack counts also // void InitializeSwapTable(void) { ULONG GET_HIGH_BIT[32] = { 0, // 00000 = 0 1, // 00001 = 1 2, // 00010 = 2 2, // 00011 = 3 4, // 00100 = 4 4, // 00101 = 5 4, // 00110 = 6 4, // 00111 = 7 8, // 01000 = 8 8, // 01001 = 9 8, // 01010 = 10 8, // 01011 = 11 8, // 01100 = 12 8, // 01101 = 13 8, // 01110 = 14 8, // 01111 = 15 16, // 10000 = 16 16, // 10001 = 17 16, // 10010 = 18 16, // 10011 = 19 16, // 10100 = 20 16, // 10101 = 21 16, // 10110 = 22 16, // 10111 = 23 16, // 11000 = 24 16, // 11001 = 25 16, // 11010 = 26 16, // 11011 = 27 16, // 11100 = 28 16, // 11101 = 29 16, // 11110 = 30 16 // 11111 = 31 }; ULONG uOnMove; PIECE p; ULONG uAtStake; ULONG uBlack; ULONG uWhite; ULONG uOld; ULONG uGains[2]; ULONG uAttacks[2]; INT iDiff; for (p = 0; p <= WHITE_KING; p++) { if (p > 1) { for (uBlack = 0; uBlack < 32; uBlack++) { for (uWhite = 0; uWhite < 32; uWhite++) { uGains[BLACK] = uGains[WHITE] = 0; uAttacks[BLACK] = uBlack; uAttacks[WHITE] = uWhite; uAtStake = PIECE_VALUE(p); uOnMove = WHITE; if (GET_COLOR(p) == WHITE) { uOnMove = BLACK; } // // Ok, if the side on move has an attack, play it // and give them credit for some plunder. // while(uAttacks[uOnMove]) { uOld = uAtStake; uGains[uOnMove] += uAtStake; uAtStake = GET_HIGH_BIT[uAttacks[uOnMove]]; if (uAtStake == 16) { uAtStake = VALUE_PAWN; } else if (uAtStake == 8) { uAtStake = VALUE_BISHOP; } else if (uAtStake == 4) { uAtStake = VALUE_ROOK; } else if (uAtStake == 2) { uAtStake = VALUE_QUEEN; } else if (uAtStake == 1) { // // Don't let them move into check // if (uAttacks[FLIP(uOnMove)]) { uGains[uOnMove] -= uOld; uAtStake = 0; } break; } else { UtilPanic(SHOULD_NOT_GET_HERE, NULL, NULL, NULL, NULL, __FILE__, __LINE__); } uAttacks[uOnMove] &= ~GET_HIGH_BIT[uAttacks[uOnMove]]; uOnMove = FLIP(uOnMove); } // // The side on move doesn't have an attack... does // the side not on move have an attack? If so they // get a chance to assert some more control. // if (uAttacks[FLIP(uOnMove)]) { uGains[FLIP(uOnMove)] += 100; } if (uGains[BLACK] > uGains[WHITE]) { iDiff = uGains[BLACK] - uGains[WHITE]; iDiff /= 100; iDiff += (iDiff == 0); g_SwapTable[p][uWhite][uBlack] = MIN(+127, iDiff); g_SwapTable[p][uWhite][uBlack] *= -1; } else if (uGains[WHITE] > uGains[BLACK]) { iDiff = uGains[WHITE] - uGains[BLACK]; iDiff /= 100; iDiff += (iDiff == 0); g_SwapTable[p][uWhite][uBlack] = MIN(+127, iDiff); } else { g_SwapTable[p][uWhite][uBlack] = 0; } } } } else // no piece sitting there { for (uBlack = 0; uBlack < 32; uBlack++) { for (uWhite = 0; uWhite < 32; uWhite++) { if (uBlack > uWhite) { g_SwapTable[p][uWhite][uBlack] = -1; } else if (uWhite > uBlack) { g_SwapTable[p][uWhite][uBlack] = +1; } else { g_SwapTable[p][uWhite][uBlack] = 0; } } } } } } void InitializeDistanceTable(void) { COOR x, y; int i; #ifdef DEBUG int j; #endif for (x = 0; x < 128; x++) { if (!IS_ON_BOARD(x)) continue; for (y = 0; y < 128; y++) { if (!IS_ON_BOARD(y)) continue; i = (int)x - (int)y; i += 128; g_uDistance[i] = REAL_DISTANCE(x, y); ASSERT(g_uDistance[i] >= 0); ASSERT(g_uDistance[i] <= 7); } } #ifdef DEBUG for (x = 0; x < 128; x++) { if (!IS_ON_BOARD(x)) continue; for (y = 0; y < 128; y++) { if (!IS_ON_BOARD(y)) continue; i = (int)x - (int)y + 128; ASSERT(g_uDistance[i] == REAL_DISTANCE(x, y)); ASSERT(g_pDistance[(int)x - (int)y] == g_uDistance[i]); ASSERT(&(g_pDistance[(int)x - (int)y]) == &(g_uDistance[i])); j = (int)y - (int)x + 128; ASSERT(g_uDistance[j] == REAL_DISTANCE(x, y)); ASSERT(g_pDistance[(int)y - (int)x] == g_uDistance[j]); ASSERT(&(g_pDistance[(int)y - (int)x]) == &(g_uDistance[j])); } } #endif } // // Per-square, per-direction "ray to board edge" bitboards for the // rook, indexed [direction][c] with direction matching // g_RookRayDeltas below (N, S, E, W). Only entries for real board // squares (IS_ON_BOARD(c)) are ever populated/queried; off-board // indices are left zeroed and unused. Built once at startup by // InitializeRookRayTables() -- part of eval.c's occupancy-bitboard // PoC (_EvalRookOccupancyBB et al.), turning a per-call // walk-to-the-edge loop into an O(1) table lookup. // 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) /** Routine description: One-time startup init for g_RookRayToEdge -- see its comment. Parameters: void Return value: void **/ { ULONG uRank, uFile, uDir; 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++) { c = (uRank << 4) | uFile; for (uDir = 0; uDir < 4; uDir++) { for (cSquare = c + g_RookRayDeltas[uDir]; IS_ON_BOARD(cSquare); cSquare += g_RookRayDeltas[uDir]) { g_RookRayToEdge[uDir][c] |= COOR_TO_BB(cSquare); g_RookRayAll[c] |= COOR_TO_BB(cSquare); } } } } } // // Same idea as g_RookRayToEdge, for the bishop's 4 diagonal directions. // 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) /** Routine description: One-time startup init for g_BishopRayToEdge -- see its comment. Parameters: void Return value: void **/ { ULONG uRank, uFile, uDir; 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++) { c = (uRank << 4) | uFile; for (uDir = 0; uDir < 4; uDir++) { for (cSquare = c + g_BishopRayDeltas[uDir]; IS_ON_BOARD(cSquare); cSquare += g_BishopRayDeltas[uDir]) { g_BishopRayToEdge[uDir][c] |= COOR_TO_BB(cSquare); g_BishopRayAll[c] |= COOR_TO_BB(cSquare); } } } } } // A combined 8-ray queen table (rook's 4 directions + bishop's 4, // concatenated) was tried here and measured SLOWER than // _EvalQueenOccupancyBB's two-pass version reusing g_RookRayToEdge/ // g_BishopRayToEdge directly -- see that function's comment for why // (probable lost constant-folding on the orthogonal-ray flag). Removed // rather than left around unused. // // Per-square "all squares a knight on c can hop to" bitboard. Unlike // the rook/bishop ray tables, a knight has no blocking to account for // -- there's nothing "in between" a knight and its landing square -- // so this is the complete, final answer for a given square, not a // ray-to-edge that still needs an occupancy AND to find blockers. // Built once at startup by InitializeKnightAttackTables(). // BITBOARD g_KnightAttacksBB[128]; void InitializeKnightAttackTables(void) /** Routine description: One-time startup init for g_KnightAttacksBB -- see its comment. Parameters: void Return value: void **/ { ULONG uRank, uFile, uDir; COOR c, cSquare; memset(g_KnightAttacksBB, 0, sizeof(g_KnightAttacksBB)); for (uRank = 0; uRank < 8; uRank++) { for (uFile = 0; uFile < 8; uFile++) { c = (uRank << 4) | uFile; for (uDir = 0; g_iNDeltas[uDir] != 0; uDir++) { cSquare = c + g_iNDeltas[uDir]; if (IS_ON_BOARD(cSquare)) { g_KnightAttacksBB[c] |= COOR_TO_BB(cSquare); } } } } } // // 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 // 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); } } } } } // // 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]); } } }