Perft(13) betting pool

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

[hgm]

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.

This is nonsense. There is nothing for you to bias. You cannot pick moves with a relative probability 12:8:6:2:1 and then pick them with other probabilities at the same time...

[Daniel Shawul]

This is nonsense. There is nothing for you to bias. You cannot pick moves with a relative probability 12:8:6:2:1 and then pick them with other probabilities at the same time...

What does that mean at all ?
Anyway you should demonstrate your estimate with an example you prefer.

Edit:
Say sub-tree sizes are 120, 80, 60 , 20 and 10 for each of the moves.
Say you have some kind of heuristic to determine the weights i.e pick your multipliers and weights. Then play one game (simulation) and estimate perft for one ply tree. I hope it is clearer now...That is the object of biasing isn't it? To get better estimates with lower number of games as possible.