From: Marco Costalba Date: Sun, 7 Nov 2010 10:13:17 +0000 (+0100) Subject: Use Heinz's RKiss instead of marsenne X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=f5e28ef5127ff29310f9c2e8e321eb24214f2439;hp=287556f97d54c87b3a973e22e133a9d09b62676f Use Heinz's RKiss instead of marsenne Signed-off-by: Marco Costalba --- diff --git a/src/application.cpp b/src/application.cpp index 2d7a10bb..08384716 100644 --- a/src/application.cpp +++ b/src/application.cpp @@ -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() { diff --git a/src/book.cpp b/src/book.cpp index c9a2e9c9..a34d17b7 100644 --- a/src/book.cpp +++ b/src/book.cpp @@ -32,7 +32,6 @@ #include #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) diff --git a/src/book.h b/src/book.h index 32b6e607..45d75688 100644 --- a/src/book.h +++ b/src/book.h @@ -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 index 332ad6c6..00000000 --- a/src/mersenne.cpp +++ /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 index ea7c929b..00000000 --- a/src/mersenne.h +++ /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 . -*/ - - -#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) diff --git a/src/position.cpp b/src/position.cpp index 3c4fdc63..e6261d3c 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -31,11 +31,11 @@ #include #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 index 00000000..6e94dc27 --- /dev/null +++ b/src/rkiss.h @@ -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 . + + ** *********************************************************************** **/ + +#ifndef _RKISS_H_ +#define _RKISS_H_ + +/** Includes **/ +#include // srand(), rand() +#include // 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