Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Did you try to run with different random number seeds to get a sampling distribution? That should help in reducing bias.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Perft(13) betting pool
Before announcing any result, give a few days' warning so that all may post their final predictions.ibid wrote:Hmmm. Lemme think about this for a month or so and I'll have an "estimate" for you.
Also, for any new perft claim, it's important to also release the 20 ply one subtotals and the 400 ply two subtotals. This gives proof of work and allows for an easier confirmation or challenge by others.
My perft(12) re-run on the new machine has spent some 51 hours wall time and has produced 13,609 of the 72,078 perft(8) subtotals (ca. 18.9%) and should finish in about nine days. After the 2011 ACCA Rapid event, this machine will start the perft(13) task. The old machine will continue to run it's perft(13) as a check on the new machine.
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
Some different runs:
The sampling noise is about what I would expect. The sampling started on the ~5M moves from the perft(4) positions, taking about 300k samples. So that should reduce the noise by about a factor sqrt(300k) = 550 compared to taking a single sample. And the standard deviation of a single sample is probably ~10 (30-50 moves), or 25%.So we would get 0.05%. But this repeats at each subsequent level, with a bit decreasing error, because the number of samples approximately doubles at each level. So that should converge to around 0.2%. Which is about what we see.
Code: Select all
perft(12)= ca.6.288624e+16 (39.190 sec) 15.003338
perft(12)= ca.6.280055e+16 (39.350 sec) 14.999360
perft(12)= ca.6.286105e+16 (39.050 sec) 14.997044
perft(12)= ca.6.271577e+16 (39.320 sec) 15.002318
perft(13)= ca.1.976485e+18 (73.920 sec) 15.001205
perft(13)= ca.1.980893e+18 (74.070 sec) 14.996600
perft(13)= ca.1.975184e+18 (73.510 sec) 14.993881
perft(13)= ca.1.977096e+18 (74.570 sec) 15.006476
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Yes 0.2% is good enough I think. If you want a stable 3rd significant digit, you can increase the sample further?
Maybe it is better to increase the depth where sampling starts to Perft(5). A single run to see how much that changes the mean..
Maybe it is better to increase the depth where sampling starts to Perft(5). A single run to see how much that changes the mean..
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
Well, that was basically the 912sec run I posted above. The problem with Monte-Carlo is that it is very difficult to get a high precision. The error only decreases as the square root of the number of samples. I guess the best way would be to tune the EBF to about 1, (by lowering the move acceptance rate to 1/32), so that each level has the same accuracy,nd no effort is wasted to get the accuracy for a higher level better while the result is already spoiled in a lower level.
I am running one now that starts sampling only after 6 ply.
Code: Select all
perft(12)= ca.6.287770e+16 (49.510 sec) 31.019958
perft(12)= ca.6.293158e+16 (49.260 sec) 30.994786
perft(12)= ca.6.280576e+16 (49.340 sec) 31.010861
perft(13)= ca.1.980212e+18 (54.700 sec) 31.030410
perft(13)= ca.1.981624e+18 (54.410 sec) 30.958658
perft(13)= ca.1.983417e+18 (54.470 sec) 31.031950
-
- Posts: 2949
- Joined: Mon May 05, 2008 12:16 pm
- Location: Bordeaux (France)
- Full name: Julien Marcel
Re: Perft(13) betting pool
I complete my estimation by adding a lower bound :
1,943,475,648,798,818,000 < perft(13) < 1,953,532,443,876,690,000
Those numbers were produced by using two different hypothesis to try to reduce the first 12 perft to a geometric progression. The final three zeros are just the result of my computers' calculator approximation.
1,943,475,648,798,818,000 < perft(13) < 1,953,532,443,876,690,000
Those numbers were produced by using two different hypothesis to try to reduce the first 12 perft to a geometric progression. The final three zeros are just the result of my computers' calculator approximation.
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Your target should be to get at least the third one right, since it seems the first two i.e 1.9 is pretty much what everyone is suggesting (except for me ).
I did a branching factor estimate for the 20 moves separately but it was much lower. about 1.7 * 10^18. There is no point trying to estimate more than the first two significant digit with the EBF method.
I think we should also put our standard deviations to the contest.
I did a branching factor estimate for the 20 moves separately but it was much lower. about 1.7 * 10^18. There is no point trying to estimate more than the first two significant digit with the EBF method.
I think we should also put our standard deviations to the contest.
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
Yeah, we could do it like Bridge:
you have to bid a standard error. If the actual result is outside the error range, you are dead. From the remaining entries, the one that bet the smallest standard deviation wins (even if he was not the closest).
you have to bid a standard error. If the actual result is outside the error range, you are dead. From the remaining entries, the one that bet the smallest standard deviation wins (even if he was not the closest).
-
- Posts: 2949
- Joined: Mon May 05, 2008 12:16 pm
- Location: Bordeaux (France)
- Full name: Julien Marcel
Re: Perft(13) betting pool
Here's how I did for the lower bound (NOTHING scientific, really ) :Daniel Shawul wrote:Your target should be to get at least the third one right, since it seems the first two i.e 1.9 is pretty much what everyone is suggesting (except for me ).
I did a branching factor estimate for the 20 moves separately but it was much lower. about 1.7 * 10^18. There is no point trying to estimate more than the first two significant digit with the EBF method.
I think we should also put our standard deviations to the contest.
Code: Select all
01: 20
02: 400 x20
03: 8,902 x22.255 (+2.255)
04: 197,281 x22.16 (-0.095) (+2.16 )
05: 4,865,609 x24.66 (+2.5 ) (+2.405) +0.245
06: 119,060,324 x24.47 (-0.19 ) (+2.31 )
07: 3,195,901,860 x26.84 (+2.37 ) (+2.18 ) -0.13
08: 84,998,978,956 x26.6 (-0.24 ) (+2.13 )
09: 2,439,530,234,167 x28.7 (+2.1 ) (+1.86 ) -0.27
10: 69,352,859,712,417 x28.43 (-0.27 ) (+1.83 )
11: 2,097,651,003,696,806 x30.25 (+1.82 ) (+1.55 ) -0.28
12: 62,854,969,236,701,747 x29.96 (-0.29 ) (+1.53 )
As you can see this is plain hocus pocus math which reminds me how I tried to fool my math teacher in high school.
So we have three methods now:
- Monte Carlo,
- EBF,
- Hocus Pocus.
Which one will get the best estimation?
Last edited by JuLieN on Mon Jul 11, 2011 5:28 pm, edited 1 time in total.
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Yes that will help those of us with a poor estimation strategy.
The sigma value can be left to the author to demonstrate his gambling skills But he has to show how he came up with the mean value through some kind of methodology.
What say you Steven ?
The sigma value can be left to the author to demonstrate his gambling skills But he has to show how he came up with the mean value through some kind of methodology.
What say you Steven ?