Perft(13) betting pool

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Uri Blass
Posts: 10216
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: Perft(13) betting pool

Post by Uri Blass »

Michel wrote:Yes probably with some care Uri's method can be made to perform similarly as Peter's method.

But why would one go through this trouble, as Peter's method is trivial to implement?

Using a conceptually and practically more complicated method would only make sense if it gave some kind of benefit. I don't see this in this case.
I posted my method before Peter.
I also considered Peter's method at that time but
I simply thought for a wrong reason that Peter's method does not work and gives a biased estimate because I made the wrong assumption that all the games have equal probability when it is not the case with random moves.
Michel
Posts: 2271
Joined: Mon Sep 29, 2008 1:50 am

Re: Perft(13) betting pool

Post by Michel »

I posted my method before Peter.
Sorry I hope you didn't interprete my comment as personal criticisism! You were the first to point out that it is feasible to use Monte Carlo methods to accurately estimate Perft(13).

That afterwards a simpler method (in my opinion) was found does in no way diminish the value of the initial idea.
User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 11:08 am
Location: Klein-Gerau, Germany

Re: Perft(13) betting pool

Post by smrf »

Here I publish my final calculation done with correct known perft numbers and inverse interpolation (for odd levels only):

Image
User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 11:08 am
Location: Klein-Gerau, Germany

Re: Perft(13) betting pool

Post by smrf »

Now I added values for even levels and refined the calculation for odd numbers by the even calculation's last term:

Image
Michel
Posts: 2271
Joined: Mon Sep 29, 2008 1:50 am

Re: Perft(13) betting pool

Post by Michel »

I did a quick variance computation for the non uniform Peter method.

It seems that to get the smallest variance, moves that reduce the
tree should be selected less frequently (and of course to get an unbiased
estimator the pay off should be the inverse of the selection probabilty as in HGM's post).

I think this applies to captures since these reduce the tree permanently
(and not all captures are equal in this respect).

There is an exact formula for the optimal weights but since the terms
are unknown it is not clear if this is useful (although one could use heuristics to estimate the terms).

For the record: if one wants to estimate x_1+...+x_n and
one has unbiased estimators X_i for x_i with variance sigma_i^2 then
if I calculated correctly one should choose X_i with probability

p_i=mu sqrt(x_i^2+sigma_i^2)

where mu should be adjusted such that the sum of the p_i is 1.

Perhaps somebody versed in statistics can double check this?
Daniel Shawul
Posts: 4185
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Perft(13) betting pool

Post by Daniel Shawul »

I did a quick variance computation for the non uniform Peter method.

It seems that to get the smallest variance, moves that reduce the
tree should be selected less frequently (and of course to get an unbiased
estimator the pay off should be the inverse of the selection probability as in HGM's post).

I think this applies to captures since these reduce the tree permanently
(and not all captures are equal in this respect).

There is an exact formula for the optimal weights but since the terms
are unknown it is not clear if this is useful (although one could use heuristics to estimate the terms).

For the record: if one wants to estimate x_1+...+x_n and
one has unbiased estimators X_i for x_i with variance sigma_i^2 then
if I calculated correctly one should choose X_i with probability

p_i=mu sqrt(x_i^2+sigma_i^2)

where mu should be adjusted such that the sum of the p_i is 1.

Perhaps somebody versed in statistics can double check this?
Since we are using pure Monte carlo approach with no "real tree", our only option is a static move selection scheme. So one can for example give lesser weight to captures as they usually lead to narrow sub-trees unrepresentative of the perft tree.

It should certainly be possible to get to the perft estimate faster with a biased move selection. But we should keep in mind that here we are mainly concerned about accuracy of estimate more than speed. I think in about 1 million games three significant digits will be secured. The faster we try we make the more unreliable the result will be. If you look at my result with LMR perft, the biased estimator gave a better result than the unbiased one. Then I thought wrongly that it was better. But the reality was non-uniform trees require much more number of games than uniform perft like trees to get better estimates.. I don't know how many games will actually be required because Peter got also 30% off result after so many games, but in theory it should converge to the correct result. I am still curious to know how many more games will be required..

Btw for tree search speed is more important than accuracy. For instance UCT tree search with a plain uniform PRNG is proven to give exact results as alpha-beta search with infinite number of games, since it is an unbiased estimator. But in practice the biased approach is prefered because it gives better results with lower number of games.
Daniel Shawul
Posts: 4185
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Perft(13) betting pool

Post by Daniel Shawul »

Hi Reinhard
Could you please explain the meanings of each column? I am remotely familiar with inverse interpolation but I am not sure what is happening here.
Also what is the reason behind taking the logarithm of the perft estimate.

thanks
User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 11:08 am
Location: Klein-Gerau, Germany

Re: Perft(13) betting pool

Post by smrf »

Well, Daniel,

a) switching to logarithm is nothing else as to recognize perft(x) as a mainly exponential function, after which inter-/extrapolation is more appropriate.

b) doing this separately for even and odd ply levels is because of the fact, that the number of possible moves in the beginning depends more on the relocated own pieces than on those of the opponent.

c) the interpolation triangle (green numbers) is done as e.g. :

d(3) = (3 - 1) / (l(3) - l(1)) ...
e(5) = (5 - 1) / (d(5) - d(3)) ...
f(7) = (7 - 1) / (e(7) - e(5)) ...

d) the red numbers have been calculated reversed to that scheme, where the last number simply has been handled as being constant,
then walking from right to left.

e) the results (blue numbers) than finally have been exposed to base e.

I hoped, that this all would be sufficiently obvious ...
Michel
Posts: 2271
Joined: Mon Sep 29, 2008 1:50 am

Re: Perft(13) betting pool

Post by Michel »

It should certainly be possible to get to the perft estimate faster with a biased move selection. But we should keep in mind that here we are mainly concerned about accuracy of estimate more than speed.
That is precisely my point. By making the variance of the estimator smaller one should in principle obtain a more precise estimate for the same amount of work.

So it should be a pure win. But it is not so clear how big the win is.
If you look at my result with LMR perft, the biased estimator gave a better result than the unbiased one.
That was a very drastic LMR as I recall. According to my formula the first move should get almost all the weight.
User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 11:08 am
Location: Klein-Gerau, Germany

Re: Perft(13) betting pool

Post by smrf »

Now I decided to also give you a link to download the used calculation form:

https://files.me.com/r.scharnagl/pzshje.numbers.zip