Perft(13) betting pool

[Sven]

Here's another piece of perft(13):

(diagram) rnbqkbnr/1ppppppp/p7/8/8/2NP4/PPP1PPPP/R1BQKBNR b KQkq - 0 2

The perft(10) for the above is 165,358,518,306,919. How well does your estimator algorithm do with this?

I had to modify the "perft estimation" functionality of KnockOut to be able to deal correctly with arbitrary positions, initially there were some hard-coded hacks suitable for the starting position only. I also made some other improvements, one of them being fully legal move generation, currently used exclusively for perft-like processing. Other speedups were minor.

Now I get these results for the position above, still with the method as defined by Uri Blass:

Code: Select all

Your move: uperft 6
u[ 1] =  19
u[ 2] =  28
u[ 3] =  30
u[ 4] =  36
u[ 5] =  46
u[ 6] =  50
time = 0:00:39.25
Your move: uperftr 10 1000000
u[ 1] =  19
u[ 2] =  28
u[ 3] =  30
u[ 4] =  36
u[ 5] =  46
u[ 6] =  50
u[ 7] =  52
u[ 8] =  56
u[ 9] =  54
u[10] =  59
time = 0:00:44.25
Your move: setu 19 28 30 36 46 50 52 56 54 59
Your move: randgame 10 1000000
estimated perft(10) after    1000000             random games (13539 legal) = 165991922206516
time = 0:00:20.92
Your move: randgame 10 2000000
estimated perft(10) after    2000000             random games (27192 legal) = 166690758129832
time = 0:00:42.47
Your move: randgame 10 4000000
estimated perft(10) after    4000000             random games (54272 legal) = 166347470307852
time = 0:01:24.18
Your move: randgame 10 8000000
estimated perft(10) after    8000000             random games (108471 legal) = 166235595258725
time = 0:02:46.91
Your move: randgame 10 16000000
estimated perft(10) after   16000000             random games (215804 legal) = 165363582889500
time = 0:05:34.83
Your move: randgame 10 32000000
estimated perft(10) after   32000000             random games (432648 legal) = 165762041968583
time = 0:11:09.29
Your move: randgame 10 64000000
estimated perft(10) after   64000000             random games (864346 legal) = 165580053446887
time = 0:22:32.01

Not bad but I would need more games, obviously, to get a satisfying result, although the 16,000,000 games number turned out to be quite nice "by accident":

Code: Select all

165,991,922,206,516   1,000,000  0.383%
166,690,758,129,832   2,000,000  0.806%
166,347,470,307,852   4,000,000  0.598%
166,235,595,258,725   8,000,000  0.530%
165,363,582,889,500  16,000,000  0.003%
165,762,041,968,583  32,000,000  0.244%
165,580,053,446,887  64,000,000  0.134%

For the new readers, here some explanation of my new KnockOut commands (no "standardization candidates", definitely):

"uperft" calculates the exact perft(1) upper bounds for K plies.
"uperftr" estimates these by finding lower bounds for them, playing random games.
"randgame" uses the (calculated or estimated) perft(1) upper bounds to estimate perft(N) with the formula "(nLegalGames / nTotalGames) * u(1) * u(2) * ... * u(N)", also by playing random games.

It seems this method has been heavily improved by Peter Österlund and others but I think it is still interesting to see how other methods perform against the current "leader".

EDIT: Just a note, I did not take the time to repeat these measurements several times and calculate the variance. The numbers given above are just a "snapshot". But at least some kind of "closeness" to the real value can be seen there.

Sven

[petero2]

For the new readers, here some explanation of my new KnockOut commands (no "standardization candidates", definitely):

"uperft" calculates the exact perft(1) upper bounds for K plies.
"uperftr" estimates these by finding lower bounds for them, playing random games.
"randgame" uses the (calculated or estimated) perft(1) upper bounds to estimate perft(N) with the formula "(nLegalGames / nTotalGames) * u(1) * u(2) * ... * u(N)", also by playing random games.

It seems this method has been heavily improved by Peter Österlund and others but I think it is still interesting to see how other methods perform against the current "leader".

I think that it has not yet been established if my method (random walks with each valid move having the same probability) or HGMs method (constant move acceptance probability) is better in terms of standard deviation for a given number of sampled positions. Michels non-uniform sampling improvement of my method is very interesting, but as HGM pointed out, his method also has some of the advantages of the non-uniform sampling method.

Anyway, I think that all three methods are not too different from each other when it comes to standard deviation for a given number of samples. Therefore, I believe that in order to compute good estimates quickly, you should concentrate on making a super-fast implementation rather than having a complex algorithm. (Which pretty much rules out Java implementations.)

[sje]

And here's another with the largest perft(10) found so far:
[D]rnbqkbnr/1ppppppp/p7/8/3P4/N7/PPP1PPPP/R1BQKBNR b KQkq - 0 2
The perft(10) for the above is 180,064,345,219,110.

[sje]

And just as I posted the above, an even bigger perft(10) appeared:
[D]rnbqkbnr/1ppppppp/p7/8/8/N3P3/PPPP1PPP/R1BQKBNR b KQkq - 0 2
perft(10): 207,289,420,418,933

[Michel]

I think that it has not yet been established if my method (random walks with each valid move having the same probability) or HGMs method (constant move acceptance probability) is better in terms of standard deviation for a given number of sampled positions. Michels non-uniform sampling improvement of my method is very interesting, but as HGM pointed out, his method also has some of the advantages of the non-uniform sampling method.

One thing I proved _I think_ is that for a _uniform tree_ your method with uniform sampling is asymptotically better than HGM's method.

By better I mean that the product (nodes visited)*variance is smaller.

For a non uniform tree I don't know.

HGM provided some data for a real perft tree and my variance estimates (assuming a uniform tree) were somewhat bigger than the real variances.
This indicates that HGM's method adapts to a non-uniform tree, as
he predicted.

I am trying to implement non uniform sampling myself (using tree splitting)
but I have great difficulty making it efficient. It seems likely
that it will not be competitive with simpler implementations.

[Ajedrecista]

I have another Hocus Pocus estimation: 1.9803e+18

I ran a regression on the odd branching factors to obtain an overfitted equation, then used this equation to predict perft(13)/perft(12) = ~31.510522.

I am also deriving an estimate from sampling actual games. It will be much less accurate than Peter's and HGM's estimates, but may shed a little light on the subset of the total tree that has actually been played. For example, I have 37,643 unique positions at ply 12 derived from the rating lists. Mostly these positions come directly from the opening books and starting positions used over the years (most are 6 moves deep or more). The perft(1) calculation performed with these positions yielded an average of ~34.755, higher than the pretty certain estimate of ~31.5 from everybody's calculations (including François Labelle). Just a factoid.

Adam

I revise my guess to 1.98058e+18. This is based off of the following overfitted equation, which gives an estimate for the branching factor:

y = a + b*ln(x) + c*ln(x)^2 + d*ln(x)^3 + f*ln(x)^4 + g*ln(x)^5

a = 2.0000000000000000E+01
b = 1.1777189669120742E+00
c = 1.7001877870841087E-01
d = 4.6899880199910882E-01
f = 1.7030901119191894E-01
g = -7.1253155574964339E-02

I also checked samples from the FICS games Marcel van Kervinck has provided. Each sample consisted of ~ 50,000 unique positions at ply 12.
I then computed perft(1) for each position. The average perft(1) was greater than 34 for each sample.

Hello Adam:

I read your method for adjusting BF and it seems good to me, but I have a question for you: did you take the correct value of Perft(12) when estimating Perft(13)? If I multiplied Perft(12) by 31.510522 the result is: 1,980,592,890,942,413,606 (rounded up to the closer integer) and not 1.9803e+18; in your improved equation, if I multiply correctly (assuming x = 13 and BF ~ 31.51461183227663301843642539818) the result is: 1,980,849,957,224,344,645 (rounded up to the closer integer) and not 1.98058e+18.

If I try your numbers, it seems to me that you took a wrong value of Perft(12), such as 62,845,969,236,701,747 (more less) instead the correct one: 62,854,969,236,701,747 (i.e. swapping 4 and 5). Anyway, your Perft(13) estimates (both of them) are quite good. Your method is quite original, congratulations!

Please post if you find the error or if you feel I am wrong.

Regards from Spain.

Ajedrecista.

[Daniel Shawul]

I think I have found the problem with splitting! The problem is that if you continuously pick up the largest tree a sequence of random numbers give you and split it, in effect you are trying to minimize your highest score And that makes it biased and it will consistently underestimate the perft(12) result.

a) First solution I found is using another different sequence of random numbers in parallel. One sequence for picking which node to visit, and a second sequence for computing perft. So the task is doubled but it gives much much better results and clearly reveals the problem.

0 h2h3 1.807032e+015 +- 7.844448e+011 1.813317e+015 2137558 27321
0 h2h4 2.610309e+015 +- 9.042559e+011 2.619606e+015 3087534 44966
0 g2g3 2.488929e+015 +- 8.773753e+011 2.497981e+015 2943998 42114
0 g2g4 2.209316e+015 +- 8.065089e+011 2.217649e+015 2613357 34897
0 f2f3 1.548068e+015 +- 6.949835e+011 1.552570e+015 1831360 18997
0 f2f4 2.043637e+015 +- 8.360377e+011 2.051062e+015 2417353 29351
0 e2e3 7.112381e+015 +- 1.420095e+012 7.161074e+015 8411995 213903
0 e2e4 7.213908e+015 +- 1.420654e+012 7.262676e+015 8532081 220771
0 d2d3 4.568078e+015 +- 1.040591e+012 4.589070e+015 5403031 118938
0 d2d4 6.289855e+015 +- 1.302074e+012 6.325778e+015 7439234 179794
0 c2c3 2.740990e+015 +- 9.349984e+011 2.751346e+015 3242069 52478
0 c2c4 3.104858e+015 +- 9.649293e+011 3.118905e+015 3672419 62723
0 b2b3 2.399700e+015 +- 8.725562e+011 2.406374e+015 2838464 39994
0 b2b4 2.403905e+015 +- 8.688635e+011 2.412823e+015 2843442 42173
0 a2a3 1.817603e+015 +- 7.894154e+011 1.823257e+015 2150054 27592
0 a2a4 2.564210e+015 +- 8.940269e+011 2.572187e+015 3033021 44534
0 g1h3 2.124594e+015 +- 8.244063e+011 2.131486e+015 2513124 32703
0 g1f3 2.695361e+015 +- 8.709471e+011 2.704374e+015 3188174 45392
0 b1c3 2.716914e+015 +- 9.792112e+011 2.728829e+015 3213539 48167
0 b1a3 2.093079e+015 +- 8.559388e+011 2.101876e+015 2475811 32296
Perft 6.255273e+016 6.284224e+016
wasted 25.27

6.255269e+016 6.284214e+016
6.255248e+016 6.284225e+016
6.255249e+016 6.284237e+016
6.255212e+016 6.284195e+016
6.255219e+016 6.284199e+016
6.255255e+016 6.284216e+016
6.255264e+016 6.284178e+016

You can see that the first perft result was used for selection is much lower, while the second result is very close to the actual result. And this behaviors is the same for every other formula I have which the sub-tree size ratio in it. Unifrom sampling doesn't which is why it perfromst best. Then followed by UCT which visits moves exponentially more. This is the second least affected but it is affected anyway. It gives results close to 6.279e16.

b)A second solution I found was to expand the tree to a fixed size say to depth 3 and then pick nodes using a non-uniform algorithm. This tends to underestimate perft until all the nodes are visited enough, but after that it gives very good results, I think even better than uniform sampling expanded to depth 3. But we have to make enough iterations first.

With this changes all splitting versions have become competitive even when splitting is done non-stop.

Daniel

[Ajedrecista]

Hi Daniel:

I took a look on your new method:

http://talkchess.com/forum/viewtopic.ph ... 49&t=39678

The Perft count seems very good (it almost fits in my new interval (1.9804681 ± 0.0002024)e+18, which is a total surprise for me!). I have calculated (I hope there are not errors) the percentage of each one of twenty first possible moves in your sample and also did the same with Perft(11) and Perft(12) (finally, there is not an 'odd-even effect' in percentages, maybe only in BF's). More less the percentages are these:

Moves: %[Perft(11)] %[Perft(12)] %(Shawul's sample)

a3 2.879568278% 2.904139798% 2.792%
a4 4.054742232% 4.092857514% 4.147%
b3 3.790445879% 3.830269713% 3.662%
b4 3.833779233% 3.837974861% 3.771%
c3 4.397087674% 4.377817668% 4.144%
c4 4.939128103% 4.963636424% 5.003%
d3 7.239429777% 7.300932114% 6.943%
d4 10.08667334% 10.06586933% 10.809%
e3 11.49259878% 11.39230718% 12.158%
e4 11.71984731% 11.55618883% 12.495%
f3 2.460575949% 2.470542707% 2.26%
f4 3.259476824% 3.262699557% 3.203%
g3 3.945500296% 3.975182931% 3.67%
g4 3.526143586% 3.528380922% 3.307%
h3 2.865008494% 2.886435552% 2.836%
h4 4.135097853% 4.169312795% 3.905%
Na3 3.340918005% 3.34358958% 3.165%
Nc3 4.359712572% 4.345721062% 4.421%
Nf3 4.287321687% 4.302520666% 4.048%
Nh3 3.386944137% 3.393620795% 3.262%

SUM: ~ 100% ~ 100% 100.001%

Due to roundings: 100.001% instead of 100%; but the most important thing are the percentages of each initial move. It is noticeable that percentages of the same move regarding Perft(11) and Perft(12) are almost the same without exception. I have no reason to think that this issue will change in Perft(13). Although the percentages of Shawul's sample are quite good comparing with the other percentages, they are a little far from what is expected (IMO), but overall they give a great estimate. I think there is a general consensus on Perft(13) and, almost 100% sure: 1.979e+18 < Perft(13) < 1.982e+18.

So, in my meaningless opinion, Shawul's sample is quite accurate and he must run this method more than once... if he wants, obviously! This topic has brought very interesting estimates of everybody, so please keep the good work.

Regards from Spain.

Ajedrecista.

Hi again Daniel:

I calculated percentages of all the initial moves for all Perft cases (not only n = 11 and n =12) and I realise that the 'odd - even effect' also exists in these percentages. Here are the highlights:

a) 1.- c4 gives the more stable evolution of percentages when n grows (very close to 5% in all cases, but less than 5%). Its evolution is independent from the rest.
b) The cases with more than 5% (from n = 3) are (from highest to lowest): e4, e3, d4, d3 (d3 grows slowly in comparison with the other three initial moves). The rest are less than 5%.
c) e4, e3 and d4 grow 'heavily' from even to odd number of plies (2 to 3, 4 to 5, 6 to 7...) while decrease slightly from odd to even number of plies (3 to 4, 5 to 6, 7 to 8...).
d) The rest of cases not cited in c) (except c4) evolve just the opposite than c): slight increases from odd to even number of plies and a little more noticeable decreases from even to odd number of plies.

Once this behaviour is known, I must say (quoting myself in a former post) that Perft(13) percentage MUST change a little (the opposite I thought at first). Thereby, some percentages estimated by Daniel (in a Notepad some days ago) seem to be better than I expected (although not all) and IMHO it gives full credit to his estimate and the method too.

If anyone wants Excel files (there are two: one dividing into number of plies and the other splitting into all the initial moves) where I calculate this, feel free to ask me for them and I will try to upload them on Megaupload ASAP (they are in version 2003, so .xls instead of .xlsx and they are in Spanish although more than 95% are numbers). I think these percentages are useful when estimating Perft values dividing into initial moves, not only in Perft(13) but in higher plies. When Perft(13) will be known, maybe I will update results from n = 1, ..., 12 to n = 1, ..., 13 (just if I do not forget it!).

Regards from Spain.

Ajedrecista.

[Adam Hair]

I have another Hocus Pocus estimation: 1.9803e+18

I ran a regression on the odd branching factors to obtain an overfitted equation, then used this equation to predict perft(13)/perft(12) = ~31.510522.

I am also deriving an estimate from sampling actual games. It will be much less accurate than Peter's and HGM's estimates, but may shed a little light on the subset of the total tree that has actually been played. For example, I have 37,643 unique positions at ply 12 derived from the rating lists. Mostly these positions come directly from the opening books and starting positions used over the years (most are 6 moves deep or more). The perft(1) calculation performed with these positions yielded an average of ~34.755, higher than the pretty certain estimate of ~31.5 from everybody's calculations (including François Labelle). Just a factoid.

Adam

I revise my guess to 1.98058e+18. This is based off of the following overfitted equation, which gives an estimate for the branching factor:

y = a + b*ln(x) + c*ln(x)^2 + d*ln(x)^3 + f*ln(x)^4 + g*ln(x)^5

a = 2.0000000000000000E+01
b = 1.1777189669120742E+00
c = 1.7001877870841087E-01
d = 4.6899880199910882E-01
f = 1.7030901119191894E-01
g = -7.1253155574964339E-02

I also checked samples from the FICS games Marcel van Kervinck has provided. Each sample consisted of ~ 50,000 unique positions at ply 12.
I then computed perft(1) for each position. The average perft(1) was greater than 34 for each sample.

Hello Adam:

I read your method for adjusting BF and it seems good to me, but I have a question for you: did you take the correct value of Perft(12) when estimating Perft(13)? If I multiplied Perft(12) by 31.510522 the result is: 1,980,592,890,942,413,606 (rounded up to the closer integer) and not 1.9803e+18; in your improved equation, if I multiply correctly (assuming x = 13 and BF ~ 31.51461183227663301843642539818) the result is: 1,980,849,957,224,344,645 (rounded up to the closer integer) and not 1.98058e+18.

If I try your numbers, it seems to me that you took a wrong value of Perft(12), such as 62,845,969,236,701,747 (more less) instead the correct one: 62,854,969,236,701,747 (i.e. swapping 4 and 5). Anyway, your Perft(13) estimates (both of them) are quite good. Your method is quite original, congratulations!

Please post if you find the error or if you feel I am wrong.

Regards from Spain.

Ajedrecista.

Hi Jesus,

I can not look at my calculations at this time. But, the discrepancy that you found is that I did not use Perft(12) but rather the number games through ply 12 that did not end in checkmate. Actually, I probably should recalculate the BF using those numbers instead of the Perft values. BF_(n)=(Perft(n)-#games ending at ply n)/(Perft(n-1)-#games ending at ply n-1).

Adam

[Ajedrecista]

Hi Adam:

Thanks for clarifying it. If I take the numbers of François Labelle web, the result that you used is 62,846,608,144,842,788 (hoping no typos). Anyway, your estimates are enough good to be considered. I guess that your recalculation should give similar results. I have not checked your equation completely, but it seems that you adjust all known odd BF's with a polynomial using natural logarithms (x = 1, BF = 20 is easy to see, but I did not calculate the rest... well, BF(x = 13) yes). I also used the idea of adjusting a polynomial for estimating Perft directly (not BF's) but in a stranger way. In fact, our results are pretty close (you: 1.98058e+18; me: ~ (1.9804681 ± 0.0002024)e+18). Your last estimate is around +0.00565% than mine! Please keep the good work, as everybody here.

Regards from Spain.

Ajedrecista.