Author: Dann Corbit
Date: 10:15:17 06/08/04
Go up one level in this thread
On June 07, 2004 at 21:23:46, Dieter Buerssner wrote: >On June 07, 2004 at 21:00:35, Dann Corbit wrote: > >>On June 07, 2004 at 20:42:22, Dieter Buerssner wrote: >> >>>On June 07, 2004 at 20:28:51, Dann Corbit wrote: >>> >>>>On June 07, 2004 at 20:19:12, Dann Corbit wrote: >>>> >>>>>ftp://cap.connx.com/pub/chess-engines/new-approach/frcpos.c >>>> >>>>It would be a lot better as a C++ class with srand((unsigned)time(NULL)) in the >>>>constructor. Also, the C/C++ prng of questionable quality would be much better >>>>replaced by the Mersenne Twister. In fact, the MT prng is so good, you could >>>>replace the monkey business with floating point and division by a modulus >>>>operator. >>> >>>For this purpose - yes. In general both approaches are flawed, because not all >>>positions will be returned with exactly the same probability. RAND_MAX%960 != 0. >>>I know, that your method is the method advertized at many places. I don't like >>>it too much. It is possibly dangerous for some simulations. A better method is, >>>to find the largest value x <= RAND_MAX, for which x % 960 == 0. Then skip all >>>returns of rand() > x. Like in the following function: >> >>If you make a 64 bit MT generator, and do a modulus, the result will be >>indistinguisable from perfect as far as measurement is concerned (even after a >>quadrillion runs). It does not matter that 960 is not prime. > >Dann, I think you missed my point. It does not matter at all, wether 960 (or the >range you want to reduce the output of the PRNG to) is prime or not for my >argument. Take a typical C-lib-rand(), which has RAND_MAX of 2**15-1 (the >argument is still valid with higher RAND_MAX). 2**15-1 = 32767. Now you take the >output of the PRNG % 960 to get a number between 0 and 959. You will get the >number 0 more often, than the number 959. With 32768 calls, you will get 0 (and >many other numbers) on average 35 times, and 959 (and again many other numbers) >on average 34 times. 3% difference in probability. This is no problem really for >an FRC generator. It would make many simulations totally invalid. > >Using the multiplication method (as in your code, and as for example suggested >in the C-FAQ) has exactly the same flaw. Some numbers will on average be got 35 >times and other numbers 34 times out of 2**15 calls. This will exactly converge >to 34/35 (no fractions) after many calls. The method I suggested (and which I >used in "serious" simulations) does not have this problem. > >Your code (using C-Lib rand()) will suggest some FRC positions about 3% more >often, than other positions on many typical implementations. Using the idea of >my rand_range function, this problem is gone, with any PRNG, that even slightly >deserves this name. Typically, it is even faster. I will repeat, I think for >this application, it can be tolerated. With a 64 bit PRNG that returns an unsigned number between 0 and 0xffffffffffffffffffffffffffffffff will eliminate the problem that you describe. That is what I meant when I spoke of using the Mersenne Twister to create a 64 bit PRNG.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.