Perft(13) betting pool

[Sven]

Congrats Daniel,
that was your CCC post no. 1000

Sven

[Daniel Shawul]

Oops, I should have made some sensational post then,like solving chess on 4x4!
[ego=on]Hmm.. may be I did make a discovery in my 100th post [ego=off]
cheers

[Ajedrecista]

Hi Daniel:

There is not a real formula: I visited François Labelle's web, and when I saw one of his graphs (the one with logarithmic scale that data suit in a line) one kind of inspiration came to me (not joking) and I started to calculate some ratios. The one that I finally used was:

{log[Perft(n)]}/n and {log[Perft(n+k)]}/(n+k)

I think I used these ratios because numbers are very close to 1 (I can handle them easily) and there are not huge jumps between values (I wanted some sort of 'stability'). If you read carefully, my first table starts with k = 2 instead k = 1... why? I do not remember: maybe k = 1 had no interesting (or obvious) trends... or maybe I deleted the numbers with k = 1 for some reason and I was so lazy for recalculate them again by hand. I just do not remeber.

As anyone can clearly see: there is not any theory behind this... at least I do not see it! It looks more like 'trial and error', or just luck, or simply watch and calculate... specially the last. But it gives some nice results anyway!

I realised that the issue of BFs of odd and even numbers was the same as in Table 2; but going with negative values of alpha(n) and beta(n), lower bound of this table is not anymore a bound (it is like a false bound, or intermediate bound, or auxiliary bound, if you want to see it just like that).

I think I have answered you. If you (or someone else) have more doubts about my strange method (which is very easy to have doubts), feel free to ask and I will try to answer the best I can.

Regards from Spain.

Ajedrecista.

[Daniel Shawul]

Hi Jesus (sorry for addressing you with the wrong name in my last post)

There is not a real formula: I visited François Labelle's web, and when I saw one of his graphs (the one with logarithmic scale that data suit in a line) one kind of inspiration came to me (not joking) and I started to calculate some ratios. The one that I finally used was:

{log[Perft(n)]}/n and {log[Perft(n+k)]}/(n+k)

Thanks. I am enjoying every one's method here so please don't take it personally if I come off as too inquisitive.
Yes that makes perfect sense. Infact at first I was not aware of the presences of odd-even effect which I thought was the effect of alpha-beta only.
But it definately needs to be taken care of as it clearly affect the perfect estimates.

As anyone can clearly see: there is not any theory behind this... at least I do not see it! It looks more like 'trial and error', or just luck, or simply watch and calculate... specially the last. But it gives some nice results anyway!

I realised that the issue of BFs of odd and even numbers was the same as in Table 2; but going with negative values of alpha(n) and beta(n), lower bound of this table is not anymore a bound (it is like a false bound, or intermediate bound, or auxiliary bound, if you want to see it just like that).

I think I have answered you. If you (or someone else) have more doubts about my strange method (which is very easy to have doubts), feel free to ask and I will try to answer the best I can.

Yes. I still have to read the pdf thoroughly. I will post here if I have more questions.

regards,
Daniel

[Daniel Shawul]

All estimates are unbiased.

My estimate is not the best because of bigger standard deviation but I basically use variables that can get some upper bound for perft or 0.

let denote U to be the upper bound for perft(n) based on multplication of upper bounds to perft(1)

U=U(1)*U(2)*....U(n) when U(1)=U(2)=20

Let denote P to be the probability that a sequence is translated to a legal game when we try to estimate perft(n) and have random sequence 1<=X(i)<=U(i) for 1<=i<=n.

every random game can be translated to a different sequence X(i) but not every sequence X(i) can be translated to a legal game

perft(n)=U*P because number of legal games is exactly the number of sequences that are translated to legal games.

our estimate based on a random sequence X(i) is 0 in case that the game is illegal and U in case that the game is legal.

The probability that the game is legal is P so the expected value of our estimate is exactly U*P that is perft(n) and if we do the average of many estimates we get the expected value for perft(n).

I thought about your method a little more and I came to the conclusion your method is biased at its current state. With a little modification of keeping counts of legal games that finished at each ply and multiplying and adding by that ply's upper bound perft value ,it can become unbiased in which case it becomes almost the same as Peter's method. Right now there is an assumption where all games should reach depth=20 for perft(20).
The reward given to each node at depth 13 is U(1) * U(2) ... * U(13) but to those games that finish at depth 10 , it should be U(1) * U(2) * ... U(10) , so we need a separate count for each of the ply's. The number of early mates is probably very low for pertf(13) on the initial positions but technically the method is biased.

eg.
1st ply: 10 moves with the first 2 having branches but the rest 8 moves do not have sub-trees. (extreme case just to make my point)
2nd ply: first move -> 2 branches
second move -> 3 branches
3rd ply: 2replys, 3replys,3replys,3replys,10replys consecutively for each 2nd ply move

U(1) = 10
U(2) = 3
U(3) = 10

Reward for legal games R = U(1) * U(2) * U(3) = 10 * 3 * 10 = 300;
My argument is the reward for the moves which did not reach ply 3 should have been R1 = 10. And a separate legal game count too.

I noticed that your method gives the same probabilties for all moves at the same ply, calculated by (1 / U(i)). So all ply 1 moves have 1/10, ply 2 have 1/3, and ply 3 have 1/10. So each path has the same probablity of 1/300 of being legal.

Total = 300 * ( 1/ 300 * (2 + 3 + 3 + 3 + 10)) + 300 * (1/10) * 8
= 21 + 240 = 261 !!
That 240 is due to those 8 root moves which do not reach ply 3. The actual perft is 21 + 8 = 29 i.e including all leaf nodes.
A correct estimator would do
Total = 21 + 10 * 1/10 * 8 = 21 + 8 = 29
So it is better in this case not to count games which do not reach the last ply to get an estimate of 21.

So with the correction it will start returning 1 (i.e Reward * probability) for each legal move at any ply and will become exactly like Peter's method. Maybe that will get us a perft estimate of 1.981e18. If intermediate games are counted as legal it will be an upper bound, and if not it is like pruning that part of the tree all in all.

@Sven, can you please modify Knockout and get us results if you don't mind ?

[Michel]

Anyway here is a method which beats around the bush instead of calculating the arithmetic mean directly. It is clearly inferior and only reason I am doing this is to finish off what I started. It gives an estimate 2x less than correct value for perft(20) and above..

I don't understand how this could possibly give an estimate that is
a factor of two off when the log normal assumption holds.

Do I understand correctly that the method is to take the average of the
logarithms and then use the log normal assumption to calculate
the mean? To do this you need the variance (of the log's) but this
you can also estimate from the sample.

[Daniel Shawul]

Right, but for perft(20) I am getting 2x smaller. For pert(13) as you can see is not far off the actual value 2.1e18. I can only say that with larger depth either more games need to be played and you can't be sure if it will be lognormal after that. Take perft(3) for instance we always have 20 moves at ply 1 and ply 2, so perft estimates are always 400 * nmoves_at_ply 3. So the distribution will be _normal_ for perft(3) since the product of the upper two plies have become a constant...
That is why I emphasized if the _assumption_ of lognormal holds. If it gives wrong results it means the assumption is violated by that much.
I will produce number for big perft values later.

Note that even doing this at the _root_ only can give bad results. That is calculate geometric average and then multiply by a factor to get arithmetic. I added a little more error from collecting the variance inside the tree as well.

perft 13
20 +/- 1.000 20 [1000000 : 1000000]
20 +/- 1.000 400 [1000000 : 1000000]
22.0222 +/- 1.151 8808.89 [1000000 : 1000000]
21.9018 +/- 1.171 192930 [1000000 : 1000000]
23.8293 +/- 1.218 4.59739e+006 [999961 : 1000000]
23.5948 +/- 1.254 1.08475e+008 [999909 : 1000000]
25.2617 +/- 1.275 2.74025e+009 [999834 : 1000000]
24.9833 +/- 1.309 6.84606e+010 [999734 : 1000000]
26.401 +/- 1.318 1.80743e+012 [999633 : 1000000]
26.1184 +/- 1.348 4.72072e+013 [999501 : 1000000]
27.3091 +/- 1.356 1.28919e+015 [999357 : 1000000]
27.0343 +/- 1.380 3.48522e+016 [999209 : 1000000]
28.0532 +/- 1.385 9.77716e+017 [999061 : 1000000]
SUM 25.6741 2.10595e+018
nodes 2.10595e+018
time 49.28 sec
perft 14
20 +/- 1.000 20 [1000000 : 1000000]
20 +/- 1.000 400 [1000000 : 1000000]
22.02 +/- 1.152 8808.01 [1000000 : 1000000]
21.9018 +/- 1.172 192911 [1000000 : 1000000]
23.8258 +/- 1.218 4.59626e+006 [999963 : 1000000]
23.5851 +/- 1.255 1.08403e+008 [999909 : 1000000]
25.2558 +/- 1.275 2.73781e+009 [999836 : 1000000]
24.9749 +/- 1.311 6.83763e+010 [999719 : 1000000]
26.3932 +/- 1.319 1.80467e+012 [999594 : 1000000]
26.119 +/- 1.348 4.71362e+013 [999447 : 1000000]
27.3182 +/- 1.354 1.28768e+015 [999305 : 1000000]
27.0225 +/- 1.383 3.47963e+016 [999156 : 1000000]
28.0339 +/- 1.388 9.75475e+017 [999014 : 1000000]
27.8093 +/- 1.405 2.71273e+019 [998873 : 1000000]
SUM 25.832 5.89122e+019
nodes 5.89122e+019
time 53.16 sec
perft 15
20 +/- 1.000 20 [1000000 : 1000000]
20 +/- 1.000 400 [1000000 : 1000000]
22.021 +/- 1.152 8808.38 [1000000 : 1000000]
21.9137 +/- 1.170 193025 [1000000 : 1000000]
23.8298 +/- 1.217 4.59974e+006 [999950 : 1000000]
23.6045 +/- 1.254 1.08575e+008 [999880 : 1000000]
25.2594 +/- 1.275 2.74253e+009 [999785 : 1000000]
24.9911 +/- 1.310 6.85387e+010 [999685 : 1000000]
26.3882 +/- 1.321 1.80861e+012 [999576 : 1000000]
26.1093 +/- 1.351 4.72216e+013 [999433 : 1000000]
27.3129 +/- 1.357 1.28976e+015 [999308 : 1000000]
27.0317 +/- 1.382 3.48644e+016 [999157 : 1000000]
28.0595 +/- 1.386 9.78278e+017 [999002 : 1000000]
27.7995 +/- 1.406 2.71956e+019 [998861 : 1000000]
28.6497 +/- 1.413 7.79148e+020 [998709 : 1000000]
SUM 26.029 1.70553e+021
nodes 1.70553e+021
time 57.50 sec
perft 20
20 +/- 1.000 20 [1000000 : 1000000]
20 +/- 1.000 400 [1000000 : 1000000]
22.0188 +/- 1.152 8807.53 [1000000 : 1000000]
21.9084 +/- 1.170 192959 [1000000 : 1000000]
23.8209 +/- 1.220 4.59644e+006 [999963 : 1000000]
23.5918 +/- 1.254 1.08438e+008 [999920 : 1000000]
25.2572 +/- 1.275 2.73885e+009 [999824 : 1000000]
24.9748 +/- 1.311 6.84023e+010 [999721 : 1000000]
26.3956 +/- 1.319 1.80552e+012 [999617 : 1000000]
26.1225 +/- 1.349 4.71647e+013 [999485 : 1000000]
27.3019 +/- 1.356 1.28769e+015 [999367 : 1000000]
27.0347 +/- 1.383 3.48122e+016 [999221 : 1000000]
28.0398 +/- 1.387 9.76128e+017 [999097 : 1000000]
27.801 +/- 1.407 2.71373e+019 [998973 : 1000000]
28.64 +/- 1.413 7.77211e+020 [998833 : 1000000]
28.431 +/- 1.427 2.20969e+022 [998683 : 1000000]
29.1389 +/- 1.435 6.43879e+023 [998525 : 1000000]
28.9198 +/- 1.451 1.86208e+025 [998338 : 1000000]
29.5119 +/- 1.460 5.49537e+026 [998177 : 1000000]
29.3032 +/- 1.475 1.61032e+028 [997995 : 1000000]
SUM 26.8049 3.66675e+028
nodes 3.66675e+028

And here is the result if everything is done only at the root. You can see
in case of pert(20) there is a big violation relatively. The arithmetic average calcualated directly is very close to Francois labelle's result and I am sure I will same number as his with more simulations. If I introduce the lognormal assumption i.e calculating geometric mean first and multiplying by a factor depending on the variance, it gives close estimates for most but can be far off the result in some cases..

perft 13
LOG: GEOM 9.66008e+017 ARTH 2.21648e+018
SUM 1.96934e+018
nodes 1.96934e+018
time 5.19 sec
perft 14
LOG: GEOM 2.69087e+019 ARTH 7.20053e+019
SUM 6.19855e+019
nodes 6.19855e+019
time 5.44 sec
perft 15
LOG: GEOM 7.6159e+020 ARTH 2.47877e+021
SUM 2.01053e+021
nodes 2.01053e+021
time 5.86 sec
perft 20
LOG: GEOM 1.52777e+028 ARTH 1.97179e+029
SUM 8.09444e+028
nodes 8.09444e+028
time 8.05 sec

[Daniel Shawul]

I improved a little using a different error propagation scheme. This time I propagated the geometric variance itself and got better results. Even better than the one calculated only at the root. I don't know why the latter gives such a bad result. One possible explanation is that the estimation of variance may be better if done at each ply and we have many short wins before depth=20 is reached. That should be the only reason because the median (geometric mean) is the same wherever you calculate it (i.e at root only or averaging each ply) so the culprit is the variance I think. Anyway using this modification perft(20) estimate is improved by about 50%.

Code: Select all

step a&b) same
step c) geom mean = exp(mean of log)
           total_variance += (variance of log / 2)
step d) nodes * exp(total_variance)

This is simpler than the previous and gives better estimate at least for perft(20). Note that the geometric std is now a multiply or divide */ instead of +/-.

perft 13
20 */ 1.000 20 [1000000 : 1000000]
20 */ 1.000 400 [1000000 : 1000000]
22.0222 */ 1.010 8808.89 [1000000 : 1000000]
21.9018 */ 1.012 192930 [1000000 : 1000000]
23.8293 */ 1.020 4.59739e+006 [999961 : 1000000]
23.5948 */ 1.026 1.08475e+008 [999909 : 1000000]
25.2617 */ 1.030 2.74025e+009 [999834 : 1000000]
24.9833 */ 1.037 6.84606e+010 [999734 : 1000000]
26.401 */ 1.039 1.80743e+012 [999633 : 1000000]
26.1184 */ 1.046 4.72072e+013 [999501 : 1000000]
27.3091 */ 1.047 1.28919e+015 [999357 : 1000000]
27.0343 */ 1.053 3.48522e+016 [999209 : 1000000]
28.0532 */ 1.054 9.77716e+017 [999061 : 1000000]
SUM 2.38949e+018
nodes 2.38949e+018
time 50.33 sec
perft 14
20 */ 1.000 20 [1000000 : 1000000]
20 */ 1.000 400 [1000000 : 1000000]
22.02 */ 1.010 8808.01 [1000000 : 1000000]
21.9018 */ 1.013 192911 [1000000 : 1000000]
23.8258 */ 1.020 4.59626e+006 [999963 : 1000000]
23.5851 */ 1.026 1.08403e+008 [999909 : 1000000]
25.2558 */ 1.030 2.73781e+009 [999836 : 1000000]
24.9749 */ 1.037 6.83763e+010 [999719 : 1000000]
26.3932 */ 1.039 1.80467e+012 [999594 : 1000000]
26.119 */ 1.045 4.71362e+013 [999447 : 1000000]
27.3182 */ 1.047 1.28768e+015 [999305 : 1000000]
27.0225 */ 1.054 3.47963e+016 [999156 : 1000000]
28.0339 */ 1.055 9.75475e+017 [999014 : 1000000]
27.8093 */ 1.059 2.71273e+019 [998873 : 1000000]
SUM 6.86977e+019
nodes 6.86977e+019
time 54.61 sec
perft 15
20 */ 1.000 20 [1000000 : 1000000]
20 */ 1.000 400 [1000000 : 1000000]
22.021 */ 1.010 8808.38 [1000000 : 1000000]
21.9137 */ 1.012 193025 [1000000 : 1000000]
23.8298 */ 1.019 4.59974e+006 [999950 : 1000000]
23.6045 */ 1.026 1.08575e+008 [999880 : 1000000]
25.2594 */ 1.030 2.74253e+009 [999785 : 1000000]
24.9911 */ 1.037 6.85387e+010 [999685 : 1000000]
26.3882 */ 1.040 1.80861e+012 [999576 : 1000000]
26.1093 */ 1.046 4.72216e+013 [999433 : 1000000]
27.3129 */ 1.048 1.28976e+015 [999308 : 1000000]
27.0317 */ 1.054 3.48644e+016 [999157 : 1000000]
28.0595 */ 1.055 9.78278e+017 [999002 : 1000000]
27.7995 */ 1.060 2.71956e+019 [998861 : 1000000]
28.6497 */ 1.062 7.79148e+020 [998709 : 1000000]
SUM 2.04737e+021
nodes 2.04737e+021
time 58.86 sec
perft 20
20 */ 1.000 20 [1000000 : 1000000]
20 */ 1.000 400 [1000000 : 1000000]
22.0188 */ 1.010 8807.53 [1000000 : 1000000]
21.9084 */ 1.012 192959 [1000000 : 1000000]
23.8209 */ 1.020 4.59644e+006 [999963 : 1000000]
23.5918 */ 1.026 1.08438e+008 [999920 : 1000000]
25.2572 */ 1.030 2.73885e+009 [999824 : 1000000]
24.9748 */ 1.037 6.84023e+010 [999721 : 1000000]
26.3956 */ 1.039 1.80552e+012 [999617 : 1000000]
26.1225 */ 1.046 4.71647e+013 [999485 : 1000000]
27.3019 */ 1.048 1.28769e+015 [999367 : 1000000]
27.0347 */ 1.054 3.48122e+016 [999221 : 1000000]
28.0398 */ 1.055 9.76128e+017 [999097 : 1000000]
27.801 */ 1.060 2.71373e+019 [998973 : 1000000]
28.64 */ 1.062 7.77211e+020 [998833 : 1000000]
28.431 */ 1.065 2.20969e+022 [998683 : 1000000]
29.1389 */ 1.067 6.43879e+023 [998525 : 1000000]
28.9198 */ 1.072 1.86208e+025 [998338 : 1000000]
29.5119 */ 1.074 5.49537e+026 [998177 : 1000000]
29.3032 */ 1.078 1.61032e+028 [997995 : 1000000]
SUM 5.31115e+028
nodes 5.31115e+028
time 80.98 sec

[Michel]

Perhaps even though the distribution looks log normal, it isn't in the tails?
Long tails can influence the mean.

[Daniel Shawul]

Perhaps even though the distribution looks log normal, it isn't in the tails?
Long tails can influence the mean.

That is probably the case. I usually do the plots around the mode (peak) which almost always shows a log-normal trend. If you recall, I mentioned that for perft 20, that the mean is very far from the mode or median, so I couldn't plot them together. With larger depths there is going to be shorter wins which can affect the lognormal shape. You would expect close to the mode (high frequency) the games are typical length of the perft.

I suspect it would be much worse for an LMR perft, because there only a few nodes reach depth=20 for perft 20. When a game ends prematurely, we are assuming a BF of 1 from then onwards, this can be really damaging to the lognormal curve. I should also add that Uri's method may give bad results for LMR perft too since it has problems when a game ends early.
Anyway, it is good to know what is happening behind but using log-normal assumption is not a good estimator.