Move magic random to RKISS
authorMarco Costalba <mcostalba@gmail.com>
Wed, 12 Feb 2014 13:47:36 +0000 (14:47 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Wed, 12 Feb 2014 13:47:36 +0000 (14:47 +0100)
When initializing the magic numbers used to
compute sliding attacks, we endless generate a
random and test it as a possible magic.

In the general case this takes a lot of iterations,
but here, insteaad of picking a casual random, we
rotate it a couple of times and generate a number that
we know has a good probability to be a magic candidate.

This is becuase the quantities by which we rotate the
number are known in advance to produce quickly a good
canidate.

The patch, inspired by DON, just moves the shuffle to RKISS
changing the boosters to take in account a left rotation
instead of a right rotation as in the original.

No functional change.

src/bitboard.cpp
src/rkiss.h

index 6784eff..b7eed92 100644 (file)
@@ -246,20 +246,6 @@ namespace {
   }
 
 
-  Bitboard pick_random(RKISS& rk, int booster) {
-
-    // Values s1 and s2 are used to rotate the candidate magic of a
-    // quantity known to be optimal to quickly find the magics.
-    int s1 = booster & 63, s2 = (booster >> 6) & 63;
-
-    Bitboard m = rk.rand<Bitboard>();
-    m = (m >> s1) | (m << (64 - s1));
-    m &= rk.rand<Bitboard>();
-    m = (m >> s2) | (m << (64 - s2));
-    return m & rk.rand<Bitboard>();
-  }
-
-
   // init_magics() computes all rook and bishop attacks at startup. Magic
   // bitboards are used to look up attacks of sliding pieces. As a reference see
   // chessprogramming.wikispaces.com/Magic+Bitboards. In particular, here we
@@ -268,8 +254,9 @@ namespace {
   void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[],
                    Bitboard masks[], unsigned shifts[], Square deltas[], Fn index) {
 
-    int MagicBoosters[][8] = { { 3191, 2184, 1310, 3618, 2091, 1308, 2452, 3996 },
-                               { 1059, 3608,  605, 3234, 3326,   38, 2029, 3043 } };
+    int MagicBoosters[][8] = { {  969, 1976, 2850,  542, 2069, 2852, 1708,  164 },
+                               { 3101,  552, 3555,  926,  834, 4122, 2131, 1117 } };
+
     RKISS rk;
     Bitboard occupancy[4096], reference[4096], edges, b;
     int i, size, booster;
@@ -309,7 +296,7 @@ namespace {
         // Find a magic for square 's' picking up an (almost) random number
         // until we find the one that passes the verification test.
         do {
-            do magics[s] = pick_random(rk, booster);
+            do magics[s] = rk.magic_rand<Bitboard>(booster);
             while (popcount<Max15>((magics[s] * masks[s]) >> 56) < 6);
 
             std::memset(attacks[s], 0, size * sizeof(Bitboard));
index b9b82ce..f3468db 100644 (file)
@@ -68,6 +68,14 @@ public:
   }
 
   template<typename T> T rand() { return T(rand64()); }
+
+  /// Special generator used to fast init magic numbers. Here the
+  /// trick is to rotate the randoms of a given quantity 's' known
+  /// to be optimal to quickly find a good magic candidate.
+  template<typename T> T magic_rand(int s) {
+    return rotate_L(rotate_L(rand<T>(), (s >> 0) & 0x3F) & rand<T>()
+                                      , (s >> 6) & 0x3F) & rand<T>();
+  }
 };
 
 #endif // #ifndef RKISS_H_INCLUDED