search

pasky / pachi

A fairly strong Go/Baduk/Weiqi playing program
http://pachi.or.cz/
GNU General Public License v2.0
514 stars 117 forks source link

Improved random number generator for integers #9

Closed gonmf closed 9 years ago

gonmf commented 9 years ago

Replaced the previous two functions (single and multi threaded) with an alternative LCG used in glibc's random. The floating point functions were left as is. It should be ~45% faster now, same average/variance.

I tested several random number geneation functions for small ranges typically used in computer Go. The standalone code is available at: https://gist.github.com/gonmf/0ee67393182ef3173de7

pasky commented 9 years ago

Thank you!

It would be great to play-test this change just as a sanity check that nothing broke. Is that within your means? (The setup is described in t-play/. For sanity check, it would be great to have 200 + 200 games. But if that sounds like too much, I think for the time being I'll be happy if you say you tested it just in a game or a few and it appeared about as strong as before; seriously breaking RNG would probably have catastrophic and very noticeable effects, so this should be fine.)

gonmf commented 9 years ago

Learning your autotest stuff right now seems a bit complicated so I'll instead run 19x19 matches directly with twogtp against GNU Go 3.8. Is it good enough or is there some specific thing that your tests run that would not be caught this way? Is GNU Go lvl 10 very severely the underdog?

pasky commented 9 years ago

GNU Go lvl 10 is very severely the underdog, but it depends on thinking time. You may try with pachi -t _90 (1.5 minutes sudden death) and reverse komi -7.5 in favor of gnugo.

gonmf commented 9 years ago

Nevermind, I'll run version against version of Pachi. I suspect that's that what autotest would do too.

pasky commented 9 years ago

In general, it's better to test against a third-party program, that's what autotest does too. But in this specific case (sanity check) it probably doesn't really matter so that's fine too. :)

gonmf commented 9 years ago

I've short on time so I run just 20 matches, 19x19, 7.5 komi with 2 minutes absolute time per side, and if I'm reading this well (twogtp with -alternate and programs with the same name&version can be misleading) the new version seems better, with winrate 60% (±11)

I'm still looking into 32 bit number generators and floating point, so I might submit a new pull request later on, with more testing than 20 matches.

pasky commented 9 years ago

Awesome, thank you for the contribution!

gonmf commented 9 years ago

The current floating point RNG is very good, for single precision. I can't seem to get it to work using double, at all. It might have to do with 32 vs 64 bit architectures and the union aligning. The function in random.c has a link in a comment that doesn't work anymore but I found the article. It doesn't imply any compatibility with double precision. This might be a serious bug (unlikely?) or an architecture/compiler issue?

Does it actually work right now?

gonmf commented 9 years ago

Anyways, the fix is very simple, I'm benchmarking it now.