Perft(13) betting pool

[Daniel Shawul]

I still have to look into why Uri's method gives a biased estimate.

It may turn out that my attempt at proof is more suited to proving Uri's method is biased (if it actually is?). He uses an estimate of the branching factor at each ply to find the perft values by multiplying the BFs. If the expected branching factors for three plies are E(X),E(Y),and E(Z) then the perft value is E(X)E(Y)E(Z). He uses random numbers to see how many of them result in a legal game. So the product is multiplied by a fraction of legal games out of the series of games generated by series of random numbers..

Given E(XYZ) = E(X)E(Y)E(Z) Three independent branching factors
Prove that E(XYZD) = E(X)E(Y)E(Z)E(D) where D is dependent branching factor.
E(XYZD) = E(XYZ_1) + E(XYZ_2) + .... + E(XYZ_D)

Since he estimates E(XYZ_1) by E(X1)E(Y1)E(Z1) by a product and then sum will this still be unbiased?

[Uri Blass]

I still have to look into why Uri's method gives a biased estimate.

It may turn out that my attempt at proof is more suited to proving Uri's method is biased (if it actually is?). He uses an estimate of the branching factor at each ply to find the perft values by multiplying the BFs. If the expected branching factors for three plies are E(X),E(Y),and E(Z) then the perft value is E(X)E(Y)E(Z). He uses random numbers to see how many of them result in a legal game. So the product is multiplied by a fraction of legal games out of the series of games generated by series of random numbers..

Given E(XYZ) = E(X)E(Y)E(Z) Three independent branching factors
Prove that E(XYZD) = E(X)E(Y)E(Z)E(D) where D is dependent branching factor.
E(XYZD) = E(XYZ_1) + E(XYZ_2) + .... + E(XYZ_D)

Since he estimates E(XYZ_1) by E(X1)E(Y1)E(Z1) by a product and then sum will this still be unbiased?

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

[Daniel Shawul]

Ok but why don't you generate legal games only and estimate average BF for each ply. I guess this will be even more in accurate..

You start from the root , then make random move , count legal moves and save cumulative legal moves at each ply, and repeat until depth 13 or game ends before that depth is reached. Once we do say 1000 of those random games, we can calculate A(1), A(2) ... A(13) dividing cumulative counts at each ply by 1000 or whatever number of simulations managed to reach that ply. Then we multiply A(i)s and estimate perft(13). Any particular reason to introduce the proportion of legal games and use U(1)*U2)...U(13) instead ? As before A(1) = A(2) = 20 but the rest will have different values but much lower their corresponding U values.

[Uri Blass]

The reason is that I thought wrongly that it is a biased estimate.

see my last post in the first page of the thread of perft(20).

Note that I thought about this idea and even generated some example to check if I get an unbiased estimate before thinking about proving that I get an unbiased estimate
but did the mistake of assuming that every game has an equal probability when by choosing random moves not every game has an equal probability(unlike choosing random moves that may be illegal in part of the cases if the number in the sequence is bigger than the number of moves).

I understood my error only later when I read that people did exactly what you suggest to get a better estimate and only posted that we need a proof
for it and understood the proof.

[Adam Hair]

Your target should be to get at least the third one right, since it seems the first two i.e 1.9 is pretty much what everyone is suggesting (except for me ).
I did a branching factor estimate for the 20 moves separately but it was much lower. about 1.7 * 10^18. There is no point trying to estimate more than the first two significant digit with the EBF method.

I think we should also put our standard deviations to the contest.

Here's how I did for the lower bound (NOTHING scientific, really ) :

Code: Select all

01:                     20 
02:                    400 x20
03:                  8,902 x22.255 (+2.255)
04:                197,281 x22.16  (-0.095) (+2.16 )
05:              4,865,609 x24.66  (+2.5  ) (+2.405) +0.245
06:            119,060,324 x24.47  (-0.19 ) (+2.31 )
07:          3,195,901,860 x26.84  (+2.37 ) (+2.18 ) -0.13
08:         84,998,978,956 x26.6   (-0.24 ) (+2.13 )
09:      2,439,530,234,167 x28.7   (+2.1  ) (+1.86 ) -0.27
10:     69,352,859,712,417 x28.43  (-0.27 ) (+1.83 )
11:  2,097,651,003,696,806 x30.25  (+1.82 ) (+1.55 ) -0.28
12: 62,854,969,236,701,747 x29.96  (-0.29 ) (+1.53 )

the x number is the branching factor between the previous and current number, the first (number) is the difference between the two latest branching factors, the second (number) is the difference between the two latest differences between the two latest branching factors, this last number showing a pair of twin numbers, and the occasional remaining number being the difference between the first number of one of those new pair and the last one of the previous pair. As this number seems to be decreasing by a double+0.01 margin each time, my hypothesis was that the new branching factor would be 29.96 + 1.53 - (0.28x2 + 0.01) = perft(12) x 30.92.

As you can see this is plain hocus pocus math which reminds me how I tried to fool my math teacher in high school.

So we have three methods now:
- Monte Carlo,
- EBF,
- Hocus Pocus.

Which one will get the best estimation?

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

[Daniel Shawul]

The reason is that I thought wrongly that it is a biased estimate.

see my last post in the first page of the thread of perft(20).

Note that I thought about this idea and even generated some example to check if I get an unbiased estimate before thinking about proving that I get an unbiased estimate
but did the mistake of assuming that every game has an equal probability when by choosing random moves not every game has an equal probability(unlike choosing random moves that may be illegal in part of the cases if the number in the sequence is bigger than the number of moves).

I understood my error only later when I read that people did exactly what you suggest to get a better estimate and only posted that we need a proof
for it and understood the proof.

I looked at your example and it seems that it will be the exact method that is used by Peter here, because you do not use the proportion of legal moves anymore. Note that in your example you said perft(3) = 11 but that is only leaf node counts, if we add the internal nodes too it will be 18 i.e (11 + 5 + 2). The multiplication by the number of legal moves at each ply estimates this number. And from your calculation = 176/11 = 16 , so this estimate is close. They will equal each other with more number of games I think.More number of games than the number of leaf nodes is required whenever the tree is selective.

I now understand that your method does not actually estimate BF for each ply. We have an upper bound of perft(13) that we try to factor by monte-carlo simulation to give us a perft estimate. This is I think much better than what I am proposing, averaging BFs at each ply. I tested this idea and here is what I got.

First using the idea in your example (similar to Peter's I think):
After 1000 games, I get an estimate of 1.94 * e18 and and after 1 million games it got pretty close to 1.981e18 so that is a confirmation I think..
This method does not fall under those method which estimate BFs because those give very bad estimates as I explained below and I am not sure if they are unbiased at all.

Then I tried averaging branching factors at each ply 1000 times and then
multiplying those 13 branching factors once. This gave a bad estimate even after i increase the simulation to 10^7 which gave me around 1.3e18 and it remained there even after many more games. I think this method is biased at least practically.

BFs for 1st game (x1,x2,x3.....x13)
BFs for 2nd game (y1,y2,y3.....y13)
.
BFs for kth game (z1,z2,z3.....z13)

-----------------------------------------------------------------
If I do arithmetic mean of the products of BFs (nodes count approximation) then
perft(13) = 1/k(x1*x2...x13 + y1*y2*...y13 + z1*z2*...z13))
This gives very good estimates as I reported above.
---------------------------------------------------------------------
BF averaging:
BF1 = (x1 + y1 + .... z1) / k
BF2 = (x2 + y2 + .... z2) / k
..
BF13 = (x13 + y13 + .... z13) / k

Now if the product BF1*BF2*....*BF13 is used as an estimate will it be biased ? There are clearly some co-variance terms in there which make it
difficult to compare with the first method.
I found practically it is since it remains around 1.3e18 even after 10^7 random games, first 3 or 4 significant digits already converged.
--------------------------------------------------------------------
Then I tried using the geometric mean of BFs at each ply instead. The idea
is since the nodes count is a multiplication of BFs may be this is a better estimate.

BF1 = kth_root(x1*y1*....z1)
BF2 = kth_root(x2*y2*....z2)
...
BF13 = kth_root(x13*y13*....z13)

Then multiplying and rearanging BFs
BF1 * BF2* ... BF13 = kth_root(x1 * x2 *... x13) * kth_root(y1 * y2 * ... y13) *...* kth_root(z1 * z2 * .... z13)

This gives the geometric mean of the nodes count of the k samples. This is consistently lower than the arithmetic mean of nodes count used in the first case. Despite my expectation, it gave around 1e18 significantly lower than the correct value. But this may be unbiased estimate of the geometric mean of tree size. I know this is not useful though.
-------------------------------------------------------------------------

The method you are using now must fall under those methods which estimate perft by taking arithmetic mean of estimated tree sizes, since it gives very good approximations. May be you can estimate the BFs at each ply from the number of legal games that reached that ply, but it is clear it doesn't estimate BFs directly.

Edit:
I estimated perft of your example using the arithmetic and geometric averages.

arithmetic:
ply 1: (2 * 11) / 11 = 2
ply 2: (2 * 3 + 3 * 8) / 11 = 30 / 11
ply 3: (1 * 1 + 2 * 2 + 3 * 3 + 1 * 1 + 4 * 4) / 11 = 31/11
perft(3) = 15.37

geometric:
ply 1: (2 ^ 11) ^ (1/11) = 2
ply 2: (2^3 * 3^8) ^ (1/11) = 2.686
ply 3: (1^1 + 2^2 * 3^3 * 1^1 * 4^4) ^ (1/11) = 2.5339
perft(3) = 13.6

[Daniel Shawul]

I wrongly thought perft was total count in my previous post.
But here is a proof that the method does converge to the correct
perft value. And it is necessary to use uniform PRNG for all kinds of trees.
at every ply.
-----------------------
Here are the probabilities of each path

(1/2,1/2,1) = 1/4
(1/2,1/2,1/2) = 1/8
(1/2,1/2,1/2) = 1/8
(1/2,1/3,1/3) = 1/18
(1/2,1/3,1/3) = 1/18
(1/2,1/3,1/3) = 1/18
(1/2,1/3,1) = 1/6
(1/2,1/3,1/4) = 1/24
(1/2,1/3,1/4) = 1/24
(1/2,1/3,1/4) = 1/24
(1/2,1/3,1/4) = 1/24

Sum = 1

If we use a uniform PRNG at each ply then , then we can multiply our estimate with the path probabilities to estimate how many times that path is sampled. For instance in 1 million games, 50% should go to first move at ply 1 and another 50% to the other.
Now when we multiply with probabilities we get 1 for each of the eleven games.

2 * 2 * 1 * 1/4 = 1
2 * 2 * 2 * 1/8 = 1
.
.
2 * 3 * 4 * 1/24 = 1

It gives perft(3) = 11

----------------------
Numerical example:
If I play 11 million games, each path will get the following number of games in millions
1st path: 11/4
2nd path: 11/8
..
11th path: 11/24
So average = (11/4 * (2 * 2 * 1) + 11/8 * 8 .... 11/24 * 24) / 11
= (11 + 11 + ... + 11) / 11
= 11

[Uri Blass]

I wrongly thought perft was total count in my previous post.
But here is a proof that the method does converge to the correct
perft value. And it is necessary to use uniform PRNG for all kinds of trees.
at every ply.
-----------------------
Here are the probabilities of each path

(1/2,1/2,1) = 1/4
(1/2,1/2,1/2) = 1/8
(1/2,1/2,1/2) = 1/8
(1/2,1/3,1/3) = 1/18
(1/2,1/3,1/3) = 1/18
(1/2,1/3,1/3) = 1/18
(1/2,1/3,1) = 1/6
(1/2,1/3,1/4) = 1/24
(1/2,1/3,1/4) = 1/24
(1/2,1/3,1/4) = 1/24
(1/2,1/3,1/4) = 1/24

Sum = 1

If we use a uniform PRNG at each ply then , then we can multiply our estimate with the path probabilities to estimate how many times that path is sampled. For instance in 1 million games, 50% should go to first move at ply 1 and another 50% to the other.
Now when we multiply with probabilities we get 1 for each of the eleven games.

2 * 2 * 1 * 1/4 = 1
2 * 2 * 2 * 1/8 = 1
.
.
2 * 3 * 4 * 1/24 = 1

It gives perft(3) = 11

----------------------
Numerical example:
If I play 11 million games, each path will get the following number of games in millions
1st path: 11/4
2nd path: 11/8
..
11th path: 11/24
So average = (11/4 * (2 * 2 * 1) + 11/8 * 8 .... 11/24 * 24) / 11
= (11 + 11 + ... + 11) / 11
= 11

You are right and I already understood earlier that I rejected Peter's method for the wrong reason since my first reply to him.

I did not correct my mistake in the relevant thread but after seeing that Peter got a good estimate I looked at the relevant post again and I understood that the expected value of Peter's estimate is 11 and not a different number.

My mistake that caused me to get a different number was assuming that all games get equal probability.

You can see that I understood my error already in page 5 of this thread based on the last lines that I wrote at that time:

quote:
"Note that I found that the expected value of the multiplication on a random game is a biased estimate but practically we do not generate a random game by generating random moves and it seems at least based on one example that I tried that it is unbiased estimate but we need to prove it."

I exactly thought about the 11 example when I said based on one example we get unbiased estimate.

[Daniel Shawul]

You are right and I already understood earlier that I rejected Peter's method for the wrong reason since my first reply to him.

I did not correct my mistake in the relevant thread but after seeing that Peter got a good estimate I looked at the relevant post again and I understood that the expected value of Peter's estimate is 11 and not a different number.

My mistake that caused me to get a different number was assuming that all games get equal probability.

You can see that I understood my error already in page 5 of this thread based on the last lines that I wrote at that time:

quote:
"Note that I found that the expected value of the multiplication on a random game is a biased estimate but practically we do not generate a random game by generating random moves and it seems at least based on one example that I tried that it is unbiased estimate but we need to prove it."

I exactly thought about the 11 example when I said based on one example we get unbiased estimate.

Ok. Well it has cleared up some confusion for me anyway. Somehow I was under the impression that the PRNG should be biased based on sub-tree sizes to be an unbiased estimator for perft. I think it is just a lucky combination here that made the method unbiased with a unifrom PRNG. If it was another operation such as maximizing, minimizing or a product then it wouldn't have worked.

I am still pondering on averaging BFs and why it gives bad results. The distribution of the perft(13) samples seems to be log-normal. If we assume each BF is normally distributed, then the product i.e nodes count will be log-normally distirubuted. The confidence interval calculations will be different from normal distribution..

[Michel]

If it was another operation such as maximizing, minimizing or a product then it wouldn't have worked.

Max and min are unfortunately extremely tricky functions to treat statistically. Even if X_1,...,X_n are uniformly distributed (and independent), the distribution of max(X_1,....,X_n) and min(X_1,....,X_n) will be very skew.