Perft(13) betting pool

[sje]

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.

[hgm]

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)

[hgm]

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.

[Daniel Shawul]

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.

[hgm]

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]

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

[hgm]

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]

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

[JuLieN]

My bet: 1,953,532,443,876,690,000

[Daniel Shawul]

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.