Re: [Computer-go] fast + good RNG
Looking at the lightest playout version of my bitmap-based 9x9 program (source-code somewhere in the archives), I spent an estimated 2% of the time generating random numbers, so 40% seems to indicate something is not right, such as re-initializing the generator all the time. The execution time of my engine breaks down sort-of like this on my MacBook: benchmarking Mersenne Twister (SFMT version [following Agner Fog]) [BRandom] = 1, [IRandom] = 1, [IRandomX] = 2, [Random] = 2, [FRandom] = 2 benchmarking playouts (clock cycles) [game] = 18051 cc, [moves] = 111.07 benchmarking playouts (wall time) [game] = 126.108 kpps, [moves] = 111.07 benchmarking board functions (calls per game/clock cycles) [select] 111/55, [play] 106/93, [score] 14, [win] 0.4251 benchmarking move generator (calls per game/clock cycles, find+pick) [moves] 111 [random] 111/17+36 This last line breaks down move-generation in finding all legal moves (17cc, using Gunnar Farneback's Brown programs definition of legal) and picking one uniformly at random (36cc). That last method uses 1-3 random numbers of 1cc each. A move takes 55 + 93 = 148cc, so 3cc represents at most 2%. Things get a bit messier to assess once you consider waterfalling moves, such as captures, atari extensions, etc. In general, though, going towards heavier playouts will only reduce the time spent on random number generation because you will have to maintain more data or perform more logic. In any case, spending more than a handful of cc on random number generation is not needed and, thus, random number generation should not be high on your resource consumption list. For reference, an old profile report for a non-bitmap heavier MCTS-player reports 1.1% of time was spent on random number generation. René BTW. The average game-length using a uniformly random move-generator is a pretty good correctness test. On Sun, Mar 29, 2015 at 10:16 PM, Petri Pitkanen petri.t.pitka...@gmail.com wrote: Assuming you are using some sensible OS there better ways profile than sample like oprofile for linux. There is similar thing for FreeBSD I think. No instrumentation san sampling gets automated Petri 2015-03-30 8:05 GMT+03:00 hughperkins2 hughperki...@gmail.com: 40% sounds pretty high. Are you sure its not an artefact of your profiling implementation? I prefer not to instrument, but to sample stack traces. You can do this using gdb by pressing ctrl-c, then type bt. Do this 10 times, and look for the parts of the stack that occur often. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
For profiling I use callgrind. Afaik it is the most accurate as it simulates a processor and counts cycles etc. As others pointed out: my playout-code is somewhat lightweight. In that 40% version it only checked if a cross is empty. I added super-ko check which gave a 10% hit on the number of pps. Currently I'm looking into doing full validity checks. It currently does +/- 20-30k pps with one core on a HT-sibling. 40% sounds pretty high. Are you sure its not an artefact of your profiling implementation? I prefer not to instrument, but to sample stack traces. You can do this using gdb by pressing ctrl-c, then type bt. Do this 10 times, and look for the parts of the stack that occur often. Folkert van Heusden -- Ever wonder what is out there? Any alien races? Then please support the seti@home project: setiathome.ssl.berkeley.edu -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
Assuming you are using some sensible OS there better ways profile than sample like oprofile for linux. There is similar thing for FreeBSD I think. No instrumentation san sampling gets automated Petri 2015-03-30 8:05 GMT+03:00 hughperkins2 hughperki...@gmail.com: 40% sounds pretty high. Are you sure its not an artefact of your profiling implementation? I prefer not to instrument, but to sample stack traces. You can do this using gdb by pressing ctrl-c, then type bt. Do this 10 times, and look for the parts of the stack that occur often. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
40% sounds pretty high. Are you sure its not an artefact of your profiling implementation? I prefer not to instrument, but to sample stack traces. You can do this using gdb by pressing ctrl-c, then type bt. Do this 10 times, and look for the parts of the stack that occur often. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
I measured that std::mt19937_64 (the mersenne twister from the standard c++ libraries) uses about 40% cpu time during playouts. So I wonder: is there a faster prng while still generating good enough random? This question suggests some: http://stackoverflow.com/q/1640258/841830 This question is not that useful, but contains links to more information on alternative random algorithms, and a link to a video presentation: http://stackoverflow.com/q/19665818/841830 Random number generation in multi-threaded programs is an interesting topic, and worth being aware of. (E.g. you don't want to use 16 threads, only to find all 16 generate the same random sequence, so each thread generates the same playout as all the other threads.) (See the example of using thread_local in http://codereview.stackexchange.com/a/84112 ) 40% sounds high. Are you re-initializing the generator each time you need a new random number? Darren -- Darren Cook, Software Researcher/Developer My new book: Data Push Apps with HTML5 SSE Published by O'Reilly: (ask me for a discount code!) http://shop.oreilly.com/product/0636920030928.do Also on Amazon and at all good booksellers! ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
Anyway, it's very easy to make a fast PRNG these days. A couple words of caution about hacking PNRG. Back in the stone age of computing, some mavens from the triple-i movie group cooked up a galaxy simulator which generated pictures of spiral galaxies based on a numerical model. The capability to make pictures was rare at the time. The pictures sucked. After lots of hunting for flaws in the model, and tweaking it, the real cause for the poor quality was determined to be that fortran's random numbers weren't very good. Substitute a better PRNG, and beautiful pictures emerged. -- On a similar note, working with a UCT robot for a blokus clone at boardspace.net, I found that tiny changes in the way PRNG's were used had measurable effects on the quality of play. Not necessarily better or worse, just different. -- So if you're going to hack the PRNG, you should retain the ability to use a gold standard PRNG instead of your faster-better-cheaper model, and you should use it once in a while, just to be sure you're not introducing hidden flaws. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
29.03.2015 um 12:29 schrieb Álvaro Begué alvaro.be...@gmail.com: If your PRNG is consuming 40% of your CPU time, your playouts are too light. That's what I was going to say, too. My program isn't the fastest (5k pps on 9x9) and the RNG never even appeared in the profiling output. Urban ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
I switched to SFMT [0]. But that was some years ago, there might be faster options now. I also generated it in megabyte batches and consume it from there, generating a new megabyte as needed. Lastly, I had some code to make sure I did not consume more bits of entropy than required. Two uniform choices, one bit. Three choices: fractional bits. [0] http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/ — Remco -Original Message- From: folkert folk...@vanheusden.com To: computer-go@computer-go.org Sent: Sun, 29 Mar 2015 17:50 Subject: [Computer-go] fast + good RNG Hi, I measured that std::mt19937_64 (the mersenne twister from the standard c++ libraries) uses about 40% cpu time during playouts. So I wonder: is there a faster prng while still generating good enough random? Folkert van Heusden -- Nagios user? Check out CoffeeSaint - the versatile Nagios status viewer! http://www.vanheusden.com/java/CoffeeSaint/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
Powers of two are easy, just take the minimum amount of bits out of your entropy. For a generic number N Approach 1: round up to the next highest power of two, then discard and try again if it is = N. This could potentially reject up to half the samples, so I have two improvements I used: Approach 2: take 3 more bits than the next highest power of two. Reject if it is higher than the highest multiple of N less than this larger power of two. On accept return modulo N. Approach 3: An arithmetic decoder fed with entropy. When done with 64 bit integers it is as good as perfect in terms of bias and entropy consumption. — Remco -Original Message- From: folkert folk...@vanheusden.com To: computer-go@computer-go.org Sent: Sun, 29 Mar 2015 18:05 Subject: Re: [Computer-go] fast + good RNG Ah! But how do you make sure the numbers are uniformly distributed? On Sun, Mar 29, 2015 at 05:58:56PM +0800, remco.bloe...@singularityu.org wrote: I switched to SFMT [0]. But that was some years ago, there might be faster options now. I also generated it in megabyte batches and consume it from there, generating a new megabyte as needed. Lastly, I had some code to make sure I did not consume more bits of entropy than required. Two uniform choices, one bit. Three choices: fractional bits. [0] http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/ ??? Remco -Original Message- From: folkert folk...@vanheusden.com To: computer-go@computer-go.org Sent: Sun, 29 Mar 2015 17:50 Subject: [Computer-go] fast + good RNG Hi, I measured that std::mt19937_64 (the mersenne twister from the standard c++ libraries) uses about 40% cpu time during playouts. So I wonder: is there a faster prng while still generating good enough random? Folkert van Heusden -- Nagios user? Check out CoffeeSaint - the versatile Nagios status viewer! http://www.vanheusden.com/java/CoffeeSaint/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go Folkert van Heusden -- MultiTail er et flexible tool for å kontrolere Logfiles og commandoer. Med filtrer, farger, sammenføringer, forskeliger ansikter etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
Hmm, I use just a super-naive LCG
unsigned long hi, lo;
lo = 16807 * (pmseed 0x);
hi = 16807 * (pmseed 16);
lo += (hi 0x7fff) 16;
lo += hi 15;
pmseed = (lo 0x7fff) + (lo 31);
return ((pmseed 0x) * max) 16;
in Pachi. Frankly, I think I could get away with just
pmseed = pmseed * 16807 + 12345;
return pmseed % max;
Do you really need high quality RNG in your program? I'd be interested
if someone using a sophisticated RNG would compare it with using just
the above wrt. Elo strength and performance.
(BTW, for floats, there's this neat trick to take advantage of the
internal representation
union { unsigned long ul; floating_t f; } p;
p.ul = (((pmseed *= 16807) 0x007f) - 1) | 0x3f80;
return p.f - 1.0f;
see also http://rgba.org/articles/sfrand/sfrand.htm)
On Sun, Mar 29, 2015 at 05:58:56PM +0800, remco.bloe...@singularityu.org wrote:
I switched to SFMT [0]. But that was some years ago, there might be faster
options now.
I also generated it in megabyte batches and consume it from there, generating
a new megabyte as needed.
Lastly, I had some code to make sure I did not consume more bits of entropy
than required. Two uniform choices, one bit. Three choices: fractional
bits.
[0]
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/
— Remco
-Original Message-
From: folkert folk...@vanheusden.com
To: computer-go@computer-go.org
Sent: Sun, 29 Mar 2015 17:50
Subject: [Computer-go] fast + good RNG
Hi,
I measured that std::mt19937_64 (the mersenne twister from the standard
c++ libraries) uses about 40% cpu time during playouts.
So I wonder: is there a faster prng while still generating good enough
random?
Folkert van Heusden
--
Nagios user? Check out CoffeeSaint - the versatile Nagios status
viewer! http://www.vanheusden.com/java/CoffeeSaint/
--
Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
--
Petr Baudis
If you do not work on an important problem, it's unlikely
you'll do important work. -- R. Hamming
http://www.cs.virginia.edu/~robins/YouAndYourResearch.html
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
Why not xorshift+128 ?
*
include stdint.h
/* The state must be seeded so that it is not everywhere zero. */
uint64_t s[2];
uint64_t xorshift128plus(void) {
uint64_t x = s[0];
uint64_t const y = s[1];
s[0] = y;
x ^= x 23; // a
x ^= x 17; // b
x ^= y ^ (y 26); // c
s[1] = x;
return x + y;
}
**
It passes even more tests of randomness than Mersenne, according to Wikipedia (easily checkable, that's BigCrush, a standard test suite, the hardest usual one),
and is 2.5x times faster, according to a PRNG shootout, though I don't think the author is neutral on the matter.
Period is $2^128 - 1$, more than sufficient for go. (If you need longer
periods, use longer keys, I guess). And the code is easy.
Jonas
Hmm, I use just a super-naive LCG
unsigned long hi, lo;
lo = 16807 * (pmseed 0x);
hi = 16807 * (pmseed 16);
lo += (hi 0x7fff) 16;
lo += hi 15;
pmseed = (lo 0x7fff) + (lo 31);
return ((pmseed 0x) * max) 16;
in Pachi. Frankly, I think I could get away with just
pmseed = pmseed * 16807 + 12345;
return pmseed % max;
Do you really need high quality RNG in your program? I'd be interested
if someone using a sophisticated RNG would compare it with using just
the above wrt. Elo strength and performance.
(BTW, for floats, there's this neat trick to take advantage of the
internal representation
union { unsigned long ul; floating_t f; } p;
p.ul = (((pmseed *= 16807) 0x007f) - 1) | 0x3f80;
return p.f - 1.0f;
see also http://rgba.org/articles/sfrand/sfrand.htm)
On Sun, Mar 29, 2015 at 05:58:56PM +0800, remco.bloe...@singularityu.org wrote:
I switched to SFMT [0]. But that was some years ago, there might be faster
options now.
I also generated it in megabyte batches and consume it from there, generating a
new megabyte as needed.
Lastly, I had some code to make sure I did not consume more bits of entropy
than required. Two uniform choices, one bit. Three choices: fractional bits.
[0]
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/
— Remco
-Original Message-
From: folkert folk...@vanheusden.com
To: computer-go@computer-go.org
Sent: Sun, 29 Mar 2015 17:50
Subject: [Computer-go] fast + good RNG
Hi,
I measured that std::mt19937_64 (the mersenne twister from the standard
c++ libraries) uses about 40% cpu time during playouts.
So I wonder: is there a faster prng while still generating good enough
random?
Folkert van Heusden
--
Nagios user? Check out CoffeeSaint - the versatile Nagios status
viewer! http://www.vanheusden.com/java/CoffeeSaint/
--
Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
--
Petr Baudis
If you do not work on an important problem, it's unlikely
you'll do important work. -- R. Hamming
http://www.cs.virginia.edu/~robins/YouAndYourResearch.html
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
I just think Go (except trivial implementation cases) should be very insensitive to RNGs. It is not like many Monte Carlo applications where you just call the RNG in a tight loop in regular manner to move in the same state space. In a Go program, you call the RNG from playouts in all sorts of irregular cases to pick out of available patterns /liberties/neighbor groups, to check whether to apply a given heuristic, and the set of moves to pick from shift-shapes continuously. Even with a short-period RNG, you always use that number to decide something else. One of these times, I'll check if Pachi can still play Go with RNG being (seed += 1313) % max. You're right, a simple LCG is probably more than sufficient. Jonas ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[Computer-go] fast + good RNG
Hi, I measured that std::mt19937_64 (the mersenne twister from the standard c++ libraries) uses about 40% cpu time during playouts. So I wonder: is there a faster prng while still generating good enough random? Folkert van Heusden -- Nagios user? Check out CoffeeSaint - the versatile Nagios status viewer! http://www.vanheusden.com/java/CoffeeSaint/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
If your PRNG is consuming 40% of your CPU time, your playouts are too light. Anyway, it's very easy to make a fast PRNG these days. The first thing that comes to mind is a 64-bit linear congruential generator of which you use the middle bits, or you can XOR the high 32 bits and the low 32 bits together. LCGs have well-understood limitations that don't really matter for a go program. If you want higher-quality PRNs you need to use a large state, but you can still make it be very fast. Still, try the LCG first. I would be surprised if you find any degradation in strength of your engine compared to the Mersenne twister. Álvaro. On Sun, Mar 29, 2015 at 12:05 PM, folkert folk...@vanheusden.com wrote: Ah! But how do you make sure the numbers are uniformly distributed? On Sun, Mar 29, 2015 at 05:58:56PM +0800, remco.bloe...@singularityu.org wrote: I switched to SFMT [0]. But that was some years ago, there might be faster options now. I also generated it in megabyte batches and consume it from there, generating a new megabyte as needed. Lastly, I had some code to make sure I did not consume more bits of entropy than required. Two uniform choices, one bit. Three choices: fractional bits. [0] http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/ ??? Remco -Original Message- From: folkert folk...@vanheusden.com To: computer-go@computer-go.org Sent: Sun, 29 Mar 2015 17:50 Subject: [Computer-go] fast + good RNG Hi, I measured that std::mt19937_64 (the mersenne twister from the standard c++ libraries) uses about 40% cpu time during playouts. So I wonder: is there a faster prng while still generating good enough random? Folkert van Heusden -- Nagios user? Check out CoffeeSaint - the versatile Nagios status viewer! http://www.vanheusden.com/java/CoffeeSaint/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go Folkert van Heusden -- MultiTail er et flexible tool for å kontrolere Logfiles og commandoer. Med filtrer, farger, sammenføringer, forskeliger ansikter etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
On Sun, Mar 29, 2015 at 01:08:20PM +0200, Kahn Jonas wrote: Why not xorshift+128 ? Because I wasn't aware of it. Nice! But I probably won't remember the code by heart like I do seed * prime_near_2^14. ;-) Period is $2^128 - 1$, more than sufficient for go. (If you need longer periods, use longer keys, I guess). And the code is easy. I just think Go (except trivial implementation cases) should be very insensitive to RNGs. It is not like many Monte Carlo applications where you just call the RNG in a tight loop in regular manner to move in the same state space. In a Go program, you call the RNG from playouts in all sorts of irregular cases to pick out of available patterns /liberties/neighbor groups, to check whether to apply a given heuristic, and the set of moves to pick from shift-shapes continuously. Even with a short-period RNG, you always use that number to decide something else. One of these times, I'll check if Pachi can still play Go with RNG being (seed += 1313) % max. Petr Baudis ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] fast + good RNG
Ah! But how do you make sure the numbers are uniformly distributed? On Sun, Mar 29, 2015 at 05:58:56PM +0800, remco.bloe...@singularityu.org wrote: I switched to SFMT [0]. But that was some years ago, there might be faster options now. I also generated it in megabyte batches and consume it from there, generating a new megabyte as needed. Lastly, I had some code to make sure I did not consume more bits of entropy than required. Two uniform choices, one bit. Three choices: fractional bits. [0] http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/ ??? Remco -Original Message- From: folkert folk...@vanheusden.com To: computer-go@computer-go.org Sent: Sun, 29 Mar 2015 17:50 Subject: [Computer-go] fast + good RNG Hi, I measured that std::mt19937_64 (the mersenne twister from the standard c++ libraries) uses about 40% cpu time during playouts. So I wonder: is there a faster prng while still generating good enough random? Folkert van Heusden -- Nagios user? Check out CoffeeSaint - the versatile Nagios status viewer! http://www.vanheusden.com/java/CoffeeSaint/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go Folkert van Heusden -- MultiTail er et flexible tool for å kontrolere Logfiles og commandoer. Med filtrer, farger, sammenføringer, forskeliger ansikter etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
