stellar

commit 0f2c3c8054d402af63a5a8b597a1346606c243e1
parent 500ef277aef9ef459745b6d68e39cd092c0a4103
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 21 Sep 2022 00:54:11 +0200

Generate magic numbers for Rook and Bishop

Diffstat:
M
src/engine.c
 | 
112
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------

1 file changed, 101 insertions(+), 11 deletions(-)
diff --git a/src/engine.c b/src/engine.c
@@ -1,5 +1,4 @@
 #include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 #include <cii/assert.h>
@@ -72,11 +71,6 @@ U64 get_random_U64_number() {
   return n1 | (n2 << 16) | (n3 << 32) | (n4 << 48);
 }
 
-U64 generate_magic_number() {
-  return get_random_U64_number() & get_random_U64_number() &
-         get_random_U64_number();
-}
-
 // squares
 // clang-format off
 enum enumSquare {
@@ -174,7 +168,7 @@ void bitboard_print(U64 bitboard) {
 /* ATTACKS */
 
 // clang-format off
-const int bishop_relavant_bits[] = {
+const int bishop_relevant_bits[64] = {
   6, 5, 5, 5, 5, 5, 5, 6,
   5, 5, 5, 5, 5, 5, 5, 5,
   5, 5, 7, 7, 7, 7, 5, 5,
@@ -185,7 +179,32 @@ const int bishop_relavant_bits[] = {
   6, 5, 5, 5, 5, 5, 5, 6,
 };
 
-const int rook_relavant_bits[] = {
+const U64 bishop_magic_numbers[64] = {
+    C64(0x40040844404084),   C64(0x2004208a004208),   C64(0x10190041080202),
+    C64(0x108060845042010),  C64(0x581104180800210),  C64(0x2112080446200010),
+    C64(0x1080820820060210), C64(0x3c0808410220200),  C64(0x4050404440404),
+    C64(0x21001420088),      C64(0x24d0080801082102), C64(0x1020a0a020400),
+    C64(0x40308200402),      C64(0x4011002100800),    C64(0x401484104104005),
+    C64(0x801010402020200),  C64(0x400210c3880100),   C64(0x404022024108200),
+    C64(0x810018200204102),  C64(0x4002801a02003),    C64(0x85040820080400),
+    C64(0x810102c808880400), C64(0xe900410884800),    C64(0x8002020480840102),
+    C64(0x220200865090201),  C64(0x2010100a02021202), C64(0x152048408022401),
+    C64(0x20080002081110),   C64(0x4001001021004000), C64(0x800040400a011002),
+    C64(0xe4004081011002),   C64(0x1c004001012080),   C64(0x8004200962a00220),
+    C64(0x8422100208500202), C64(0x2000402200300c08), C64(0x8646020080080080),
+    C64(0x80020a0200100808), C64(0x2010004880111000), C64(0x623000a080011400),
+    C64(0x42008c0340209202), C64(0x209188240001000),  C64(0x400408a884001800),
+    C64(0x110400a6080400),   C64(0x1840060a44020800), C64(0x90080104000041),
+    C64(0x201011000808101),  C64(0x1a2208080504f080), C64(0x8012020600211212),
+    C64(0x500861011240000),  C64(0x180806108200800),  C64(0x4000020e01040044),
+    C64(0x300000261044000a), C64(0x802241102020002),  C64(0x20906061210001),
+    C64(0x5a84841004010310), C64(0x4010801011c04),    C64(0xa010109502200),
+    C64(0x4a02012000),       C64(0x500201010098b028), C64(0x8040002811040900),
+    C64(0x28000010020204),   C64(0x6000020202d0240),  C64(0x8918844842082200),
+    C64(0x4010011029020020),
+};
+
+const int rook_relevant_bits[64] = {
   12, 11, 11, 11, 11, 11, 11, 12,
   11, 10, 10, 10, 10, 10, 10, 11,
   11, 10, 10, 10, 10, 10, 10, 11,
@@ -195,6 +214,31 @@ const int rook_relavant_bits[] = {
   11, 10, 10, 10, 10, 10, 10, 11,
   12, 11, 11, 11, 11, 11, 11, 12,
 };
+
+const U64 rook_magic_numbers[64] = {
+    C64(0x8a80104000800020), C64(0x140002000100040),  C64(0x2801880a0017001),
+    C64(0x100081001000420),  C64(0x200020010080420),  C64(0x3001c0002010008),
+    C64(0x8480008002000100), C64(0x2080088004402900), C64(0x800098204000),
+    C64(0x2024401000200040), C64(0x100802000801000),  C64(0x120800800801000),
+    C64(0x208808088000400),  C64(0x2802200800400),    C64(0x2200800100020080),
+    C64(0x801000060821100),  C64(0x80044006422000),   C64(0x100808020004000),
+    C64(0x12108a0010204200), C64(0x140848010000802),  C64(0x481828014002800),
+    C64(0x8094004002004100), C64(0x4010040010010802), C64(0x20008806104),
+    C64(0x100400080208000),  C64(0x2040002120081000), C64(0x21200680100081),
+    C64(0x20100080080080),   C64(0x2000a00200410),    C64(0x20080800400),
+    C64(0x80088400100102),   C64(0x80004600042881),   C64(0x4040008040800020),
+    C64(0x440003000200801),  C64(0x4200011004500),    C64(0x188020010100100),
+    C64(0x14800401802800),   C64(0x2080040080800200), C64(0x124080204001001),
+    C64(0x200046502000484),  C64(0x480400080088020),  C64(0x1000422010034000),
+    C64(0x30200100110040),   C64(0x100021010009),     C64(0x2002080100110004),
+    C64(0x202008004008002),  C64(0x20020004010100),   C64(0x2048440040820001),
+    C64(0x101002200408200),  C64(0x40802000401080),   C64(0x4008142004410100),
+    C64(0x2060820c0120200),  C64(0x1001004080100),    C64(0x20c020080040080),
+    C64(0x2935610830022400), C64(0x44440041009200),   C64(0x280001040802101),
+    C64(0x2100190040002085), C64(0x80c0084100102001), C64(0x4024081001000421),
+    C64(0x20030a0244872),    C64(0x12001008414402),   C64(0x2006104900a0804),
+    C64(0x1004081002402),
+};
 // clang-format on
 
 // pawn attack table [side][square]
@@ -316,9 +360,55 @@ U64 set_occupancy(int index, int bits_in_mask, U64 attack_mask) {
   return occupancy;
 }
 
-int main(void) {
-  init_leapers_attacks();
+// magic numbers
+
+U64 generate_magic_number() {
+  return get_random_U64_number() & get_random_U64_number() &
+         get_random_U64_number();
+}
+
+U64 find_magic_number(int square, int relevant_bits, int bishop) {
+  U64 occupancies[4096], attacks[4096], used_attacks[4096];
+  U64 attack_mask =
+      bishop ? mask_bishop_attacks(square) : mask_rook_attacks(square);
+  int occupancy_indicies = 1 << relevant_bits;
+
+  for (int index = 0; index < occupancy_indicies; index++) {
+    occupancies[index] = set_occupancy(index, relevant_bits, attack_mask);
+    attacks[index] = bishop
+                         ? bishop_attacks_on_the_fly(square, occupancies[index])
+                         : rook_attacks_on_the_fly(square, occupancies[index]);
+  }
+
+  for (int random_count = 0; random_count < 100000000; random_count++) {
+    U64 magic_number = generate_magic_number();
+    if (bit_count((attack_mask * magic_number) & C64(0xFF00000000000000)) < 6)
+      continue;
+
+    memset(used_attacks, C64(0), sizeof(used_attacks));
+    int index, fail;
+
+    for (index = 0, fail = 0; !fail && index < occupancy_indicies; index++) {
+      int magic_index =
+          (int)((occupancies[index] * magic_number) >> (64 - relevant_bits));
+
+      if (used_attacks[magic_index] == C64(0))
+        used_attacks[magic_index] = attacks[index];
+      else if (used_attacks[magic_index] != attacks[index])
+        fail = 1;
+    }
+
+    if (!fail)
+      return magic_number;
+  }
 
-  bitboard_print(generate_magic_number());
+  printf("Magic number fail!\n");
+  return C64(0);
+}
+
+void init_all() { init_leapers_attacks(); }
+
+int main(void) {
+  init_all();
   return 0;
 }