Perft(13) betting pool

[Daniel Shawul]

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

[sje]

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.

[hgm]

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]

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

[hgm]

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.

[JuLieN]

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.

[Daniel Shawul]

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.

[hgm]

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

[JuLieN]

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

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?

[Daniel Shawul]

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 ?