Perft(13) betting pool

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Daniel Shawul
Posts: 3437
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Mon Jul 11, 2011 12:50 pm

Did you try to run with different random number seeds to get a sampling distribution? That should help in reducing bias.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Perft(13) betting pool

Post by sje » Mon Jul 11, 2011 1:08 pm

ibid wrote:Hmmm. Lemme think about this for a month or so and I'll have an "estimate" for you. :)
Before announcing any result, give a few days' warning so that all may post their final predictions.

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.

User avatar
hgm
Posts: 22298
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Perft(13) betting pool

Post by hgm » Mon Jul 11, 2011 1:40 pm

Some different runs:

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
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.

Daniel Shawul
Posts: 3437
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Mon Jul 11, 2011 2:27 pm

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..

User avatar
hgm
Posts: 22298
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Perft(13) betting pool

Post by hgm » Mon Jul 11, 2011 2:59 pm

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.

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
I am running one now that starts sampling only after 6 ply.

User avatar
JuLieN
Posts: 2945
Joined: Mon May 05, 2008 10:16 am
Location: Nantes (France)
Contact:

Re: Perft(13) betting pool

Post by JuLieN » Mon Jul 11, 2011 3:05 pm

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.
"The only good bug is a dead bug." (Don Dailey)
Image [Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]

Daniel Shawul
Posts: 3437
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Mon Jul 11, 2011 3:12 pm

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.

User avatar
hgm
Posts: 22298
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Perft(13) betting pool

Post by hgm » Mon Jul 11, 2011 3:19 pm

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).

User avatar
JuLieN
Posts: 2945
Joined: Mon May 05, 2008 10:16 am
Location: Nantes (France)
Contact:

Re: Perft(13) betting pool

Post by JuLieN » Mon Jul 11, 2011 3:26 pm

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.
Here's how I did for the lower bound (NOTHING scientific, really ;) ) :

Code: Select all

01&#58;                     20 
02&#58;                    400 x20
03&#58;                  8,902 x22.255 (+2.255&#41;
04&#58;                197,281 x22.16  (-0.095&#41; (+2.16 )
05&#58;              4,865,609 x24.66  (+2.5  ) (+2.405&#41; +0.245
06&#58;            119,060,324 x24.47  (-0.19 ) (+2.31 )
07&#58;          3,195,901,860 x26.84  (+2.37 ) (+2.18 ) -0.13
08&#58;         84,998,978,956 x26.6   (-0.24 ) (+2.13 )
09&#58;      2,439,530,234,167 x28.7   (+2.1  ) (+1.86 ) -0.27
10&#58;     69,352,859,712,417 x28.43  (-0.27 ) (+1.83 )
11&#58;  2,097,651,003,696,806 x30.25  (+1.82 ) (+1.55 ) -0.28
12&#58; 62,854,969,236,701,747 x29.96  (-0.29 ) (+1.53 )
the x number is the branching factor between the previous and current number, the first (number) is the difference between the two latest branching factors, the second (number) is the difference between the two latest differences between the two latest branching factors, this last number showing a pair of twin numbers, and the occasional remaining number being the difference between the first number of one of those new pair and the last one of the previous pair. As this number seems to be decreasing by a double+0.01 margin each time, my hypothesis was that the new branching factor would be 29.96 + 1.53 - (0.28x2 + 0.01) = perft(12) x 30.92.

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 3:28 pm, edited 1 time in total.
"The only good bug is a dead bug." (Don Dailey)
Image [Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]

Daniel Shawul
Posts: 3437
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Mon Jul 11, 2011 3:27 pm

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 ?

Post Reply