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.
Post Reply
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Perft(13) betting pool

Post by sje » Sun Jul 10, 2011 3:29 pm

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.

User avatar
hgm
Posts: 22338
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Perft(13) betting pool

Post by hgm » Sun Jul 10, 2011 4:36 pm

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)

User avatar
hgm
Posts: 22338
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Perft(13) betting pool

Post by hgm » Sun Jul 10, 2011 5:33 pm

An improved estimate is:

Code: Select all

perft(13)= ca. 1978347153520590848 (912.710 sec)
But I guess for the official contest I will stick to the sub-minute value. :wink:

Daniel Shawul
Posts: 3437
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Sun Jul 10, 2011 6:32 pm

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.

User avatar
hgm
Posts: 22338
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Perft(13) betting pool

Post by hgm » Sun Jul 10, 2011 6:48 pm

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.

Daniel Shawul
Posts: 3437
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Sun Jul 10, 2011 6:58 pm

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

User avatar
hgm
Posts: 22338
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Perft(13) betting pool

Post by hgm » Sun Jul 10, 2011 8:56 pm

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
I correct the values a little bit to increase the accuracy, by counting at each level how many moves are accepted, and how many are pruned. As this is randomly decided on a per-move basis, it is never exactly 1/16 of the moves that is searched. So now I multiply the final count by the actual number, rather than 16. This shouldproduce a significant reduction of the standard deviation (at the expenseof a 25% slowdown).

So my bet is now on 1.979269e+18 .

ibid
Posts: 88
Joined: Mon Jun 13, 2011 10:09 am

Re: Perft(13) betting pool

Post by ibid » Mon Jul 11, 2011 6:46 am

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

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

Re: Perft(13) betting pool

Post by JuLieN » Mon Jul 11, 2011 7:57 am

My bet: 1,953,532,443,876,690,000
"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: 3437
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Mon Jul 11, 2011 12:41 pm

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.

Post Reply