Simpler PRNG and faster magics search

This patch replaces RKISS by a simpler and faster PRNG, xorshift64* proposed
by S. Vigna (2014). It is extremely simple, has a large enough period for
Stockfish's needs (2^64), requires no warming-up (allowing such code to be
removed), and offers slightly better randomness than MT19937.

Paper: http://xorshift.di.unimi.it/
Reference source code (public domain):
http://xorshift.di.unimi.it/xorshift64star.c

The patch also simplifies how init_magics() searches for magics:

- Old logic: seed the PRNG always with the same seed,
  then use optimized bit rotations to tailor the RNG sequence per rank.

- New logic: seed the PRNG with an optimized seed per rank.

This has two advantages:
1. Less code and less computation to perform during magics search (not ROTL).
2. More choices for random sequence tuning. The old logic only let us choose
from 4096 bit rotation pairs. With the new one, we can look for the best seeds
among 2^64 values. Indeed, the set of seeds[][] provided in the patch reduces
the effort needed to find the magics:

64-bit SF:
Old logic -> 5,783,789 rand64() calls needed to find the magics
New logic -> 4,420,086 calls

32-bit SF:
Old logic -> 2,175,518 calls
New logic -> 1,895,955 calls

In the 64-bit case, init_magics() take 25 ms less to complete (Intel Core i5).

Finally, when playing with strength handicap, non-determinism is achieved
by setting the seed of the static RNG only once. Afterwards, there is no need
to skip output values.

The bench only changes because the Zobrist keys are now different (since they
are random numbers straight out of the PRNG).

The RNG seed has been carefully chosen so that the
resulting Zobrist keys are particularly well-behaved:

1. All triplets of XORed keys are unique, implying that it
   would take at least 7 keys to find a 64-bit collision
   (test suggested by ceebo)

2. All pairs of XORed keys are unique modulo 2^32

3. The cardinality of { (key1 ^ key2) >> 48 } is as close
   as possible to the maximum (65536)

Point 2 aims at ensuring a good distribution among the bits
that determine an TT entry's cluster, likewise point 3
among the bits that form the TT entry's key16 inside a
cluster.

Details:

     Bitset   card(key1^key2)
     ------   ---------------
RKISS
     key16     64894   = 99.020% of theoretical maximum
     low18    180117   = 99.293%
     low32    305362   = 99.997%

Xorshift64*, old seed
     key16     64918   = 99.057%
     low18    179994   = 99.225%
     low32    305350   = 99.993%

Xorshift64*, new seed
     key16     65027   = 99.223%
     low18    181118   = 99.845%
     low32    305371   = 100.000%

Bench: 9324905

Resolves #148

diff --git a/src/bitboard.cpp b/src/bitboard.cpp
index 2a7ef100b5bd036ea5bf966ba44298bf3c9810cf..dbaeb701cff9e6e29fc732895a71fda4408bc99e 100644 (file)
--- a/src/bitboard.cpp
+++ b/src/bitboard.cpp
@@ -22,7 +22,7 @@
 
 #include "bitboard.h"
 #include "bitcount.h"
 
 #include "bitboard.h"
 #include "bitcount.h"

-#include "rkiss.h"
+#include "misc.h"

 
 Bitboard RookMasks[SQUARE_NB];
 Bitboard RookMagics[SQUARE_NB];
 
 Bitboard RookMasks[SQUARE_NB];
 Bitboard RookMagics[SQUARE_NB];


@@ -250,11 +250,10 @@ namespace {
   void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[],
                    Bitboard masks[], unsigned shifts[], Square deltas[], Fn index) {
 
   void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[],
                    Bitboard masks[], unsigned shifts[], Square deltas[], Fn index) {
 

-    int MagicBoosters[][RANK_NB] = { {  969, 1976, 2850,  542, 2069, 2852, 1708,  164 },
-                                     { 3101,  552, 3555,  926,  834,   26, 2131, 1117 } };
-    RKISS rk;
+    int seeds[][RANK_NB] = { { 8977, 44560, 54343, 38998,  5731, 95205, 104912, 17020 },
+                             {  728, 10316, 55013, 32803, 12281, 15100,  16645,   255 } };

     Bitboard occupancy[4096], reference[4096], edges, b;
     Bitboard occupancy[4096], reference[4096], edges, b;

-    int i, size, booster;
+    int i, size;

 
     // attacks[s] is a pointer to the beginning of the attacks table for square 's'
     attacks[SQ_A1] = table;
 
     // attacks[s] is a pointer to the beginning of the attacks table for square 's'
     attacks[SQ_A1] = table;


@@ -294,13 +293,13 @@ namespace {
         if (HasPext)
             continue;
 
         if (HasPext)
             continue;
 

-        booster = MagicBoosters[Is64Bit][rank_of(s)];
+        PRNG rng(seeds[Is64Bit][rank_of(s)]);

 
         // Find a magic for square 's' picking up an (almost) random number
         // until we find the one that passes the verification test.
         do {
             do
 
         // 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] = rk.magic_rand<Bitboard>(booster);
+                magics[s] = rng.sparse_rand<Bitboard>();

             while (popcount<Max15>((magics[s] * masks[s]) >> 56) < 6);
 
             std::memset(attacks[s], 0, size * sizeof(Bitboard));
             while (popcount<Max15>((magics[s] * masks[s]) >> 56) < 6);
 
             std::memset(attacks[s], 0, size * sizeof(Bitboard));

diff --git a/src/misc.h b/src/misc.h
index 420347f43faf46313fe06a3991f3e9c7bbd02a91..b9277372aa4ac224dd2c4baf68aebfceef64d711 100644 (file)
--- a/src/misc.h
+++ b/src/misc.h
@@ -59,4 +59,37 @@ std::ostream& operator<<(std::ostream&, SyncCout);
 #define sync_cout std::cout << IO_LOCK
 #define sync_endl std::endl << IO_UNLOCK
 
 #define sync_cout std::cout << IO_LOCK
 #define sync_endl std::endl << IO_UNLOCK
 

+
+/// xorshift64star Pseudo-Random Number Generator
+/// This class is based on original code written and dedicated
+/// to the public domain by Sebastiano Vigna (2014).
+/// It has the following characteristics:
+///  -  Outputs 64-bit numbers
+///  -  Passes Dieharder and SmallCrush test batteries
+///  -  Does not require warm-up, no zeroland to escape
+///  -  Internal state is a single 64-bit integer
+///  -  Period is 2^64 - 1
+///  -  Speed: 1.60 ns/call (Core i7 @3.40GHz)
+/// For further analysis see
+///   <http://vigna.di.unimi.it/ftp/papers/xorshift.pdf>
+
+class PRNG {
+
+  uint64_t x;
+
+  uint64_t rand64() {
+    x^=x>>12; x^=x<<25; x^=x>>27;
+    return x * 2685821657736338717LL;
+  }
+
+public:
+  PRNG(uint64_t seed) : x(seed) { assert(seed); }
+
+  template<typename T> T rand() { return T(rand64()); }
+
+  /// Special generator used to fast init magic numbers.
+  /// Output values only have 1/8th of their bits set on average.
+  template<typename T> T sparse_rand() { return T(rand64() & rand64() & rand64()); }
+};
+

 #endif // #ifndef MISC_H_INCLUDED
 #endif // #ifndef MISC_H_INCLUDED

diff --git a/src/position.cpp b/src/position.cpp
index ccc66d5ba79c6779177ad5d6ec672a7d318be5a1..a41dd52b66777aad041bfbd3bb914be8ff6c2f30 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -27,7 +27,7 @@
 #include "movegen.h"
 #include "position.h"
 #include "psqtab.h"
 #include "movegen.h"
 #include "position.h"
 #include "psqtab.h"

-#include "rkiss.h"
+#include "misc.h"

 #include "thread.h"
 #include "tt.h"
 #include "uci.h"
 #include "thread.h"
 #include "tt.h"
 #include "uci.h"


@@ -137,15 +137,15 @@ std::ostream& operator<<(std::ostream& os, const Position& pos) {
 
 void Position::init() {
 
 
 void Position::init() {
 

-  RKISS rk;
+  PRNG rng(1070372);

 
   for (Color c = WHITE; c <= BLACK; ++c)
       for (PieceType pt = PAWN; pt <= KING; ++pt)
           for (Square s = SQ_A1; s <= SQ_H8; ++s)
 
   for (Color c = WHITE; c <= BLACK; ++c)
       for (PieceType pt = PAWN; pt <= KING; ++pt)
           for (Square s = SQ_A1; s <= SQ_H8; ++s)

-              Zobrist::psq[c][pt][s] = rk.rand<Key>();
+              Zobrist::psq[c][pt][s] = rng.rand<Key>();

 
   for (File f = FILE_A; f <= FILE_H; ++f)
 
   for (File f = FILE_A; f <= FILE_H; ++f)

-      Zobrist::enpassant[f] = rk.rand<Key>();
+      Zobrist::enpassant[f] = rng.rand<Key>();

 
   for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
   {
 
   for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
   {


@@ -153,12 +153,12 @@ void Position::init() {
       while (b)
       {
           Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
       while (b)
       {
           Key k = Zobrist::castling[1ULL << pop_lsb(&b)];

-          Zobrist::castling[cr] ^= k ? k : rk.rand<Key>();
+          Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();

       }
   }
 
       }
   }
 

-  Zobrist::side = rk.rand<Key>();
-  Zobrist::exclusion  = rk.rand<Key>();
+  Zobrist::side = rng.rand<Key>();
+  Zobrist::exclusion  = rng.rand<Key>();

 
   for (PieceType pt = PAWN; pt <= KING; ++pt)
   {
 
   for (PieceType pt = PAWN; pt <= KING; ++pt)
   {

diff --git a/src/rkiss.h b/src/rkiss.h
deleted file mode 100644 (file)
index f3468db..0000000
--- a/src/rkiss.h
+++ /dev/null
@@ -1,81 +0,0 @@
-/*
-  Stockfish, a UCI chess playing engine derived from Glaurung 2.1
-  Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
-  Copyright (C) 2008-2014 Marco Costalba, Joona Kiiski, Tord Romstad
-
-  Stockfish is free software: you can redistribute it and/or modify
-  it under the terms of the GNU General Public License as published by
-  the Free Software Foundation, either version 3 of the License, or
-  (at your option) any later version.
-
-  Stockfish is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-  GNU General Public License for more details.
-
-  You should have received a copy of the GNU General Public License
-  along with this program.  If not, see <http://www.gnu.org/licenses/>.
-
-  This file is based on original code by Heinz van Saanen and is
-  available under the GNU General Public License as published by
-  the Free Software Foundation, either version 3 of the License, or
-  (at your option) any later version.
-*/
-
-#ifndef RKISS_H_INCLUDED
-#define RKISS_H_INCLUDED
-
-#include "types.h"
-
-/// RKISS is our pseudo random number generator (PRNG) used to compute hash keys.
-/// George Marsaglia invented the RNG-Kiss-family in the early 90's. This is a
-/// specific version that Heinz van Saanen derived from some public domain code
-/// by Bob Jenkins. Following the feature list, as tested by Heinz.
-///
-/// - Quite platform independent
-/// - Passes ALL dieharder tests! Here *nix sys-rand() e.g. fails miserably:-)
-/// - ~12 times faster than my *nix sys-rand()
-/// - ~4 times faster than SSE2-version of Mersenne twister
-/// - Average cycle length: ~2^126
-/// - 64 bit seed
-/// - Return doubles with a full 53 bit mantissa
-/// - Thread safe
-
-class RKISS {
-
-  uint64_t a, b, c, d;
-
-  uint64_t rotate_L(uint64_t x, unsigned k) const {
-    return (x << k) | (x >> (64 - k));
-  }
-
-  uint64_t rand64() {
-
-    const uint64_t e = a - rotate_L(b,  7);
-    a = b ^ rotate_L(c, 13);
-    b = c + rotate_L(d, 37);
-    c = d + e;
-    return d = e + a;
-  }
-
-public:
-  RKISS(int seed = 73) {
-
-    a = 0xF1EA5EED, b = c = d = 0xD4E12C77;
-
-    for (int i = 0; i < seed; ++i) // Scramble a few rounds
-        rand64();
-  }
-
-  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

diff --git a/src/search.cpp b/src/search.cpp
index 5b22b8e93730ec7bcce5c6e62cb18e2051c2bba6..7cf4a8a3b583054b651d17b7c422564e859a7296 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -27,7 +27,7 @@
 #include "evaluate.h"
 #include "movegen.h"
 #include "movepick.h"
 #include "evaluate.h"
 #include "movegen.h"
 #include "movepick.h"

-#include "rkiss.h"
+#include "misc.h"

 #include "search.h"
 #include "timeman.h"
 #include "thread.h"
 #include "search.h"
 #include "timeman.h"
 #include "thread.h"


@@ -1377,11 +1377,8 @@ moves_loop: // When in check and at SpNode search starts from here
 
   Move Skill::pick_move() {
 
 
   Move Skill::pick_move() {
 

-    static RKISS rk;
-
-    // PRNG sequence should be not deterministic
-    for (int i = Time::now() % 50; i > 0; --i)
-        rk.rand<unsigned>();
+    // PRNG sequence should be non-deterministic, so we seed it with the time at init
+    static PRNG rng(Time::now());

 
     // RootMoves are already sorted by score in descending order
     int variance = std::min(RootMoves[0].score - RootMoves[candidates - 1].score, PawnValueMg);
 
     // RootMoves are already sorted by score in descending order
     int variance = std::min(RootMoves[0].score - RootMoves[candidates - 1].score, PawnValueMg);


@@ -1402,7 +1399,7 @@ moves_loop: // When in check and at SpNode search starts from here
 
         // This is our magic formula
         score += (  weakness * int(RootMoves[0].score - score)
 
         // This is our magic formula
         score += (  weakness * int(RootMoves[0].score - score)

-                  + variance * (rk.rand<unsigned>() % weakness)) / 128;
+                  + variance * (rng.rand<unsigned>() % weakness)) / 128;

 
         if (score > maxScore)
         {
 
         if (score > maxScore)
         {