From a4024e15a807e26ddad04d6804742fab0d6c8c96 Mon Sep 17 00:00:00 2001 From: Adam Date: Tue, 18 Aug 2026 20:55:21 +0200 Subject: perf(board): implementing magic bitboards for faster move generation --- src/moves.cpp | 373 +++++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 316 insertions(+), 57 deletions(-) (limited to 'src/moves.cpp') diff --git a/src/moves.cpp b/src/moves.cpp index 0b8230f..44e78b2 100644 --- a/src/moves.cpp +++ b/src/moves.cpp @@ -13,6 +13,57 @@ static void Assert_message() { std::cout << "Internal error: run in debug to see assert\n"; } +constexpr int MAGIC_SHIFT = 52; + +constexpr size_t MAGIC_INDEX_COUNT = 1ULL << (64 - MAGIC_SHIFT); + +constexpr std::array rookMagics = { + 0x2080002240041082ULL, 0x0804084001208018ULL, 0x6220040220400800ULL, + 0x1280081200805410ULL, 0x240040080e021c00ULL, 0x0200045108821008ULL, + 0x0200051618004284ULL, 0x4c80090001a04680ULL, 0x0414800123400034ULL, + 0x005818403a020148ULL, 0x0320480c41902928ULL, 0x5a1010122010a004ULL, + 0x61841005004a4428ULL, 0x302018042000830bULL, 0x101db80a030ec294ULL, + 0x142620004a002004ULL, 0x006142d0012822b0ULL, 0x14084044009c4200ULL, + 0x2289030009422003ULL, 0x1c410100091450c1ULL, 0x00b2860010200200ULL, + 0x4cc21212096c2020ULL, 0x0241400900948022ULL, 0x1080290804022142ULL, + 0x3a620312001481c0ULL, 0x00c0003008649060ULL, 0x108920b010020020ULL, + 0x2940040204002212ULL, 0x071aa860080008a0ULL, 0x0003200401030011ULL, + 0x3011662100680410ULL, 0x210c008440010028ULL, 0x1402104340042320ULL, + 0x001ee08a42280420ULL, 0x28008a1900420040ULL, 0x05048a0020c00241ULL, + 0x0100202928036808ULL, 0x4000c0100201c6c0ULL, 0x43c2148c00480500ULL, + 0x4084620200540320ULL, 0x2201080402080084ULL, 0x010050006c280880ULL, + 0x0070080104040294ULL, 0x4402866c3a066c04ULL, 0x44900d4842200800ULL, + 0x20830a4014001452ULL, 0x2884200042018410ULL, 0x0300009a01a04002ULL, + 0x0008028212400410ULL, 0x2522084a008b6040ULL, 0x4140a00023001a18ULL, + 0x013c9000200400c4ULL, 0x398007a004c96418ULL, 0x00b5090608883210ULL, + 0x120024820025001bULL, 0x204d008b2082b0c0ULL, 0x02e9902241008003ULL, + 0x00026040106820c2ULL, 0x2820ac4612013a16ULL, 0x2389661e00401852ULL, + 0x4004881014016026ULL, 0x1983903822140e81ULL, 0x095a0296420f0c04ULL, + 0x000041440700806aULL}; + +constexpr std::array bishopMagics = { + 0x02af09244210b482ULL, 0x2c04718255220041ULL, 0x61252af82e518e4cULL, + 0x0401f401008090f1ULL, 0x2040141002801001ULL, 0x2080150800434900ULL, + 0x09c3104103a08d90ULL, 0x40a1800100522044ULL, 0x228420020508a01cULL, + 0x006084634c40080aULL, 0x19210511294a3120ULL, 0x66049cb640121220ULL, + 0x0050845041020000ULL, 0x000311406280e9aaULL, 0x4104011844905120ULL, + 0x64404044091b5e40ULL, 0x0849a9c36082240aULL, 0x7115188e4091a24aULL, + 0x2030b14c4620627cULL, 0x1205504402000230ULL, 0x04e28e2b03040021ULL, + 0x1010c00464206049ULL, 0x0048d442011000c8ULL, 0x481804c51a134008ULL, + 0x500019c401343d09ULL, 0x42420025480d5148ULL, 0x20000440020174c8ULL, + 0x100c002040840300ULL, 0x0002902012910086ULL, 0x1195d43058c01038ULL, + 0x0005082018222c56ULL, 0x2a1d416647108240ULL, 0x011401002b094230ULL, + 0x3002220520042c00ULL, 0x02308a2010306160ULL, 0x6040229800045200ULL, + 0x0940805040040490ULL, 0x00ba44420380021aULL, 0x0004139001480240ULL, + 0x400048a000808c10ULL, 0x22cc8b0c10d805b1ULL, 0x1246820825600419ULL, + 0x085645080c029540ULL, 0x2000240909910951ULL, 0x02e0158514006f10ULL, + 0x0008801a00a88886ULL, 0x7601001029220420ULL, 0x0a480e024049b010ULL, + 0x200a88272430020cULL, 0x000008140a511242ULL, 0x4a8831ac00328250ULL, + 0x1128802901011444ULL, 0x0202110160092844ULL, 0x520d8052300a4090ULL, + 0x1810404c0230cc15ULL, 0x004202000ec40e41ULL, 0x00b0e81a20174085ULL, + 0x400240c023021254ULL, 0x2112090c601a0207ULL, 0x09f4c5011001af13ULL, + 0x4000081508448480ULL, 0x0040d43528062200ULL, 0x04820090591d8083ULL, + 0x000d06b4400d80e0ULL}; constexpr std::array computeKnightAttacks() { std::array attacks{}; @@ -63,6 +114,7 @@ constexpr std::array, 2> computePawnAttacks() { } return attacks; } + constexpr std::array computeKingAttacks() { std::array attacks{}; constexpr std::array king_offsets{-1, 1, 8, -8, -9, 9, -7, 7}; @@ -85,6 +137,222 @@ constexpr std::array computeKingAttacks() { return attacks; } +constexpr uint64_t computeRookMaskFromSquare(uint8_t from) { + uint64_t mask = 0; + + if (from >= 64) { + assert(false && "invalid square"); + Assert_message(); + exit(1); + } + + constexpr std::array ROOK_MOVES{-1, 1, 8, -8}; + + for (int offset : ROOK_MOVES) { + int pos = from; + while (true) { + pos += offset; + int doublePos = pos + offset; + + if (doublePos >= 64 || doublePos < 0) { + break; + } + + int oldFile = (pos - offset) % 8; + int newFile = doublePos % 8; + + if (offset == -1 || offset == 1) { + if (newFile - oldFile != 2 && newFile - oldFile != -2) { + break; + } + } + + mask |= (1ULL << pos); + } + } + return mask; +}; +constexpr uint64_t computeBishopMaskFromSquare(uint8_t from) { + uint64_t mask = 0; + + if (from >= 64) { + assert(false && "invalid square"); + Assert_message(); + exit(1); + } + + constexpr std::array BISHOP_MOVES{-9, 9, -7, 7}; + + for (int offset : BISHOP_MOVES) { + int pos = from; + while (true) { + pos += offset; + int doublePos = pos + offset; + + if (doublePos >= 64 || doublePos < 0) { + break; + } + + int oldFile = (pos - offset) % 8; + int newFile = doublePos % 8; + + if (newFile - oldFile != 2 && newFile - oldFile != -2) { + break; + } + + int curFile = pos % 8; + if (newFile - curFile != 1 && newFile - curFile != -1) { + break; + } + mask |= (1ULL << pos); + } + } + return mask; +}; +constexpr uint64_t mapSquaresToMask(uint index, uint64_t mask) { + uint64_t result = 0ULL; + int bitsInMask = __builtin_popcountll(mask); + + for (int i = 0; i < bitsInMask; i++) { + int square = __builtin_ctzll(mask); + mask &= mask - 1; + + if (index & (1 << i)) { + result |= (1ULL << square); + } + } + + return result; +} + +constexpr std::array computeRookMask() { + std::array masks; + for (uint8_t i = 0; i < 64; i++) { + masks[i] = computeRookMaskFromSquare(i); + }; + return masks; +} +constexpr std::array computeBishopMask() { + std::array masks; + for (uint8_t i = 0; i < 64; i++) { + masks[i] = computeBishopMaskFromSquare(i); + }; + return masks; +} +constexpr std::array ROOK_MASKS = computeRookMask(); +constexpr std::array BISHOP_MASKS = computeBishopMask(); +uint64_t computeRookAttacksFromSquare(uint8_t square, uint64_t blockers) { + uint64_t attacks = 0; + constexpr std::array directions{-1, 1, 8, -8}; + + for (int dir : directions) { + int pos = square; + while (true) { + int next = pos + dir; + if (next < 0 || next >= 64) { + break; + } + int nextFile = next % 8; + int curFile = pos % 8; + if ((dir == -1 || dir == 1) && + (nextFile - curFile != 1 && nextFile - curFile != -1)) { + break; + } + attacks |= (1ULL << next); + if (blockers & (1ULL << next)) { + break; // blocked + } + pos = next; + } + } + return attacks; +} +uint64_t computeBishopAttacksFromSquare(uint8_t square, uint64_t blockers) { + uint64_t attacks = 0; + constexpr std::array directions{-9, 9, -7, 7}; + + for (int dir : directions) { + int pos = square; + while (true) { + int next = pos + dir; + if (next < 0 || next >= 64) { + break; + } + int nextFile = next % 8; + int curFile = pos % 8; + if (nextFile - curFile != 1 && nextFile - curFile != -1) { + break; + } + attacks |= (1ULL << next); + if ((blockers & (1ULL << next)) > 0) { + break; // blocked + } + pos = next; + } + } + return attacks; +} +constexpr uint64_t turnMaskAndSquareToSmallerUsingMagic(uint64_t blockers, + uint64_t magic) { + return (blockers * magic) >> MAGIC_SHIFT; +} + +constexpr uint +generateAllBlocker(uint64_t mask, + std::array &blockers) { + int squareCount = __builtin_popcountll(mask); + uint possibleOptions = (1 << squareCount); + + for (uint i = 0; i < possibleOptions; i++) { + uint64_t blocker = mapSquaresToMask(i, mask); + blockers[i] = blocker; + }; + + return possibleOptions; +}; +constexpr std::array, 64> +computeRookAttacks() { + std::array, 64> ROOK_ATTACKS; + for (uint8_t i = 0; i < 64; i++) { + uint64_t mask = ROOK_MASKS[static_cast(i)]; + std::array blockers; + uint blockerCount = generateAllBlocker(mask, blockers); + for (uint i2 = 0; i2 < blockerCount; i2++) { + uint64_t magic = turnMaskAndSquareToSmallerUsingMagic( + blockers[static_cast(i2)], + rookMagics[static_cast(i)]); + ROOK_ATTACKS[static_cast(i)][magic] = + computeRookAttacksFromSquare(i, blockers[i2]); + }; + } + return ROOK_ATTACKS; +} +constexpr std::array, 64> +computeBishopAttacks() { + std::array, 64> BISHOP_ATTACKS; + for (uint8_t i = 0; i < 64; i++) { + uint64_t mask = BISHOP_MASKS[static_cast(i)]; + std::array blockers; + uint blockerCount = generateAllBlocker(mask, blockers); + for (uint i2 = 0; i2 < blockerCount; i2++) { + uint64_t magic = turnMaskAndSquareToSmallerUsingMagic( + blockers[static_cast(i2)], + bishopMagics[static_cast(i)]); + BISHOP_ATTACKS[static_cast(i)][magic] = + computeBishopAttacksFromSquare(i, blockers[i2]); + }; + } + return BISHOP_ATTACKS; +} + +std::array, 64> rookAttacks; +std::array, 64> bishopAttacks; + +void initMagicBitboards() { + rookAttacks = computeRookAttacks(); + bishopAttacks = computeBishopAttacks(); +}; + constexpr std::array KNIGHT_ATTACKS = computeKnightAttacks(); constexpr std::array, 2> PAWN_ATTACKS = computePawnAttacks(); @@ -116,7 +384,51 @@ static void GenerateKnightMoves(const uint8_t &from, const Game &g, moves.push_back(CreateMove(from, next)); } }; +static void GenerateRookMoves(const uint8_t &from, const Game &g, + std::vector &moves, + const move_generate_options &options) { + uint64_t mask = ROOK_MASKS[from] & g.PieceBitboard; + uint64_t index = turnMaskAndSquareToSmallerUsingMagic(mask, rookMagics[from]); + uint64_t rook_attacks = rookAttacks[from][index]; + rook_attacks &= ~(g.turn ? g.WhitePieceBitboard : g.BlackPieceBitboard); + while (rook_attacks != 0) { + auto next = static_cast(__builtin_ctzll(rook_attacks)); + rook_attacks &= rook_attacks - 1; + + bool isCaptuare = (g.PieceBitboard & (1ULL << next)) > 0; + if (options == NON_CAPTUARES_ONLY && isCaptuare) { + continue; + } + if (options == CAPTUARES_ONLY && !isCaptuare) { + continue; + } + moves.push_back(CreateMove(from, next)); + } +}; +static void GenerateBishopMoves(const uint8_t &from, const Game &g, + std::vector &moves, + const move_generate_options &options) { + uint64_t mask = BISHOP_MASKS[from] & g.PieceBitboard; + uint64_t index = + turnMaskAndSquareToSmallerUsingMagic(mask, bishopMagics[from]); + uint64_t rook_attacks = bishopAttacks[from][index]; + + rook_attacks &= ~(g.turn ? g.WhitePieceBitboard : g.BlackPieceBitboard); + while (rook_attacks != 0) { + auto next = static_cast(__builtin_ctzll(rook_attacks)); + rook_attacks &= rook_attacks - 1; + + bool isCaptuare = (g.PieceBitboard & (1ULL << next)) > 0; + if (options == NON_CAPTUARES_ONLY && isCaptuare) { + continue; + } + if (options == CAPTUARES_ONLY && !isCaptuare) { + continue; + } + moves.push_back(CreateMove(from, next)); + } +}; static void GeneratePawnMoves(const uint8_t &from, const Game &g, std::vector &moves, const move_generate_options &options) { @@ -355,56 +667,6 @@ GameState GetNewGameState(Game *g) { return g->state; } -Position IndexToPosition(int i) { - auto rank = static_cast(i / 8); // 0-7 - auto file = static_cast(i % 8); // 0-7 - return {.rank = rank, .file = file}; -} - -static void GenerateSlidingMoves(const uint8_t &from, const Game &g, - const std::array &directions, - std::vector &moves, - const move_generate_options options) { - for (uint i = 0; i < directions.size(); i++) { - int direction = directions[i]; - - int i2 = from; - while (true) { - i2 += direction; - int oldFile = (i2 - direction) % 8; - int newFile = i2 % 8; - - if (direction == 7 || direction == -7 || direction == 9 || - direction == -9) { - if (std::abs(newFile - oldFile) != 1) { - break; - } - } - if (i2 >= 64 || i2 < 0) { - break; - } - - if ((direction == 1 || direction == -1) && - (i2 / 8 != (i2 - direction) / 8)) { - break; - } - if (g.pieces[i2].color == g.turn && g.pieces[i2].type != NONEPIECE) { - break; - } - if (options == CAPTUARES_ONLY && g.pieces[i2].type == NONEPIECE) { - continue; - } - if (options == NON_CAPTUARES_ONLY && g.pieces[i2].type != NONEPIECE) { - break; - } - moves.push_back( - CreateMove(static_cast(from), static_cast(i2))); - if (g.pieces[i2].color != g.turn && g.pieces[i2].type != NONEPIECE) { - break; - } - } - }; -}; static void GenerateCastlingMoves(const uint8_t &from, const Game &g, std::vector &moves) { Piece piece = g.pieces[from]; @@ -471,9 +733,6 @@ GetPseudoLegalMoves(const Game &g, const move_generate_options &options) { std::vector moves; moves.reserve(40); - constexpr std::array ROOK_MOVES{-1, 1, 8, -8}; - constexpr std::array BISHOP_MOVES{-9, 9, -7, 7}; - uint64_t piece_bitboard = g.PieceBitboard; while (piece_bitboard != 0) { const auto i = static_cast(__builtin_ctzll(piece_bitboard)); @@ -493,14 +752,14 @@ GetPseudoLegalMoves(const Game &g, const move_generate_options &options) { GenerateKnightMoves(i, g, moves, options); } if (piece.type == BISHOP) { - GenerateSlidingMoves(i, g, BISHOP_MOVES, moves, options); + GenerateBishopMoves(i, g, moves, options); } if (piece.type == ROOK) { - GenerateSlidingMoves(i, g, ROOK_MOVES, moves, options); + GenerateRookMoves(i, g, moves, options); } if (piece.type == QUEEN) { - GenerateSlidingMoves(i, g, ROOK_MOVES, moves, options); - GenerateSlidingMoves(i, g, BISHOP_MOVES, moves, options); + GenerateRookMoves(i, g, moves, options); + GenerateBishopMoves(i, g, moves, options); } if (piece.type == KING) { GenerateKingMoves(g, i, moves, options); -- cgit v1.2.3