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.
Sven
Posts: 3695
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Perft(13) betting pool

Post by Sven » Mon Jul 11, 2011 4:42 pm

JuLieN wrote: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

User avatar
hgm
Posts: 22581
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 4:51 pm

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
Posts: 3500
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Mon Jul 11, 2011 4:53 pm

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

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

Re: Perft(13) betting pool

Post by JuLieN » Mon Jul 11, 2011 4:59 pm

Sven Schüle wrote:
JuLieN wrote: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?
"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 ]

User avatar
hgm
Posts: 22581
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 5:28 pm

For reference I copied the results from that thread here:
Sven and Uri wrote:

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%

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

Re: Perft(13) betting pool

Post by JuLieN » Mon Jul 11, 2011 5:47 pm

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

Image
"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: 3500
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Mon Jul 11, 2011 5:49 pm

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

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

Re: Perft(13) betting pool

Post by JuLieN » Mon Jul 11, 2011 6:43 pm

Daniel Shawul wrote: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?
"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: 3500
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

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

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
Posts: 3500
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Mon Jul 11, 2011 6:55 pm

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)

Post Reply