Perft(13) betting pool

[Michel]

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.

I am not sure if I follow precisely what you say here but I had
made similar considerations.

I understand it like this. If you assign very small probabilities
then the distribution becomes very skew and you need very large
samples before the strong limit theorem kicks in (which allows
you to use the variance to compute error bars).

So saying that the weights should be proportional to tree size
is an exageration. One should not assign probabilities which
are small compared to the sample size one wants to use.

But as the example in my post shows: even a very crude biasing
of the weights gives a substantial reduction of the variance.

EDIT: I am not sure you noticed my "optimal" value for the weights.
I reproduce it here

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.

[Daniel Shawul]

I am sure the 1/4 1/4 1/8 1/8 will be worse than unifrom averaging since giving more weight to those moves at the extreme (with high and low sub-trees) can only bias the result more. Are going to select moves with different probablity and still use the same multiplier ?

[hgm]

You caught me; I miscalculated, and should have typed 29.

[Michel]

Are going to select moves with different probablity and still use the same multiplier ?

No of course not. The multipliers are the inverses of the weights.

4 4 8 8 8 8

[Daniel Shawul]

And where does the number of legal moves go ? I see when you multiply you get 1. What do you get from this ?

[Michel]

Suppose we have random variables X_1, ..., X_n
and we define a random variable Y which is (1/p_i)*X_i with probability p_i
for i=1,...n.

Then we get

E(Y)=sum_i p_i E((1/p_i)X_i)=sum_i E(X_i)

This is the idea.

[Daniel Shawul]

I think you should do it for the example I provided.
150 100 75 25 12 1

I say 1/6 for all is the best since after inifite number of games each would have a probability of 1/6.
Perft = 1/6 * (150 + 100 + 75 + 25 + 12 + 1) * 6

Now do it with your bias.
I am saying with a constant multiplier 6 you should weigh like
1/8 1/4 1/2 1/4 1/8 to get a better estimate. I just put the numbers randomly but the pattern should be like that. It is definitely biased but
could give better result before many games are played...

Please do it step by step with your probability and weight as well.
I don't know what you are going to aciheve since the probability and weight cancel out??

[hgm]

So saying that the weights should be proportional to tree size
is an exageration. One should not assign probabilities which
are small compared to the sample size one wants to use.

I don't think so. The variance is still what it is. Even if you take only one sample. Of course the result is less accurate, then, but that is justa consequence of the 1/sqrt(N) law. It would still be worse if you take sub-optimal sampling probabilities.

Btw, I can confirm the proportionality with sqrt(x_i^2 + s_i^2).

[hgm]

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.

No, to get an unbiased estimate the multiplier has to be the inverse of the probability. So only in the case of homogeneous sampling, where in a node with N moves every move has probability 1/N of being sampled, the weights are all N. If the product of weight and sampling probability is not 1, the contribution of that sub-tree to the expectation value has a weight different from 1, and you will not get the correct expectation value.

Now do it with your bias.
I am saying with a constant multiplier 6 you should weigh like
1/8 1/4 1/2 1/4 1/8 to get a better estimate. I just put the numbers randomly but the pattern should be like that. It is definitely biased but
could give better result before many games are played...

This does not give the correct average, because the average contribution of the 150 and 0 is weighted by a factor 6/8, that of 100 and 12 by 6/4 and that of 75 and 25 by 6/2. (Well, your probabilities do not add up to 1, which makes it impossible to work this out numerically...)

Making the variance small at the expense of getting a wrong expectation value is not worth anything. I can estimate it a 0 with 100% probability, and that would have zero variance... Small variance is only an asset if the expectation value was correct. Otherwise it just reduces the probability to be correct.

[Daniel Shawul]

Lets do the example with your weights.
150 100 75 25 12 1

12:8:6:2:1 => with multiplier 29/12 29/8 29/6 29/2 29/1


If I am asked to estimate the perft with playing only _one_ game. I would bias my move selection towards the average value i.e 75 and multiply by 6.

As you said for your case any move picked gives the same result that is
29 * 12.5, so far so good. But you don't know the average in the first place..
What am I missing ? Please do it with the example by playing one game..


Edit:
I know the probablities I gave are wrong.