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

8 files changed, 600 insertions, 60 deletions

diff --git a/.gitignore b/.gitignore
index f6f7b43..97c5942 100644
--- a/.gitignore
+++ b/.gitignore
@@ -18,4 +18,6 @@ outgoing
 .kden4/
 chess.kden4
 *.kden4
+magic_finder
+magics.txt
 
diff --git a/CMakeLists.txt b/CMakeLists.txt
index b8a0602..e5cb17b 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -38,6 +38,11 @@ else()
     )
 endif()
 
+option(PERFT_DIVIDE "Enable perft divide output" OFF)
+if (PERFT_DIVIDE)
+  target_compile_definitions(${PROJECT_NAME} PRIVATE PERFT_DIVIDE)
+endif()
+
 if (NOT MSVC AND CMAKE_BUILD_TYPE STREQUAL "Debug")
   target_compile_options(${PROJECT_NAME} PRIVATE
         -fsanitize=address,undefined
diff --git a/magic_finder.c b/magic_finder.c
new file mode 100644
index 0000000..50c4279
--- /dev/null
+++ b/magic_finder.c
@@ -0,0 +1,220 @@
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+static int popcount(uint64_t b) { return __builtin_popcountll(b); }
+
+static uint64_t computeRookMask(int sq) {
+  uint64_t mask = 0;
+  int r = sq / 8, f = sq % 8;
+  for (int i = r + 1; i < 7; i++)
+    mask |= 1ULL << (i * 8 + f);
+  for (int i = r - 1; i > 0; i--)
+    mask |= 1ULL << (i * 8 + f);
+  for (int j = f + 1; j < 7; j++)
+    mask |= 1ULL << (r * 8 + j);
+  for (int j = f - 1; j > 0; j--)
+    mask |= 1ULL << (r * 8 + j);
+  return mask;
+}
+
+static uint64_t computeBishopMask(int sq) {
+  uint64_t mask = 0;
+  int r = sq / 8, f = sq % 8;
+  for (int i = r + 1, j = f + 1; i < 7 && j < 7; i++, j++)
+    mask |= 1ULL << (i * 8 + j);
+  for (int i = r + 1, j = f - 1; i < 7 && j > 0; i++, j--)
+    mask |= 1ULL << (i * 8 + j);
+  for (int i = r - 1, j = f + 1; i > 0 && j < 7; i--, j++)
+    mask |= 1ULL << (i * 8 + j);
+  for (int i = r - 1, j = f - 1; i > 0 && j > 0; i--, j--)
+    mask |= 1ULL << (i * 8 + j);
+  return mask;
+}
+
+static uint64_t computeRookAttacks(int sq, uint64_t occ) {
+  uint64_t att = 0;
+  int r = sq / 8, f = sq % 8;
+  for (int i = r + 1; i < 8; i++) {
+    att |= 1ULL << (i * 8 + f);
+    if (occ & (1ULL << (i * 8 + f)))
+      break;
+  }
+  for (int i = r - 1; i >= 0; i--) {
+    att |= 1ULL << (i * 8 + f);
+    if (occ & (1ULL << (i * 8 + f)))
+      break;
+  }
+  for (int j = f + 1; j < 8; j++) {
+    att |= 1ULL << (r * 8 + j);
+    if (occ & (1ULL << (r * 8 + j)))
+      break;
+  }
+  for (int j = f - 1; j >= 0; j--) {
+    att |= 1ULL << (r * 8 + j);
+    if (occ & (1ULL << (r * 8 + j)))
+      break;
+  }
+  return att;
+}
+
+static uint64_t computeBishopAttacks(int sq, uint64_t occ) {
+  uint64_t att = 0;
+  int r = sq / 8, f = sq % 8;
+  for (int i = r + 1, j = f + 1; i < 8 && j < 8; i++, j++) {
+    att |= 1ULL << (i * 8 + j);
+    if (occ & (1ULL << (i * 8 + j)))
+      break;
+  }
+  for (int i = r + 1, j = f - 1; i < 8 && j >= 0; i++, j--) {
+    att |= 1ULL << (i * 8 + j);
+    if (occ & (1ULL << (i * 8 + j)))
+      break;
+  }
+  for (int i = r - 1, j = f + 1; i >= 0 && j < 8; i--, j++) {
+    att |= 1ULL << (i * 8 + j);
+    if (occ & (1ULL << (i * 8 + j)))
+      break;
+  }
+  for (int i = r - 1, j = f - 1; i >= 0 && j >= 0; i--, j--) {
+    att |= 1ULL << (i * 8 + j);
+    if (occ & (1ULL << (i * 8 + j)))
+      break;
+  }
+  return att;
+}
+
+static uint64_t mapSquaresToMask(uint64_t index, uint64_t mask) {
+  uint64_t result = 0;
+  int bits = __builtin_popcountll(mask);
+  for (int i = 0; i < bits; i++) {
+    int sq = __builtin_ctzll(mask);
+    mask &= mask - 1;
+    if (index & (1ULL << i))
+      result |= (1ULL << sq);
+  }
+  return result;
+}
+
+static int findMagic(uint64_t mask, uint64_t (*attackFn)(int, uint64_t), int sq,
+                     int shift, uint64_t *outMagic) {
+  int nbits = popcount(mask);
+  uint64_t nocc = 1ULL << nbits;
+
+  uint64_t *occs = malloc(nocc * sizeof(uint64_t));
+  uint64_t *atts = malloc(nocc * sizeof(uint64_t));
+  for (uint64_t i = 0; i < nocc; i++) {
+    occs[i] = mapSquaresToMask(i, mask);
+    atts[i] = attackFn(sq, occs[i]);
+  }
+
+  uint64_t tableSize = 1ULL << (64 - shift);
+  uint64_t *table = malloc(tableSize * sizeof(uint64_t));
+  uint64_t *epoch = calloc(tableSize, sizeof(uint64_t));
+  uint64_t cnt = 0;
+
+  for (unsigned long long attempt = 0; attempt < 10000000000ULL; attempt++) {
+    uint64_t magic;
+    do {
+      magic =
+          ((uint64_t)rand() << 32 | rand()) & ((uint64_t)rand() << 32 | rand());
+    } while (popcount((mask * magic) & 0xFF00000000000000ULL) < 6);
+
+    cnt++;
+    int ok = 1;
+    for (uint64_t i = 0; i < nocc; i++) {
+      uint64_t idx = (occs[i] * magic) >> shift;
+      if (epoch[idx] < cnt) {
+        epoch[idx] = cnt;
+        table[idx] = atts[i];
+      } else if (table[idx] != atts[i]) {
+        ok = 0;
+        break;
+      }
+    }
+    if (ok) {
+      *outMagic = magic;
+      free(occs);
+      free(atts);
+      free(table);
+      free(epoch);
+      return 1;
+    }
+  }
+
+  free(occs);
+  free(atts);
+  free(table);
+  free(epoch);
+  return 0;
+}
+
+int main(int argc, char *argv[]) {
+  int shift = 52;
+  if (argc > 1) {
+    shift = atoi(argv[1]);
+    if (shift < 32 || shift > 63) {
+      fprintf(stderr, "Usage: %s [shift]  (32..63, default 52)\n", argv[0]);
+      return 1;
+    }
+  }
+  srand(time(NULL));
+
+  uint64_t rookMags[64], bishopMags[64];
+  uint64_t rookMasks[64], bishopMasks[64];
+
+  fprintf(stderr, "Finding per-square rook magics (shift %d, table size %llu)...\n",
+          shift, (unsigned long long)(1ULL << (64 - shift)));
+  for (int sq = 0; sq < 64; sq++) {
+    rookMasks[sq] = computeRookMask(sq);
+    if (!findMagic(rookMasks[sq], computeRookAttacks, sq, shift, &rookMags[sq])) {
+      fprintf(stderr, "FAILED to find rook magic for square %d\n", sq);
+      return 1;
+    }
+    fprintf(stderr, "  sq %2d: %d bits, magic 0x%016llx\n", sq,
+            popcount(rookMasks[sq]), (unsigned long long)rookMags[sq]);
+  }
+
+  fprintf(stderr, "\nFinding per-square bishop magics (shift %d)...\n", shift);
+  for (int sq = 0; sq < 64; sq++) {
+    bishopMasks[sq] = computeBishopMask(sq);
+    if (!findMagic(bishopMasks[sq], computeBishopAttacks, sq, shift,
+                   &bishopMags[sq])) {
+      fprintf(stderr, "FAILED to find bishop magic for square %d\n", sq);
+      return 1;
+    }
+    fprintf(stderr, "  sq %2d: %d bits, magic 0x%016llx\n", sq,
+            popcount(bishopMasks[sq]), (unsigned long long)bishopMags[sq]);
+  }
+
+  fprintf(stderr, "\nDone! Writing magics.txt\n");
+
+  FILE *f = fopen("magics.txt", "w");
+  if (!f) {
+    fprintf(stderr, "Cannot open magics.txt\n");
+    return 1;
+  }
+
+  fprintf(f, "// shift = %d\n", shift);
+  fprintf(f, "constexpr int MAGIC_SHIFT = %d;\n\n", shift);
+
+  fprintf(f, "constexpr std::array<uint64_t, 64> rookMagics = {\n");
+  for (int i = 0; i < 64; i++) {
+    fprintf(f, "    0x%016llxULL%c // %c%d\n", (unsigned long long)rookMags[i],
+            i < 63 ? ',' : ' ', 'a' + i % 8, i / 8 + 1);
+  }
+  fprintf(f, "};\n\n");
+
+  fprintf(f, "constexpr std::array<uint64_t, 64> bishopMagics = {\n");
+  for (int i = 0; i < 64; i++) {
+    fprintf(f, "    0x%016llxULL%c // %c%d\n",
+            (unsigned long long)bishopMags[i], i < 63 ? ',' : ' ', 'a' + i % 8,
+            i / 8 + 1);
+  }
+  fprintf(f, "};\n");
+
+  fclose(f);
+  return 0;
+}
diff --git a/src/main.cpp b/src/main.cpp
index c3945d3..98ff360 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -33,7 +33,12 @@ static void perft(int argc, char *argv[]) {
   auto start = std::chrono::steady_clock::now();
 
   Game game = initBoard(fen, nullptr);
-  uint64_t count = MoveGenTest(depth, &game);
+  uint64_t count = 0;
+#ifdef PERFT_DIVIDE
+  count = MoveGenTestDivide(depth, &game);
+#else
+  count = MoveGenTest(depth, &game);
+#endif
 
   auto end = std::chrono::steady_clock::now();
   auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start)
@@ -72,6 +77,7 @@ static void zobristCmd(int argc, char *argv[]) {
 
 int main(int argc, char *argv[]) {
   InitZobrist();
+  initMagicBitboards();
 
   if (argc >= 2 && std::string(argv[1]) == "perft") {
     perft(argc, argv);
diff --git a/src/misc.cpp b/src/misc.cpp
index e9073d4..a69054b 100644
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -1,6 +1,8 @@
 #include "misc.hpp"
+#include "board/board.hpp"
 #include "moves.hpp"
 #include <cstdint>
+#include <iostream>
 #include <string_view>
 #include <vector>
 
@@ -31,3 +33,44 @@ uint64_t MoveGenTest(uint32_t depth, Game *g) {
   }
   return positionCount;
 }
+
+uint64_t MoveGenTestDivide(uint32_t depth, Game *g) {
+  if (depth == 0) {
+    return 1;
+  }
+
+  uint64_t total = 0;
+
+  std::vector<uint16_t> moves = GetLegalMoves(g, ALL);
+
+  for (uint16_t move : moves) {
+    uint8_t from = getFromValueFromMove(move);
+    uint8_t to = getToValueFromMove(move);
+    Position fromPos = IndexToPosition(from);
+    Position toPos = IndexToPosition(to);
+
+    Undo undo = MakeMove(move, g);
+
+    uint64_t count = MoveGenTest(depth - 1, g);
+
+    UndoMove(undo, g);
+
+    char fromFile = static_cast<char>('a' + fromPos.file);
+    char toFile = static_cast<char>('a' + toPos.file);
+    std::cout << fromFile << (fromPos.rank + 1) << toFile << (toPos.rank + 1);
+    PieceType promo = getPromotionTypeFromMove(move);
+    if (promo == QUEEN)
+      std::cout << 'q';
+    else if (promo == ROOK)
+      std::cout << 'r';
+    else if (promo == KNIGHT)
+      std::cout << 'n';
+    else if (promo == BISHOP)
+      std::cout << 'b';
+    std::cout << ": " << count << "\n";
+    total += count;
+  }
+
+  std::cout << "\nTotal: " << total << "\n";
+  return total;
+}
diff --git a/src/misc.hpp b/src/misc.hpp
index b0ebe9a..a076dcb 100644
--- a/src/misc.hpp
+++ b/src/misc.hpp
@@ -8,5 +8,6 @@
 std::string_view engine_info();
 
 uint64_t MoveGenTest(uint32_t depth, Game *g);
+uint64_t MoveGenTestDivide(uint32_t depth, Game *g);
 
 #endif /* SRC_MICS_H_ */
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);
diff --git a/src/moves.hpp b/src/moves.hpp
index e0ed427..47e41c0 100644
--- a/src/moves.hpp
+++ b/src/moves.hpp
@@ -10,12 +10,16 @@ enum move_generate_options : std::uint8_t {
   CAPTUARES_ONLY,
   NON_CAPTUARES_ONLY,
 };
-
+void initMagicBitboards();
 std::vector<uint16_t> GetLegalMoves(Game *g,
                                     const move_generate_options &options);
 std::vector<uint16_t> GetPseudoLegalMoves(const Game &g,
                                           const move_generate_options &options);
-Position IndexToPosition(int i);
+constexpr Position IndexToPosition(int i) {
+  auto rank = static_cast<uint8_t>(i / 8);
+  auto file = static_cast<uint8_t>(i % 8);
+  return {.rank = rank, .file = file};
+}
 bool IsSquareAttacked(const Game &g, Position square, bool byColor);
 GameState GetNewGameState(Game *g);