search

leela-zero / leela-zero

Go engine with no human-provided knowledge, modeled after the AlphaGo Zero paper.
GNU General Public License v3.0
5.36k stars 1.01k forks source link

Why xoroshiro128+ as Random engine? #896

Closed Error323 closed 6 years ago

Error323 commented 6 years ago

I was wondering why the xoroshiro128+ random generator was implemented in Random.cpp? Wouldn't e.g. the std::mt19937_64 suffice?

d7urban commented 6 years ago

Because it’s much faster?

wctgit commented 6 years ago

I'm guessing because it's good enough and very fast. Probably speed is a big consideration, though I wonder if RNGtion is an actual performance bottleneck or not.

sethtroisi commented 6 years ago

AFAIK we only use random in three places.

  1. For constructing ~1500 Zobrist hashes on program start up
  2. For determining which rotational symmetry to use.
  3. For debug and sampling purposes.

None of these require highly random numbers and none of these have high performance requirements (2 is called ~1000 times per second), so pretty much any PRNG will do IMO

Error323 commented 6 years ago

Agreed @sethtroisi, since you went over Random and Timing with the std lib. Greatly improving their simplicity I was wondering what made you keep xoroshiro :-)

sethtroisi commented 6 years ago

@Error323 I always aim for the smallest possible change (minimizing the number of possible objections and hangups in the Pull Request). When I worked on random I said "that can go in a later pull request" and never returned to look at it.

gcp commented 6 years ago

It's faster and much better (in terms of randomness) than mt19937_64. The rng in the C++11 stdlib are just terrible compared to modern state of the art, and there's seeding issues with the stdlib interfaces too.

Also having a fast RNG is pretty handy for Monte Carlo playouts (i.e. it's a leftover).

marcocalignano commented 6 years ago

I wrote a random library few years a go for my GA projects that uses /var/urandom on a linux system. I could 'port' to C++14 and then have CMake link it if a /dev/urandom device is found, so at least the Linux systems (and maybe Mac) have a fast RNG.

gcp commented 6 years ago

We already use /dev/urandom for seeding on Linux through https://github.com/gcp/leela-zero/blob/bdc3abe7bbd08d1c3a4d5e5ad2068ea81c99237e/src/GTP.cpp#L101

In any case such a call is much slower (userspace<>kernel transition) than just generating the numbers ourselves. xoroshiro is state of the art and we're not doing cryptography.

Error323 commented 6 years ago

I see, I had assumed mersenne twister was quite allright. Just looked up the differences and xoroshiro128+ is indeed far superior. http://xoroshiro.di.unimi.it/

Anyway I realize this is not a very relevant issue for the project, I think it can be closed now. Thanks!