Perft(13) betting pool

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

[Daniel Shawul]

Hopefull again after seeing Uri's result 1.997*10^18 is more closer to my value 2*10^18 than to yours. Sven's estimate however is close to yours.
All that I have to do now is bet smart with the standard deviation. Are you sure you like your sd ?

[JuLieN]

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

If you look at the graph, you'll see that there is an odd-even effect. Now where does it come from? From the fact that black is a ply late compared with white? Is this another evidence that white has an advantage by starting the game? Will this effect eventually disappear after a while?

And by the way, would the interpolation curve allow us to determine the medium duration of a game, or would it change its general shape with time instead of being symetrical?

[Daniel Shawul]

Oops I made a mistake in the code which added a BF of 0.15 that was intended to be used for the move by move method. My estimate now is magnitudes below 2

[Daniel Shawul]

It could very well be the case. Mobility increases with each move in the opening so I will not be surprised if that is the case. Btw your plot is for an even ply (12), may be it will be different for ply(11)