Perft(13) betting pool

[Daniel Shawul]

I re-run my best version to get the variance of the second sequence of random numbers. I am running a test with a modification of Michel's formula that proportions the "defect" sqrt(mean^2 + variance) - mean of the child nodes to equal the visits ratio of child and parent nodes, but it is not looking good midway through the test.

Code: Select all

------------ 100 --------------
0 h2h3   1.809615e+015 +- 7.063162e+011 1.814779e+015 +- 7.198981e+011   3027428     32422
0 h2h4   2.614463e+015 +- 8.360739e+011 2.621821e+015 +- 8.541002e+011   4241078     55813
0 g2g3   2.493358e+015 +- 8.132253e+011 2.498488e+015 +- 8.276915e+011   4013273     51077
0 g2g4   2.212914e+015 +- 7.543553e+011 2.217805e+015 +- 7.664253e+011   3452672     37893
0 f2f3   1.550219e+015 +- 6.364387e+011 1.552914e+015 +- 6.472942e+011   2457536     20666
0 f2f4   2.044718e+015 +- 7.512627e+011 2.049625e+015 +- 7.656225e+011   3424443     38694
0 e2e3   7.137743e+015 +- 1.368108e+012 7.159585e+015 +- 1.407503e+012  11356290    234938
0 e2e4   7.242147e+015 +- 1.373962e+012 7.263448e+015 +- 1.413396e+012  11453439    240671
0 d2d3   4.582549e+015 +- 1.037340e+012 4.590385e+015 +- 1.051276e+012   6528737    106016
0 d2d4   6.308750e+015 +- 1.268903e+012 6.329049e+015 +- 1.302198e+012   9768843    191149
0 c2c3   2.745548e+015 +- 8.611873e+011 2.750965e+015 +- 8.755714e+011   4499837     63246
0 c2c4   3.112827e+015 +- 9.047247e+011 3.120779e+015 +- 9.216664e+011   4966148     72263
0 b2b3   2.402359e+015 +- 8.021260e+011 2.407173e+015 +- 8.187345e+011   3904298     48332
0 b2b4   2.406878e+015 +- 8.021316e+011 2.411027e+015 +- 8.166175e+011   3904241     49645
0 a2a3   1.821020e+015 +- 7.099334e+011 1.826291e+015 +- 7.239297e+011   3057890     33730
0 a2a4   2.566753e+015 +- 8.273012e+011 2.572809e+015 +- 8.435523e+011   4153008     54118
0 g1h3   2.127181e+015 +- 7.546554e+011 2.132300e+015 +- 7.679604e+011   3455289     39055
0 g1f3   2.698899e+015 +- 8.242595e+011 2.704493e+015 +- 8.369223e+011   4122065     50107
0 b1c3   2.725092e+015 +- 8.766602e+011 2.732710e+015 +- 8.951625e+011   4662829     65958
0 b1a3   2.096248e+015 +- 7.649992e+011 2.101248e+015 +- 7.792509e+011   3550656     41989
Perft 6.269928e+016 +- 4.059742e+012  6.285769e+016 +- 4.146412e+012
wasted 0.00

[Daniel Shawul]

I did some test runs with my tree growing perft implementation (ignoring the tree vs graph problem). The results are comparable to what has been posted here.

However when inspecting the generated tree it seems to be basically uniform (with the leafnodes distributed over the two largest depths).

This suggest that tree growing might be overkill for this problem. Just expanding
the tree to a certain depth and then using dynamically adapting weights
at the leaf nodes of the expanded sub-tree might be enough.

Why exactly ? Note that uniform is performing the worst in these tests. And you can not use weights when you have the true values of the means for each leaf node. In MC part the sub-tree sizes were guesses so using multipliers makes sense but not for the tree, unless I am missing your point. So expanding is essential to reduce the variance as it turned out even for this seemingly uniform tree. What happens inside the MC part is immaterial as you can use any of the light or heavy ones.

[Ajedrecista]

Hi everybody:

In other thread, Mr. Edwards has posted the result of four Perft(11) subtotals of the Perft(13) count:

Na3, a6 ---> 1,865,423,942,798,492
Nc3, a6 ---> 2,458,021,022,756,805
b3, a6 ---> 2,110,456,650,953,864
a3, a6 ---> 1,562,327,606,120,748

I hope I do not post typos... I think these subtotals are a good test for probing your Monte Carlo methods (or the methods you want) for seeing the accuracy of them. So far, I have seen some estimates (in other positions) which errors are below |0.01%| if I remember correctly. Since I do not know about these methods (I only 'play with the numbers' to get estimates of whole Perft(13) and my best is ~ (1.9804681 ± 0.0002024)e+18), I ask if you can estimate these four subtotals, please. Thanks in advance.

Regards from Spain.

Ajedrecista.

I have implemented the original method of Peter Österlund with uniform move selection probabilities (i.e. no weights, tree splitting, UCT, or other sophisticated methods ) in my C++ engine KnockOut. In my tests I always used fullDepth=0. For the four positions above I get the following perft(11) estimates, in each case after 5,000,000 random walks (where one random walk is one MC game for fullDepth=0):

Code: Select all

           1.Na3 a6      1.Nc3 a6      1.b3 a6       1.a3 a6
mean       1.866258E+15  2.456335E+15  2.113448E+15  1.562362E+15
true value 1.865424E+15  2.458021E+15  2.110457E+15  1.562328E+15
Error      8.340470E+11  1.686219E+12  2.990849E+12  3.415721E+1
Error%     0.0447%       0.0686%       0.1417%       0.0022%

[EDIT: the table above initially had wrong contents, fixed it.]

The last few digits may be rounded by Excel. I can't provide any standard deviation since I have not implemented the required functionality for that purpose, and do not store the sample values. Currently I only calculate the mean value of all samples.

Each of the four runs above took about 4 minutes on a Core2Duo 2.4GHz Laptop. I would guess this is quite slow.

For the initial position I get the following perft(12) result after 100,000,000 random walks (about 90 minutes):

Code: Select all

           perft(12) from initial pos
mean       62,836,664,667,437,300
true value 62,854,969,236,701,700
Error      1.830457E+13
Error%     0.0291%

I also ran a quick test of perft(13) with only 10,000,000 random walks (about 9 minutes) and got the following result:

Code: Select all

           perft(13) from initial pos
mean       1,981,794,079,918,660,000

Sven

Hi sven:

Thank you very much for testing it! The estimate on a3, a6 seems a little lucky but is astonishing anyway (in my screen the error shown is 3.4...e+1 but it should be 3.4...e+10). OTOH, I am surprised of the 'big' error in b3, a6 (bad luck IMO). Maybe more games are needed. I also appreciate so much your estimate on Perft(12): when I did my estimate some days ago using my strange method (playing with numbers and a couple of parameters) I got around 6.2877e+16 if I do not remember wrong (i.e. around +0.035% error), but remember that my 'method' is not empirical or serious, just imaginative... The advantage is that with my 'method' and only using the calculator of Windows I finish the estimate in around fifteen minutes or even less.

Your Perft(13) estimate seems a little higher than others I have read here (maybe 1e+8 games are better?). If I am right, the highest one I have read until you post this one was from Muller almost a month ago: (1.981375 ± 0.0002)e+18. Also, it is 'too' different of one you posted almost a month ago using Uri's method, and was ~ 1.979078e+18 (a little low in my opinion). Just a feeling, but I think Perft(13) will begin with 1.98 or 1.981...

Thanks for your work. Well done!

Regards from Spain.

Ajedrecista.

[Sven]

The estimate on a3, a6 seems a little lucky but is astonishing anyway (in my screen the error shown is 3.4...e+1 but it should be 3.4...e+10).

Also in my screen I edited the table manually and introduced that typo right before the 15 minutes timeout would have killed me ... Thanks for pointing that out. Unfortunately I cannot correct it in the posting itself.

OTOH, I am surprised of the 'big' error in b3, a6 (bad luck IMO). Maybe more games are needed.

Of course more games would be needed. And more time for me to run them

Your Perft(13) estimate seems a little higher than others I have read here (maybe 1e+8 games are better?).

Yes, as I wrote I only ran a 9 minutes quick test for that.

If I am right, the highest one I have read until you post this one was from Muller almost a month ago: (1.981375 ± 0.0002)e+18. Also, it is 'too' different of one you posted almost a month ago using Uri's method, and was ~ 1.979078e+18 (a little low in my opinion). Just a feeling, but I think Perft(13) will begin with 1.98 or 1.981...

We will know more in a couple of months when the calculation of Steven is done. Until then, most estimates being posted here are the result of some algorithm being run on a machine with usually almost no feelings I cannot tell yet what is high or low since the final result is unknown today.

Regarding previous perft(13) estimates I posted, 1.979078e+18 was not based on the method of Uri but was my personal value based on interpolation. In this post I published a table containing values based on the method of Uri for the first time (see column "estimatedPerft" there). The value for perft(13) posted there was quite inaccurate (1.997340e+18), as well as the others in that column, and should be ignored today. This was not the fault of the method itself, though, but of my implementation.

Sven

[Ajedrecista]

Hi Sven:

It is true: it was with Uri's method the result above 1.997e+18. I misunderstood it, because your corrected value was around 1.979078e+18. Sorry. You also have the reason when you say that it is impossible to say which estimate is 'high' and which 'low': I only say that your fast estimate seems a little high when comparing with other estimates. Here are some values without error bars (hope I remember well):

Yours (some weeks ago): ~ 1.979078e+18 (posted next to Uri's method estimate).
Mine: ~ 1.980468096e+18 (posted a lot of times, sorry).
Shawul: ~ 1.980549e+18 (when dividing into initial moves. Maybe UCT?).
Hair: ~ 1.98058e+18 (adjusting branching factor with a polynomial).
Österlund: ~ 1.98107567e+18 (nice method... maybe MC? I do not know).
Reinhard: ~ 1.98112e+18 (inverse interpolation).
Muller: ~ 1.981375e+18 (almost a month ago. I do not know the method).
Yours (today): ~ 1.981794e+18 (using 1e+7 games).

There are probably more estimates I have not posted: I remember one of Julien Marcel that was around 1.943e+18 or 1.953e+18, but it seems he did not take care of the 'odd - even effect', that is why I do not include in the list.

Another fact I realise is that your Perft(20) estimate is quite low when comparing with two different estimates:

Yours: ~ 7.677e+28 (6th of July).
Mine: ~ 8.3348e+28 (posted recently).
François Labelle: ~ 8.35e+28 (Labelle estimates seem good).

Labelle method pruning moves seems very similar with other methods here (this is why I write it seems good); my method is laughable as minimum, but I almost had the same result (in a very independent way), so maybe your estimates of 6th of July may be a little low (keep in mind that I am not saying your estimates are bad... in fact I think just the opposite!). It is curious for me that Labelle estimates and my own estimates (all from n = 13 to n = 20) differ in less than 0.2%, but the difference between our estimates is much higher (for n = 20 the difference is above 7%!).

Thanks for your effort and the effort of more people here.

Regards from Spain.

Ajedrecista.

[sje]

Four more draft 11 results:

Code: Select all

rnbqkbnr/1ppppppp/p7/8/8/7N/PPPPPPPP/RNBQKB1R w KQkq - 0 2 11 1882390155585040
rnbqkbnr/1ppppppp/p7/8/8/5N2/PPPPPPPP/RNBQKB1R w KQkq - 0 2 11 2373558610955814
rnbqkbnr/1ppppppp/p7/8/P7/8/1PPPPPPP/RNBQKBNR w KQkq - 0 2 11 2250225134770081
rnbqkbnr/1ppppppp/p7/8/1P6/8/P1PPPPPP/RNBQKBNR w KQkq - 0 2 11 2178802463490013

[Sven]

It is true: it was with Uri's method the result above 1.997e+18. I misunderstood it, because your corrected value was around 1.979078e+18.

Hi Jesús,

I appreciate your valuable comments. I would just like to point out, although it is not very important, that it was not a corrected value but a value obtained by a completely different method (a "Hocus Pocus" method) that I already used before implementing Uri's method, and that cannot compete with any other computiational method that has been presented here.

Another fact I realise is that your Perft(20) estimate is quite low when comparing with two different estimates:

Yours: ~ 7.677e+28 (6th of July).
Mine: ~ 8.3348e+28 (posted recently).
François Labelle: ~ 8.35e+28 (Labelle estimates seem good).

Yes, true. Now that I have the MC method presented by Peter Österlund available in my program I can calculate much better values for perft(20), like this one which I have done quickly right now (note, with very few games):

Code: Select all

perft(20) estimate (1,000,000 random walks in about 93 seconds): 8.3691e+28

For completeness I also let my program calculate perft(14) to perft(19):

Code: Select all

perft(14) estimate (1,000,000 random walks in about 62 seconds): 6.2176e+19
perft(15) estimate (1,000,000 random walks in about 67 seconds): 2.0121e+21
perft(16) estimate (1,000,000 random walks in about 72 seconds): 6.5239e+22
perft(17) estimate (1,000,000 random walks in about 78 seconds): 2.1782e+24
perft(18) estimate (1,000,000 random walks in about 83 seconds): 7.2156e+25
perft(19) estimate (1,000,000 random walks in about 88 seconds): 2.4620e+27

Still no standard deviation available. Some values are close to those of Labelle which is no surprise since I believe that the method of Peter Österlund that I implemented is basically the same as that of François Labelle.

Sven

[petero2]

"cost" is defined as sqrt(mean^2 + variance)

My conjecture is that the correct measure to decide splitting is what
I call the "defect".

sqrt(mean^2 + variance)-mean

I tested this method and a method that has the much simpler node expansion criteria "ply<5". This means that the in-memory tree will very quickly grow to a tree with exactly perft(5) leaf nodes. Here are the standard deviations I measured after 100e6 random walks:

Code: Select all

split condition   stddev
sqrt(m^2+var)     3.9826e+12
sqrt(m^2+var)-m   3.9805e+12
ply<5             3.9642e+12

I don't know if the differences are significant, but it does seem to support your idea that tree growing is overkill for this problem, at least when you start from the initial chess position. Maybe starting from a more tactical position would be different.

[Daniel Shawul]

I did some test runs with my tree growing perft implementation (ignoring the tree vs graph problem). The results are comparable to what has been posted here.

However when inspecting the generated tree it seems to be basically uniform (with the leafnodes distributed over the two largest depths).

This suggest that tree growing might be overkill for this problem. Just expanding
the tree to a certain depth and then using dynamically adapting weights
at the leaf nodes of the expanded sub-tree might be enough.

Why exactly ? Note that uniform is performing the worst in these tests. And you can not use weights when you have the true values of the means for each leaf node. In MC part the sub-tree sizes were guesses so using multipliers makes sense but not for the tree, unless I am missing your point. So expanding is essential to reduce the variance as it turned out even for this seemingly uniform tree. What happens inside the MC part is immaterial as you can use any of the light or heavy ones.

Here are results for depth=0 and depth=1 which I never calculated before with 100 mil simulations. Stddeve is about 8.6e12 so if we take the best estimate with UCT like algorithms of about 4e12 that will be about 5x i.e 500 million games will be required for the one that will start from depth=1 to get equal stddev with UCT like algorithms. That is big no doubt.

Code: Select all

------------ 100 --------------
0 h2h3   1.814487e+015 +- 1.039442e+012 1.814367e+015 +- 1.039395e+012   5000000         1
0 h2h4   2.618947e+015 +- 1.468325e+012 2.623877e+015 +- 1.474765e+012   5000000         1
0 g2g3   2.500112e+015 +- 1.375962e+012 2.498545e+015 +- 1.374372e+012   5000000         1
0 g2g4   2.218368e+015 +- 1.133485e+012 2.217433e+015 +- 1.131525e+012   5000000         1
0 f2f3   1.551644e+015 +- 7.799353e+011 1.552322e+015 +- 7.819099e+011   5000000         1
0 f2f4   2.049802e+015 +- 1.150282e+012 2.050630e+015 +- 1.151879e+012   5000000         1
0 e2e3   7.158432e+015 +- 3.915091e+012 7.160812e+015 +- 3.920251e+012   5000000         1
0 e2e4   7.265294e+015 +- 3.836694e+012 7.258460e+015 +- 3.828049e+012   5000000         1
0 d2d3   4.586423e+015 +- 2.137093e+012 4.588341e+015 +- 2.140378e+012   5000000         1
0 d2d4   6.325736e+015 +- 3.419007e+012 6.326205e+015 +- 3.423210e+012   5000000         1
0 c2c3   2.753399e+015 +- 1.510281e+012 2.751710e+015 +- 1.508416e+012   5000000         1
0 c2c4   3.116828e+015 +- 1.689435e+012 3.118422e+015 +- 1.692888e+012   5000000         1
0 b2b3   2.407769e+015 +- 1.354601e+012 2.406701e+015 +- 1.349449e+012   5000000         1
0 b2b4   2.415501e+015 +- 1.321356e+012 2.412522e+015 +- 1.317487e+012   5000000         1
0 a2a3   1.826585e+015 +- 1.064308e+012 1.824674e+015 +- 1.062721e+012   5000000         1
0 a2a4   2.571640e+015 +- 1.441037e+012 2.574241e+015 +- 1.445860e+012   5000000         1
0 g1h3   2.133571e+015 +- 1.174486e+012 2.133034e+015 +- 1.174665e+012   5000000         1
0 g1f3   2.706024e+015 +- 1.379953e+012 2.704017e+015 +- 1.376833e+012   5000000         1
0 b1c3   2.730606e+015 +- 1.593464e+012 2.731803e+015 +- 1.598079e+012   5000000         1
0 b1a3   2.103510e+015 +- 1.196824e+012 2.101463e+015 +- 1.193691e+012   5000000         1
Perft 6.285468e+016 +- 8.592524e+012  6.284958e+016 +- 8.593996e+012

[Daniel Shawul]

NT