Perft(13) betting pool

[Daniel Shawul]

That was a very drastic LMR as I recall. According to my formula the first move should get almost all the weight.

Not necessarily. Infact if you do so it will probably be much larger than expected perft. Please note that perft is an _average_ estimate so you should give more weight to those nodes representative to the perft tree. Maybe the mode is candidate. But perft is different from tree search because you are not trying to maximize or minimize anything (just get average). For UCT tree search you bias the tree in such a way winning branches are explored more. Estimating perft starting from ply 3 already reduces the variance significantly. For the aggressive LMR tree we experimented with may be a depth of (perftD / 2) is more appropriate.

There is an exploration-exploitation dilemma as in the case of UCT. And if you want to use sigma for move selection, you should keep statistic on a tree. And I am not even clear how to do this for perft. UCT uses

Code: Select all

UCTValue(parent, n) = winrate + sqrt((ln(parent.visits))/(5*n.nodevisits))

The second term is the exploration term that gives more weight to those nodes who have a winning ratio.. But in perft we don't have a rule to differentiate which is more representative path?? So I don't think we can do that.

[Michel]

Not necessarily. Infact if you do so it will probably be much larger than expected perft.

I deleted this post since my example was incorrect. I have to think about
the above statement.

[Daniel Shawul]

Thanks,
I am trying to open the xml file with excel with no luck.It seems that simple extrapolation should give good estimates if one takes care of the odd-even effect. Jesus also did that and got about 1.98e18. I think that in your previous estimate missed that and got
a number like mine i.e about 1.934e10. Even after breaking down the perft to two ply moves I still got something around that. Maybe you can improve your estimate if you extrapolate each 2-ply path separately...

Taking log OR nth_root of perft nodes makes sense if you want to interpolate on BFs instead of nodes count. Alos BF increases from ply to ply especially for the opening position so it is not a simple BF^13 for perft(13). So unless you assume the BF to remain constant from ply to ply you should not take the same base of logarithm. I should also add that my efforts so far with estimating perft from estimating BF in each ply gave me bad results.

[Michel]

Not necessarily. Infact if you do so it will probably be much larger than expected perft.

I don't understand why you say this. Suppose we always take
the first move (so the first weight is 1 and the others 0). Then we
get Perft[N]=1. So certainly not "much larger".

Of course this is an illegal example as weights cannot be zero (the payoff
for a zero weight is infinite). So the contributions of the other moves
will give us an unbiased estimator.

I don't think it is necessary to collect statistics on the three. Heuristics
might be enough. The aim is to find weights better then the uniform ones. Not necessarily optimal ones. My formula says that the weights should
be roughly proportional to the tree size.

[smrf]

Maby, Daniel, you are using a Windows OS and MS Office/Excel, then following might be useful for you:

https://files.me.com/r.scharnagl/btzxo0

I have tried here to export it from my Mac.

[Daniel Shawul]

Perft is an average estimate and as such any bias should be towards the average for good results. The first move is the deepest searched and is not representative.
Consider a one ply tree with 5 moves. Each move has sub-trees with the following node count. 150 100 75 25 12 0.
Now the perft estimate for each move will be 5 * sub-tree size since we have 5 legal moves. So if you take the first one you have 5 * 150 =750, but the middle one is 75 and gives 5 * 75 = 375 which is closer to the truth. Actual perft is 150 + 100 + 100 + 12 = 372

The LMR tree we experimented with pretty much like this. Every other move gets reduced by one more ply giving a decreasing sub-tree size as we go towards the end of move list.

[Michel]

As said, I want the weights to be proportional to the tree size.

Take your example

150 100 75 25 12 1

(I have changed the 0 into 1 a one to avoid a degenerate case). Thus
Perft=363.

The SD for uniform sampling is 318.7 which is the square root of

(1/6)*(6*150-363)^2+(1/6)*(6*100-363)^2+...

Now I would like to take weights which are proportional to
the tree size. Thus

150/363 100/363 75/363 25/363 12/363 1/363

What is the variance?

150/363*(363/150*150-363)^2+...=0!!!

Suddenly it is zero.

Of course we don't know the tree size so we can't select weights in this
way. So let us take very crude approximations (given by heuristics say).

1/4 1/4 1/8 1/8 1/8 1/8

Now we compute square root of

1/4*(4*150-363)^2+...

which is 222.2 which is quite a bit smaller than 318.7.

I hope this example clarifies my point.

[hgm]

Perft is an average estimate and as such any bias should be towards the average for good results. The first move is the deepest searched and is not representative.
Consider a one ply tree with 5 moves. Each move has sub-trees with the following node count. 150 100 75 25 12 0.
Now the perft estimate for each move will be 5 * sub-tree size since we have 5 legal moves. So if you take the first one you have 5 * 150 =750, but the middle one is 75 and gives 5 * 75 = 375 which is closer to the truth. Actual perft is 150 + 100 + 100 + 12 = 372

The LMR tree we experimented with pretty much like this. Every other move gets reduced by one more ply giving a decreasing sub-tree size as we go towards the end of move list.

This is not correct. The best would be to pick the moves with relative probability 12:8:6:2:1, implying multipliers 39/12, 39/8, 39/6, 39/2 and 39/1. That way the outcome would be 39*12.5 whatever you pick, i.e. no variance at all.

[edit] I see Michel in the mean time pointed out the same.

Another remark: One has to be pretty careful here, because it is very tempting to come up with examples where you choose some of the probabililities zero, to reduce variance. But then you fall into the trap of the limit of an expectation value (or variance, which is also an expectation value) in general not being equal to the expectation value of the limit distribution. If you let probabilities approach zero, the weight you need to give the result when it happens approaches infinity, and this hugely drives up variance. Only when you take that limit first, setting the probability to exactly zero, you get rid of the variance. But that is meaningless, it is not the variance of any unbiased estimate, because it becomes independent of the size of that sub-tree, which the true average is not.

[Daniel Shawul]

I don't understand. The multiplier is _fixed_ i.e always 5 (number of legal moves) which ever you pick. That is the way Peter's method work. With that in mind the bias of the PRNG should be towards the average case. If you are going to use different multipliers , then ofcourse you should use different weights.

[Ajedrecista]

Hi Mr. Muller:

First of all, I want to congratulate you and the rest of people that are doing astonishing estimates with superb methods.

Secondly, I do not understand the method you propose in your post (I am not so clever and please do not waste time trying to explain it to me). But reading it, there is something that I find shocking: if relative probabilities are 12:8:6:2:1 (at least I understand it), why multipliers are 39/12, 39/8... instead 29/12, 29/8... (I mean: 12 + 8 + 6 + 2 + 1 = 29), and finally the outcome is 39 · 12.5 instead of 29 · 12.5 = 362.5, which is very close to 150 + 100 + 75 + 25 + 12 = 362? I think that 39 instead of 29 is a typo, but I could be wrong because this method (like many others of this thread) is far beyond my capabilities. If, by chance, I have reason (I am not sure at all) please correct it (and I will be glad of realise that typo and understand a little such method).

Regards from Spain.

Ajedrecista.