Simpler PRNG and faster magics search
authorErnesto Gatti <rnysto@gmail.com>
Mon, 8 Dec 2014 00:10:57 +0000 (08:10 +0800)
committerGary Linscott <glinscott@gmail.com>
Mon, 8 Dec 2014 00:18:26 +0000 (08:18 +0800)
commit158864270a055fe20dca4a87f4b7a8aa9cedfeb9
tree55b42af742a43155069b5b7ecd2ef65354baa659
parenta87da2c4b3dce975fa8642c352c99aed5a1420f8
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
src/bitboard.cpp
src/misc.h
src/position.cpp
src/rkiss.h [deleted file]
src/search.cpp