Author: Dieter Buerssner
Date: 14:31:33 08/13/03
Go up one level in this thread
On August 13, 2003 at 13:44:16, Erik Bergren wrote:
It is a nice and interesting discussion for me. I hope, it is not getting too
far off topic.
>Robert Hyatt's Random number generator
>worked well ("rather decent") for that. You can find it
>in the following letter.
Sure. But before using the pseudo random number generator of Crafty for
important simulations, you should read:
http://www.evensen.org/marsaglia/keynote.ps
Look at the passages about Lagged Fibonacci PRNG, and about duplicate birthday
spacing test. (THe Crafty PRNG is a Lagged Fibonacci PRNG suggested by Knuth).
>Here is the Theoretical and experimental data produced by
>the programs above:
>
>
> (After 10,000,000 matches):
> (With Probability Ratio of .6237 for White to win.)
>Number of White Theoretical Experimental Experimental
>Wins per outcome outcome outcome
>each match(="n"): for "n": for "100-n": for "n"
>==========================================================================
>50 821699 (823153) 823153
>51 804525 805157 803365
>52 755117 753009 756603
>53 679385 680519 678344
>54 585885 587044 585463
>55 484234 482899 484001
>56 383517 383030 383595
>57 291021 291419 290359
>58 211537 211395 211549
>59 147254 146946 147571
>60 98140 98336 98541
>61 62601 63001 63208
>62 38206 38150 38069
>63 22301 22647 22274
>64 12444 12388 12268
>65 6635 6534 6614
>66 3378 3295 3392
>67 1642 1662 1607
>68 761 757 735
>69 336 336 334
>70 142 153 129
>71 57 51 52
>72 22 16 21
>73 8 11 8
>74 3 1 1
>75 1 0 1
>76 0 0 0
>(76 to 100 are all zero)
BTW. This could be a typical test for the quality of a PRNG. You can compare the
theoretical and empirical data with some chi square statistics, and see, whether
it fits or not. I think, many typical library rands() would already fail this
simple test. The Crafty PRNG seems good enough for this. I wrote a similar
program (I posted it here some time ago), and no surprise, I get similar
results:
C:\e\dcrand>cmatch 100 6237 3763 0 10000000
Result of chess matches between equal opponents
White wins 62.4%, black 37.6% and 0.0% draws
A match of 100 games was simulated by 10000000 Monte Carlo tries
result probability <= this > this
50.0 - 50.0 ( 50.0%): 8.23294% 8.23294% 91.76706%
51.0 - 49.0 ( 51.0%): 16.07968% 24.31262% 75.68738%
52.0 - 48.0 ( 52.0%): 15.10048% 39.41310% 60.58690%
53.0 - 47.0 ( 53.0%): 13.58176% 52.99486% 47.00514%
54.0 - 46.0 ( 54.0%): 11.71276% 64.70762% 35.29238%
55.0 - 45.0 ( 55.0%): 9.68426% 74.39188% 25.60812%
56.0 - 44.0 ( 56.0%): 7.67636% 82.06824% 17.93176%
57.0 - 43.0 ( 57.0%): 5.82292% 87.89116% 12.10884%
58.0 - 42.0 ( 58.0%): 4.23536% 92.12652% 7.87348%
59.0 - 41.0 ( 59.0%): 2.93463% 95.06115% 4.93885%
60.0 - 40.0 ( 60.0%): 1.96364% 97.02479% 2.97521%
61.0 - 39.0 ( 61.0%): 1.25256% 98.27735% 1.72265%
62.0 - 38.0 ( 62.0%): 0.76831% 99.04566% 0.95434%
63.0 - 37.0 ( 63.0%): 0.44484% 99.49050% 0.50950%
64.0 - 36.0 ( 64.0%): 0.24875% 99.73925% 0.26075%
65.0 - 35.0 ( 65.0%): 0.13298% 99.87223% 0.12777%
66.0 - 34.0 ( 66.0%): 0.06737% 99.93960% 0.06040%
67.0 - 33.0 ( 67.0%): 0.03335% 99.97295% 0.02705%
68.0 - 32.0 ( 68.0%): 0.01507% 99.98802% 0.01198%
69.0 - 31.0 ( 69.0%): 0.00693% 99.99495% 0.00505%
70.0 - 30.0 ( 70.0%): 0.00319% 99.99814% 0.00186%
71.0 - 29.0 ( 71.0%): 0.00122% 99.99936% 0.00064%
72.0 - 28.0 ( 72.0%): 0.00046% 99.99982% 0.00018%
73.0 - 27.0 ( 73.0%): 0.00013% 99.99995% 0.00005%
74.0 - 26.0 ( 74.0%): 0.00003% 99.99998% 0.00002%
75.0 - 25.0 ( 75.0%): 0.00002% 100.00000% 0.00000%
CPU-time 38.104 s wall 39, PRNG was called 1e+009 times, 0.03810 us/PRN
The probability column added together your n and 100-n (which after all have the
same probability). The idea of the later colums was to get a feeling for how
probable a outcome is in such a match (Is my new version better?)
When adding draw, the distribution becomes more narrow. For the same ratio of
white/black wins, but 50% draw probability, I get:
C:\e\dcrand>cmatch 100 6237 3763 10000 10000000
Result of chess matches between equal opponents
White wins 31.2%, black 18.8% and 50.0% draws
A match of 100 games was simulated by 10000000 Monte Carlo tries
result probability <= this > this
50.0 - 50.0 ( 50.0%): 5.71516% 5.71516% 94.28484%
50.5 - 49.5 ( 50.5%): 11.32289% 17.03805% 82.96195%
51.0 - 49.0 ( 51.0%): 10.99712% 28.03517% 71.96483%
51.5 - 48.5 ( 51.5%): 10.43432% 38.46949% 61.53051%
52.0 - 48.0 ( 52.0%): 9.72800% 48.19749% 51.80251%
52.5 - 47.5 ( 52.5%): 8.85531% 57.05280% 42.94720%
53.0 - 47.0 ( 53.0%): 7.90431% 64.95711% 35.04289%
53.5 - 46.5 ( 53.5%): 6.91111% 71.86822% 28.13178%
54.0 - 46.0 ( 54.0%): 5.94428% 77.81250% 22.18750%
54.5 - 45.5 ( 54.5%): 4.97376% 82.78626% 17.21374%
55.0 - 45.0 ( 55.0%): 4.09692% 86.88318% 13.11682%
55.5 - 44.5 ( 55.5%): 3.28789% 90.17107% 9.82893%
56.0 - 44.0 ( 56.0%): 2.59457% 92.76564% 7.23436%
56.5 - 43.5 ( 56.5%): 2.01030% 94.77594% 5.22406%
57.0 - 43.0 ( 57.0%): 1.52500% 96.30094% 3.69906%
57.5 - 42.5 ( 57.5%): 1.12471% 97.42565% 2.57435%
58.0 - 42.0 ( 58.0%): 0.81504% 98.24069% 1.75931%
58.5 - 41.5 ( 58.5%): 0.58414% 98.82483% 1.17517%
59.0 - 41.0 ( 59.0%): 0.40460% 99.22943% 0.77057%
59.5 - 40.5 ( 59.5%): 0.27682% 99.50625% 0.49375%
60.0 - 40.0 ( 60.0%): 0.18428% 99.69053% 0.30947%
60.5 - 39.5 ( 60.5%): 0.11966% 99.81019% 0.18981%
61.0 - 39.0 ( 61.0%): 0.07462% 99.88481% 0.11519%
61.5 - 38.5 ( 61.5%): 0.04639% 99.93120% 0.06880%
62.0 - 38.0 ( 62.0%): 0.02872% 99.95992% 0.04008%
62.5 - 37.5 ( 62.5%): 0.01692% 99.97684% 0.02316%
63.0 - 37.0 ( 63.0%): 0.01040% 99.98724% 0.01276%
63.5 - 36.5 ( 63.5%): 0.00569% 99.99293% 0.00707%
64.0 - 36.0 ( 64.0%): 0.00327% 99.99620% 0.00380%
64.5 - 35.5 ( 64.5%): 0.00187% 99.99807% 0.00193%
65.0 - 35.0 ( 65.0%): 0.00108% 99.99915% 0.00085%
65.5 - 34.5 ( 65.5%): 0.00044% 99.99959% 0.00041%
66.0 - 34.0 ( 66.0%): 0.00020% 99.99979% 0.00021%
66.5 - 33.5 ( 66.5%): 0.00009% 99.99988% 0.00012%
67.0 - 33.0 ( 67.0%): 0.00006% 99.99994% 0.00006%
67.5 - 32.5 ( 67.5%): 0.00003% 99.99997% 0.00003%
68.0 - 32.0 ( 68.0%): 0.00002% 99.99999% 0.00001%
68.5 - 31.5 ( 68.5%): 0.00001% 100.00000% 0.00000%
CPU-time 38.585 s wall 39, PRNG was called 1e+009 times, 0.03859 us/PRN
Perhaps, one can do this analytically as well (it should become more difficult,
than the binominal distribution).
I used Mersenne Twister as PRNG for the above simulations, and a carefully
crafted "flip()" equivalent.
I have written similar simple simulations about unequal opponents, to give me an
idea of the probability of outcomes. For example you have a longer match vs. one
opponent (who will in general be of different strength), and want to judge a new
match result.
>The probability ( or "strangeness") of a computer
>(randomized in some way to prevent bad ruts,
> (if possible?))
>winning 85 (or higher) out of 100 games
>from one of equal strength
>(or against an identical computer, say) ,
>and assuming that the "Probability Ratio"
>for White to win is .6237,
>is (certainly) equal to
>
>
>4.99769099966...*10^-14.
Or practically much lower even, when we consider draws.
Of course, we assume, that the games are independant (no learning).
>I found that thanks to help from:
You are extremely polite!
Rémi's program is very interesting, and he has written a nice article about it.
Regards,
Dieter
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.