Place your estimate of perft(13) here so that it'll be easy to compare it with those of others when the actual value becomes known, probably sometime in early 2012.
I'll stick with my 2*10^18 figure as I'm too lazy to improve it.
Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
OK, I am also lazy, so my guess is this:
Code: Select all
hgm@hgm-laptop:~/qperft$ ./fakeperft 13
- - - - - - - - - - - -
- - - - - - - - - - - -
- - r n b q k b n r - -
- - p p p p p p p p - -
- - . . . . . . . . - -
- - . . . . . . . . - -
- - . . . . . . . . - -
- - . . . . . . . . - -
- - P P P P P P P P - -
- - R N B Q K B N R - -
- - - - - - - - - - - -
- - - - - - - - - - - -
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft( 1)= 20 ( 0.000 sec)
perft( 2)= 400 ( 0.000 sec)
perft( 3)= 8902 ( 0.000 sec)
perft( 4)= 197281 ( 0.010 sec)
perft( 5)= 4865609 ( 0.300 sec)
perft( 6)= ca. 118935680 ( 0.750 sec)
perft( 7)= ca. 3191629568 ( 1.510 sec)
perft( 8)= ca. 84735868928 ( 2.760 sec)
perft( 9)= ca. 2445589086208 ( 5.000 sec)
perft(10)= ca. 69392470638592 ( 8.980 sec)
perft(11)= ca. 2095210624450560 (16.570 sec)
perft(12)= ca. 62829565818437632 (30.500 sec)
perft(13)= ca. 1972589998431535104 (57.270 sec)
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
An improved estimate is:
But I guess for the official contest I will stick to the sub-minute value. ![Wink :wink:](./images/smilies/icon_wink.gif)
Code: Select all
perft(13)= ca. 1978347153520590848 (912.710 sec)
![Wink :wink:](./images/smilies/icon_wink.gif)
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
what did you do you ?
My guess is you filled up the pst table with average number of moves from the perfts you _can_ calculate. I will try my luck with that if you didn't already use that.
![Smile :)](./images/smilies/icon_smile.gif)
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
Just a Monte-Carlo sampling of the perft tree. After a certain ply (but not in horizon nodes) I only accept moves with the probability 1/N (i.e. I prune them with probability 1-1/N), and then multiply the total count by N for each ply where I do that. The results her use N=16. (In the supposedly more accurate one I started the pruning one level later.)
This required me to only slip one extra if statement into qperft (for the pruning), and fiddle a bit with the final printing of the count.
This required me to only slip one extra if statement into qperft (for the pruning), and fiddle a bit with the final printing of the count.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
I see. So you did an artifical reduction of the branching factor first and then correct the result (similar to progressive widening i think). I will try with estimating the branching factor on a per move basis. The problem with the opening position is that the branching factor increases rapidly so I am not sure it will be a good estimate..
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
Code: Select all
perft( 1)= 2.000000e+01 ( 0.000 sec) -nan
perft( 2)= 4.000000e+02 ( 0.000 sec) 0.000000
perft( 3)= 8.902000e+03 ( 0.000 sec) 0.000000
perft( 4)= 1.972810e+05 ( 0.010 sec) 0.000000
perft( 5)= 4.865609e+06 ( 0.300 sec) 0.000000
perft( 6)= ca.1.191103e+08 ( 0.910 sec) 14.981951
perft( 7)= ca.3.193653e+09 ( 1.900 sec) 15.016684
perft( 8)= ca.8.500709e+10 ( 3.590 sec) 15.006076
perft( 9)= ca.2.439202e+12 ( 6.440 sec) 14.990016
perft(10)= ca.6.939898e+13 (11.690 sec) 14.993228
perft(11)= ca.2.097027e+15 (21.220 sec) 15.010978
perft(12)= ca.6.284901e+16 (39.290 sec) 14.996416
perft(13)= ca.1.979269e+18 (74.120 sec) 14.995501
So my bet is now on 1.979269e+18 .
-
- Posts: 89
- Joined: Mon Jun 13, 2011 12:09 pm
Re: Perft(13) betting pool
Hmmm. Lemme think about this for a month or so and I'll have an "estimate" for you. :)
Seriously though, an update on the other perft 13 project...
I have finished computing the unique positions at 10 ply: 85,375,278,064 matching
François Labelle's result at http://wismuth.com/chess/statistics-positions.html --
we also agree on the number of uniquely realizable positions. For those keeping score,
the most frequent position at 10 ply is just the position after 1. e4 e5, which is reached
in 1,126,591 different 10 ply lines.
I have just finished recomputing perft 12 as a sanity check, and obtained the correct
result in 85326 seconds -- just short of a day. I have another project I'd like to run on
the machine over the next couple of days before I give it over to perft 13, but once it
gets started it should finish in about a month.
-paul
Seriously though, an update on the other perft 13 project...
I have finished computing the unique positions at 10 ply: 85,375,278,064 matching
François Labelle's result at http://wismuth.com/chess/statistics-positions.html --
we also agree on the number of uniquely realizable positions. For those keeping score,
the most frequent position at 10 ply is just the position after 1. e4 e5, which is reached
in 1,126,591 different 10 ply lines.
I have just finished recomputing perft 12 as a sanity check, and obtained the correct
result in 85326 seconds -- just short of a day. I have another project I'd like to run on
the machine over the next couple of days before I give it over to perft 13, but once it
gets started it should finish in about a month.
-paul
-
- Posts: 2949
- Joined: Mon May 05, 2008 12:16 pm
- Location: Bordeaux (France)
- Full name: Julien Marcel
Re: Perft(13) betting pool
My bet: 1,953,532,443,876,690,000
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Well EBF method sucks as expected.
EBF10 = 24.1139
EBF11 = 24.6177 +0.5038
EBF12 = 25.0257 +0.408
EBF13 = 25.3379 +0.3122 Assuming same amount of reduction
So perft(13) = 2*10^18
Probably an upper bound though?
....
I will improve in the coming month.
EBF10 = 24.1139
EBF11 = 24.6177 +0.5038
EBF12 = 25.0257 +0.408
EBF13 = 25.3379 +0.3122 Assuming same amount of reduction
So perft(13) = 2*10^18
Probably an upper bound though?
....
I will improve in the coming month.