perf(board): implementing magic bitboards for faster move generation

1 files changed, 316 insertions, 57 deletions

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<uint64_t, 64> 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<uint64_t, 64> 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<std::uint64_t, 64> computeKnightAttacks() {
   std::array<std::uint64_t, 64> attacks{};
@@ -63,6 +114,7 @@ constexpr std::array<std::array<std::uint64_t, 64>, 2> computePawnAttacks() {
   }
   return attacks;
 }
+
 constexpr std::array<std::uint64_t, 64> computeKingAttacks() {
   std::array<std::uint64_t, 64> attacks{};
   constexpr std::array<int, 8> king_offsets{-1, 1, 8, -8, -9, 9, -7, 7};
@@ -85,6 +137,222 @@ constexpr std::array<std::uint64_t, 64> 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<int, 4> 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<int, 4> 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<uint64_t, 64> computeRookMask() {
+  std::array<uint64_t, 64> masks;
+  for (uint8_t i = 0; i < 64; i++) {
+    masks[i] = computeRookMaskFromSquare(i);
+  };
+  return masks;
+}
+constexpr std::array<uint64_t, 64> computeBishopMask() {
+  std::array<uint64_t, 64> masks;
+  for (uint8_t i = 0; i < 64; i++) {
+    masks[i] = computeBishopMaskFromSquare(i);
+  };
+  return masks;
+}
+constexpr std::array<std::uint64_t, 64> ROOK_MASKS = computeRookMask();
+constexpr std::array<std::uint64_t, 64> BISHOP_MASKS = computeBishopMask();
+uint64_t computeRookAttacksFromSquare(uint8_t square, uint64_t blockers) {
+  uint64_t attacks = 0;
+  constexpr std::array<int, 4> 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<int, 4> 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<uint64_t, MAGIC_INDEX_COUNT> &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<std::array<uint64_t, MAGIC_INDEX_COUNT>, 64>
+computeRookAttacks() {
+  std::array<std::array<uint64_t, MAGIC_INDEX_COUNT>, 64> ROOK_ATTACKS;
+  for (uint8_t i = 0; i < 64; i++) {
+    uint64_t mask = ROOK_MASKS[static_cast<size_t>(i)];
+    std::array<uint64_t, MAGIC_INDEX_COUNT> blockers;
+    uint blockerCount = generateAllBlocker(mask, blockers);
+    for (uint i2 = 0; i2 < blockerCount; i2++) {
+      uint64_t magic = turnMaskAndSquareToSmallerUsingMagic(
+          blockers[static_cast<size_t>(i2)],
+          rookMagics[static_cast<size_t>(i)]);
+      ROOK_ATTACKS[static_cast<size_t>(i)][magic] =
+          computeRookAttacksFromSquare(i, blockers[i2]);
+    };
+  }
+  return ROOK_ATTACKS;
+}
+constexpr std::array<std::array<uint64_t, MAGIC_INDEX_COUNT>, 64>
+computeBishopAttacks() {
+  std::array<std::array<uint64_t, MAGIC_INDEX_COUNT>, 64> BISHOP_ATTACKS;
+  for (uint8_t i = 0; i < 64; i++) {
+    uint64_t mask = BISHOP_MASKS[static_cast<size_t>(i)];
+    std::array<uint64_t, MAGIC_INDEX_COUNT> blockers;
+    uint blockerCount = generateAllBlocker(mask, blockers);
+    for (uint i2 = 0; i2 < blockerCount; i2++) {
+      uint64_t magic = turnMaskAndSquareToSmallerUsingMagic(
+          blockers[static_cast<size_t>(i2)],
+          bishopMagics[static_cast<size_t>(i)]);
+      BISHOP_ATTACKS[static_cast<size_t>(i)][magic] =
+          computeBishopAttacksFromSquare(i, blockers[i2]);
+    };
+  }
+  return BISHOP_ATTACKS;
+}
+
+std::array<std::array<uint64_t, MAGIC_INDEX_COUNT>, 64> rookAttacks;
+std::array<std::array<uint64_t, MAGIC_INDEX_COUNT>, 64> bishopAttacks;
+
+void initMagicBitboards() {
+  rookAttacks = computeRookAttacks();
+  bishopAttacks = computeBishopAttacks();
+};
+
 constexpr std::array<std::uint64_t, 64> KNIGHT_ATTACKS = computeKnightAttacks();
 constexpr std::array<std::array<std::uint64_t, 64>, 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<uint16_t> &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<uint8_t>(__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<uint16_t> &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<uint8_t>(__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<uint16_t> &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<uint8_t>(i / 8); // 0-7
-  auto file = static_cast<uint8_t>(i % 8); // 0-7
-  return {.rank = rank, .file = file};
-}
-
-static void GenerateSlidingMoves(const uint8_t &from, const Game &g,
-                                 const std::array<int, 4> &directions,
-                                 std::vector<uint16_t> &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<uint8_t>(from), static_cast<uint8_t>(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<uint16_t> &moves) {
   Piece piece = g.pieces[from];
@@ -471,9 +733,6 @@ GetPseudoLegalMoves(const Game &g, const move_generate_options &options) {
   std::vector<uint16_t> moves;
   moves.reserve(40);
 
-  constexpr std::array<int, 4> ROOK_MOVES{-1, 1, 8, -8};
-  constexpr std::array<int, 4> BISHOP_MOVES{-9, 9, -7, 7};
-
   uint64_t piece_bitboard = g.PieceBitboard;
   while (piece_bitboard != 0) {
     const auto i = static_cast<uint8_t>(__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);