Use Heinz's RKiss instead of marsenne
authorMarco Costalba <mcostalba@gmail.com>
Sun, 7 Nov 2010 10:13:17 +0000 (11:13 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Sun, 7 Nov 2010 10:52:59 +0000 (11:52 +0100)
Signed-off-by: Marco Costalba <mcostalba@gmail.com>
src/application.cpp
src/book.cpp
src/book.h
src/mersenne.cpp [deleted file]
src/mersenne.h [deleted file]
src/position.cpp
src/rkiss.h [new file with mode: 0644]

index 2d7a10b..0838471 100644 (file)
@@ -27,7 +27,6 @@
 #include "endgame.h"
 #include "evaluate.h"
 #include "material.h"
-#include "mersenne.h"
 #include "misc.h"
 #include "movepick.h"
 #include "position.h"
@@ -41,7 +40,6 @@
 
 Application::Application() {
 
-    init_mersenne();
     init_direction_table();
     init_bitboards();
     init_uci_options();
@@ -51,10 +49,6 @@ Application::Application() {
     init_bitbases();
     init_search();
     init_threads();
-
-    // Make random number generation less deterministic, for book moves
-    for (int i = abs(get_system_time() % 10000); i > 0; i--)
-        genrand_int32();
 }
 
 void Application::initialize() {
index c9a2e9c..a34d17b 100644 (file)
@@ -32,7 +32,6 @@
 #include <cassert>
 
 #include "book.h"
-#include "mersenne.h"
 #include "movegen.h"
 
 using namespace std;
@@ -343,6 +342,13 @@ namespace {
 //// Functions
 ////
 
+// C'tor. Make random number generation less deterministic, for book moves
+Book::Book() {
+
+  for (int i = abs(get_system_time() % 10000); i > 0; i--)
+      RKiss.rand32();
+}
+
 
 /// Destructor. Be sure file is closed before we leave.
 
@@ -435,7 +441,7 @@ Move Book::get_move(const Position& pos, bool findBestMove) {
       // high score it has more probability to be choosen then a one with
       // lower score. Note that first entry is always chosen.
       scoresSum += score;
-      if (int(genrand_int32() % scoresSum) < score)
+      if (int(RKiss.rand32() % scoresSum) < score)
           bookMove = entry.move;
   }
   if (!bookMove)
index 32b6e60..45d7568 100644 (file)
@@ -38,6 +38,7 @@
 
 #include "move.h"
 #include "position.h"
+#include "rkiss.h"
 
 
 ////
@@ -56,7 +57,7 @@ class Book : private std::ifstream {
   Book(const Book&); // just decleared..
   Book& operator=(const Book&); // ..to avoid a warning
 public:
-  Book() {}
+  Book();
   ~Book();
   void open(const std::string& fName);
   void close();
@@ -74,6 +75,7 @@ private:
 
   std::string fileName;
   int bookSize;
+  RKISS RKiss;
 };
 
 
diff --git a/src/mersenne.cpp b/src/mersenne.cpp
deleted file mode 100644 (file)
index 332ad6c..0000000
+++ /dev/null
@@ -1,171 +0,0 @@
-/*
-   A C-program for MT19937, with initialization improved 2002/1/26.
-   Coded by Takuji Nishimura and Makoto Matsumoto.
-
-   Before using, initialize the state by using init_genrand(seed)
-   or init_by_array(init_key, key_length).
-
-   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
-   All rights reserved.
-
-   Redistribution and use in source and binary forms, with or without
-   modification, are permitted provided that the following conditions
-   are met:
-
-     1. Redistributions of source code must retain the above copyright
-        notice, this list of conditions and the following disclaimer.
-
-     2. Redistributions in binary form must reproduce the above copyright
-        notice, this list of conditions and the following disclaimer in the
-        documentation and/or other materials provided with the distribution.
-
-     3. The names of its contributors may not be used to endorse or promote
-        products derived from this software without specific prior written
-        permission.
-
-   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
-   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
-   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
-   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
-   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
-   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
-   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
-   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
-
-   Any feedback is very welcome.
-   http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
-   email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
-*/
-
-#include "mersenne.h"
-
-namespace {
-
-  // Period parameters
-  const int N = 624;
-  const int M = 397;
-  const unsigned long MATRIX_A   = 0x9908b0dfUL; // Constant vector a
-  const unsigned long UPPER_MASK = 0x80000000UL; // Most significant w-r bits
-  const unsigned long LOWER_MASK = 0x7fffffffUL; // Least significant r bits
-
-  unsigned long mt[N]; // The array for the state vector
-  int mti = N + 1;     // mti == N+1 means mt[N] is not initialized
-
-  // Initializes mt[N] with a seed
-  void init_genrand(unsigned long s) {
-
-      mt[0]= s & 0xffffffffUL;
-      for (mti = 1; mti < N; mti++)
-      {
-          // See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier.
-          // In the previous versions, MSBs of the seed affect
-          // only MSBs of the array mt[].
-          // 2002/01/09 modified by Makoto Matsumoto
-          mt[mti] = 1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti;
-          mt[mti] &= 0xffffffffUL; // For > 32 bit machines
-      }
-  }
-
-  // Initialize by an array with array-length
-  // init_key is the array for initializing keys
-  // key_length is its length
-  // slight change for C++, 2004/2/26
-  void init_by_array(unsigned long init_key[], int key_length) {
-
-      int i = 1;
-      int j = 0;
-      int k = (N > key_length ? N : key_length);
-
-      init_genrand(19650218UL);
-
-      for ( ; k; k--)
-      {
-          mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL)) + init_key[j] + j; // Non linear
-          mt[i] &= 0xffffffffUL; // For WORDSIZE > 32 machines
-          i++; j++;
-          if (i >= N)
-          {
-              mt[0] = mt[N-1];
-              i = 1;
-          }
-          if (j >= key_length)
-              j = 0;
-      }
-      for (k = N-1; k; k--)
-      {
-          mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL)) - i; // Non linear
-          mt[i] &= 0xffffffffUL; // For WORDSIZE > 32 machines
-          i++;
-          if (i >= N)
-          {
-              mt[0] = mt[N-1];
-              i = 1;
-          }
-      }
-      mt[0] = 0x80000000UL; // MSB is 1; assuring non-zero initial array
-  }
-
-} // namespace
-
-
-// Generates a random number on [0,0xffffffff]-interval
-uint32_t genrand_int32() {
-
-  unsigned long y;
-  static unsigned long mag01[2] = {0x0UL, MATRIX_A};
-  /* mag01[x] = x * MATRIX_A  for x=0,1 */
-
-  // Generate N words at one time
-  if (mti >= N)
-  {
-      int kk;
-
-      if (mti == N+1)           // If init_genrand() has not been called,
-          init_genrand(5489UL); // a default initial seed is used.
-
-      for (kk = 0; kk < N-M; kk++)
-      {
-          y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
-          mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
-      }
-      for ( ; kk < N-1; kk++)
-      {
-          y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
-          mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
-      }
-      y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
-      mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
-      mti = 0;
-  }
-
-  y = mt[mti++];
-
-  // Tempering
-  y ^= (y >> 11);
-  y ^= (y <<  7) & 0x9d2c5680UL;
-  y ^= (y << 15) & 0xefc60000UL;
-  y ^= (y >> 18);
-
-  return y;
-}
-
-uint64_t genrand_int64() {
-
-  uint64_t x, y;
-
-  x = genrand_int32();
-  y = genrand_int32();
-  return (x << 32) | y;
-}
-
-void init_mersenne() {
-
-  unsigned long init[4] = {0x123, 0x234, 0x345, 0x456};
-  unsigned long length = 4;
-
-  init_by_array(init, length);
-}
diff --git a/src/mersenne.h b/src/mersenne.h
deleted file mode 100644 (file)
index ea7c929..0000000
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
-  Stockfish, a UCI chess playing engine derived from Glaurung 2.1
-  Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
-  Copyright (C) 2008-2010 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/>.
-*/
-
-
-#if !defined(MERSENNE_H_INCLUDED)
-#define MERSENNE_H_INCLUDED
-
-////
-//// Includes
-////
-
-#include "types.h"
-
-
-////
-//// Prototypes
-////
-
-extern uint32_t genrand_int32();
-extern uint64_t genrand_int64();
-extern void init_mersenne();
-
-
-#endif // !defined(MERSENNE_H_INCLUDED)
index 3c4fdc6..e6261d3 100644 (file)
 #include <sstream>
 
 #include "bitcount.h"
-#include "mersenne.h"
 #include "movegen.h"
 #include "movepick.h"
 #include "position.h"
 #include "psqtab.h"
+#include "rkiss.h"
 #include "san.h"
 #include "tt.h"
 #include "ucioption.h"
@@ -1759,19 +1759,20 @@ bool Position::has_mate_threat() {
 
 void Position::init_zobrist() {
 
+  RKISS RKiss;
   int i,j, k;
 
   for (i = 0; i < 2; i++) for (j = 0; j < 8; j++) for (k = 0; k < 64; k++)
-      zobrist[i][j][k] = Key(genrand_int64());
+      zobrist[i][j][k] = Key(RKiss.rand64());
 
   for (i = 0; i < 64; i++)
-      zobEp[i] = Key(genrand_int64());
+      zobEp[i] = Key(RKiss.rand64());
 
   for (i = 0; i < 16; i++)
-      zobCastle[i] = Key(genrand_int64());
+      zobCastle[i] = Key(RKiss.rand64());
 
-  zobSideToMove = Key(genrand_int64());
-  zobExclusion  = Key(genrand_int64());
+  zobSideToMove = Key(RKiss.rand64());
+  zobExclusion  = Key(RKiss.rand64());
 }
 
 
diff --git a/src/rkiss.h b/src/rkiss.h
new file mode 100644 (file)
index 0000000..6e94dc2
--- /dev/null
@@ -0,0 +1,77 @@
+/** *********************************************************************** **
+ ** A small "keep it simple and stupid" RNG with some fancy merits:
+ **
+ ** 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 save
+ **
+ ** (c) Heinz van Saanen
+
+  This file 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.
+
+  This file 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/>.
+
+ ** *********************************************************************** **/
+
+#ifndef _RKISS_H_
+#define _RKISS_H_
+
+/** Includes **/
+#include <cstdlib>    // srand(), rand()
+#include <ctime>      // time()
+#include "types.h"    // (u)int8_t .. (u)int64_t
+
+
+/** Random class **/
+class RKISS {
+
+private:
+       // Keep variables always together
+       struct S { uint64_t a; uint64_t b; uint64_t c; uint64_t d; } s;
+
+       // Init seed and scramble a few rounds
+       void raninit ( uint64_t seed ) {
+               s.a = 0xf1ea5eed; s.b = s.c = s.d = seed;
+               for ( uint64_t i=0; i<8; i++ ) rand64();
+       }
+
+public:
+       // Instance seed random or implicite
+       RKISS() { ::srand ( (uint32_t)time(NULL) ); raninit ( (uint64_t)::rand() ); }
+       // RKISS( uint64_t s ) { raninit ( s ); }
+
+       // (Re)init seed
+       // void init ( uint64_t seed ) { raninit ( seed ); }
+
+       // Return 32 bit unsigned integer in between [0,2^32-1]
+       uint32_t rand32 () { return (uint32_t) rand64 (); }
+
+       // Return 64 bit unsigned integer in between [0,2^64-1]
+       uint64_t rand64 () {
+               const uint64_t e = s.a - ((s.b<<7) | (s.b>>57));
+               s.a = s.b ^ ((s.c<<13) | (s.c>>51));
+               s.b = s.c + ((s.d<<37) | (s.d>>27));
+               s.c = s.d + e;
+               return s.d = e + s.a;
+       }
+
+       // Return double in between [0,1). Keep full 53 bit mantissa
+       // double frand () { return (int64_t)(rand64()>>11) * (1.0/(67108864.0*134217728.0)); }
+};
+
+// _RKISS_H_
+#endif