Perft(13) betting pool

[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 ?

[Sven]

So we have three methods now:
- Monte Carlo,
- EBF,
- Hocus Pocus.

Which one will get the best estimation?

There is also a fourth method by Uri which is described and discussed in the Perft(20) thread.

Sven

[hgm]

OK, the one starting with 6 full-width ply is done, with the following results:

Code: Select all

perft( 6)=    1.190603e+08 ( 7.480 sec)   0.000000
perft( 7)=    3.195902e+09 (196.740 sec)   0.000000
perft( 8)= ca.8.499744e+10 (453.500 sec)  31.000333 (-0.0018%)
perft( 9)= ca.2.439623e+12 (673.320 sec)  31.003881 (+0.0038%)
perft(10)= ca.6.934676e+13 (870.170 sec)  30.995329 (-0.0088%)
perft(11)= ca.2.097743e+15 (1051.900 sec)  30.992257 (+0.0044%)
perft(12)= ca.6.285371e+16 (1225.810 sec)  31.013377 (-0.002%)
perft(13)= ca.1.981375e+18 (1392.530 sec)  31.019608

Based on the errors in the known values, I guess that 0.01% is a reasonable (95%) confidence interval. So I revise my bet to:

(1.981375 +/- 0.000200) * 10^18

[Daniel Shawul]

Yes so far Uri or HG are looking good. Me and Julien (if I may) are fillers
By the way you and also Juline seem to take into consideration the odd-even effect. Isn't that for alpha-beta only ? perft is min-max

[JuLieN]

So we have three methods now:
- Monte Carlo,
- EBF,
- Hocus Pocus.

Which one will get the best estimation?

There is also a fourth method by Uri which is described and discussed in the Perft(20) thread.

Sven

Oh, and your method is an Hocus Pocus variation I see, although based on what was the second (number) column in my table. Yet we don't agree on the 3rd digit!

And Uri's result is even above it.

If, in lack of time to devote to it, I took this as a game, I suspect that the problem is actually very deep and finding satisfactory prediction methods to it might be fruitful in a lot of domains.

Is all this pure chaos? Can it get tamed using statistics? Should we take into account the nature of chess when making our predictions, instead of focusing on pure numbers? What I mean is: we see various components contributing to the branch factor increase: lines openings, piece development, etc... Soon, the exchange of pieces will certainly reduce the average branch factor: my question is "isn't this so chess-specific that it disqualifies any numbers-analysis only method?" Is there a way to develop a better prediction method that would take into account both numbers and the chess game structure?

[hgm]

For reference I copied the results from that thread here:

Code: Select all

depth                           perft                  estimatedPerft  nRandomGames    dev%
    1                              20                              20     1,000,000   0.00%
    2                             400                             400     1,000,000   0.00%
    3                           8,902                           8,907     1,000,000   0.06%
    4                         197,281                         197,341     1,000,000   0.03%
    5                       4,865,609                       4,865,758     1,000,000   0.00%
    6                     119,060,324                     118,971,166     1,000,000  -0.07%
    7                   3,195,901,860                   3,209,904,114     1,000,000   0.44%
    8                  84,998,978,956                  85,542,969,699     1,000,000   0.64%
    9               2,439,530,234,167               2,432,591,226,863     1,000,000  -0.28%
   10              69,352,859,712,417              69,428,574,036,197     2,000,000   0.11%
   11           2,097,651,003,696,800           2,087,523,969,541,570     2,000,000  -0.48%
   12          62,854,969,236,701,700          63,242,213,290,599,300     2,000,000   0.62%
   13       1,979,078,380,667,300,000       1,997,340,520,734,860,000     8,000,000   0.92%
   14      61,737,614,603,214,200,000      61,805,223,274,842,600,000    16,000,000   0.11%
   15   2,001,643,963,368,810,000,000   1,990,053,614,855,530,000,000    64,000,000  -0.58%
   16  64,294,429,943,331,100,000,000  66,008,877,020,267,700,000,000   128,000,000   2.67%

[JuLieN]

And here's a little graph with the known branching factors for the first 12 plies, and a spline interpolation curve: