Perft(13) betting pool

[hgm]

I wasn't trying to make fun of anything.

But you said you want to bias the move selection (i.e. change the selection probability p_i of move i), WITHOUT changing the weight w_i (keeping it 6 in your example). That it NOT compatible with the goal stated above. It makes the estimate INCORRECT. To get a correct estimate the equation p_i * w_i = 1 must remain valid.

Your example violated that equation (e.g. p_i = 1/2 and w_i = 6). So any conclusion you base upon it regarding variance is meaningless. It no longer satisfies your primary goal of being correct.

[Daniel Shawul]

I wasn't trying to make fun of anything.

But you said you want to bias the move selection (i.e. change the selection probability p_i of move i), WITHOUT changing the weight w_i (keeping it 6 in your example). That it NOT compatible with the goal stated above. It makes the estimate INCORRECT. To get a correct estimate the equation p_i * w_i = 1 must remain valid.

Please get the context of what is being discussed before jumping in. I didn't say it gives CORRECT results, so why you keep on repeating it.

Your example violated that equation (e.g. p_i = 1/2 and w_i = 6). So any conclusion you base upon it regarding variance is meaningless. It no longer satisfies your primary goal of being correct.

Why? can't we calculate variance for a biased estimate?

Atleast the one I proposed gives a result faster than standard. That is what is refered when we say "biased", it is underlined it is faster but is away from the mean? Now you are trying to escape through biased move selection unbiased estimate stuff. That is fine but please do demonstrate how it is going to work.
Do you realize your method asks for an average perft estimate at each node to estimate perft itself ?? That needs some thinking... What are you going to use for that? If you are so confident why don't you do it for a simple perft tree anyway..

[Daniel Shawul]

More to clarify this ridiculous claim of low variance and unbiased estimate

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!!!

So far so good variance is 0. But at what cost?? The estimate has to become either super-bad (very biased) OR you impose an absurd requirement such as an average perft estimate to be returned which ever move is picked. Thinking of the latter is a lough out loud stuff for me because I can't comprehend that we need a perft estimate to estimate perft itself.

Please do finish the example and calculate the unbiased mean if that is what you claim as HG does.

[Daniel Shawul]

More to clarify this ridiculous claim of low variance and unbiased estimate

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!!!

So far so good variance is 0. But at what cost?? The estimate has to become either super-bad (very biased) OR you impose an absurd requirement such as an average perft estimate to be returned which ever move is picked. Thinking of the latter is a lough out loud stuff for me because I can't comprehend that we need a perft estimate to estimate perft itself.

Please do finish the example and calculate the unbiased mean if that is what you claim as HG does.

Ok I will finish it for you

Code: Select all

Mean = 150/363 * (363/150 * 150)
          + 100/363 * (363/100 * 100)
          + 75/363 * (363/75 * 75)
          + 25/363 * (363/25 * 25)
          + 1/263 * (363/1 * 1)

      = 150/363 * (363)
         + 100/363 * (363)
         + 75/363 * (363)
         + 25/363 * (363)
         + 1/363 * (363)
       = 363

So clearly which ever move gets selected 363 is the perft estimate ?? This is typical circular reasoning. Why do I go to the trouble of calculating all this if I knew the _unbiased_ perft value anyway ??
I think it is clear the estimate will be biased or you are a magician to get 363 right If we estimated it as 300 it means we are biased by 63, even though a trillion games are played.

HG said the following in response to my estimate being biased. I knew it is gonna come bite his a**.

So any conclusion you base upon it regarding variance is meaningless. It no longer satisfies your primary goal of being correct.

Well I will not even dare to say your estimate will be biased, when it requires a freakin magician! It will blunder most of the time period.

What is funny about this is that I thought the same as you do now (Michel) couple of days ago and you corrected me. I realized my mistake which was perft was an _averaging_ estimate so uniform PRNG should be used for an unbiased estimate. But here you are using different weights, which led you to use different multiplier (which btw doesn't include the number of legal moves in it!!), which in turn led you to the ridiculous requirement of having the unbiased perft estimate
Also here we play one move and multipy by some random weight disregarding how many moves are. But in MC approach only one move is explored and the estimate for the rest is assumed to be the same as the move we explored that is why we multiply by number of legal moves. So it should be definitely in there. This whole thing is messed up and I hope everyone sees it..

[Michel]

So clearly which ever move gets selected 363 is the perft estimate ?? This is typical circular reasoning.

As I wrote: this was a hypothetical example. But it shows you what to strive for. The next paragraph in my post reads.

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

And then I proceeded to show that you get indeed a smaller variance with those weights.

I don't know why you keep arguing with what is a simple mathematical
fact (confirmed by HGM).

[Daniel Shawul]

So clearly which ever move gets selected 363 is the perft estimate ?? This is typical circular reasoning.

As I wrote: this was a hypothetical example. But it shows you what to strive for. The next paragraph in my post reads.

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

And then I proceeded to show that you get indeed a smaller variance with those weights.

I don't know why you keep arguing with what is a simple mathematical
fact (confirmed by HGM).

Confirmed of what ?? HG is saying the estimate should be unbiased first..

So any conclusion you base upon it regarding variance is meaningless. It no longer satisfies your primary goal of being correct.

Did you miss that or are you saying your method gives an unbiased estimate ? Please say if your estimate will be biased/unbiased/blunder in most cases, then we can continue.. I say it will blunder most of the time.
There is nothing to strive for when it blunders most of the time. My estimate on the other hand is admittedly biased, but faster than the standard method. I would choose my biased method when I have time constraints for example.

[Michel]

Please say if your estimate will be biased/unbiased/blunder in most cases, then we can continu

Of course it is unbiased. I thought we were through with this by now. If the multipliers are the inverses of the weights then you get an unbiased estimate. I even wrote a (trivial) proof a couple of posts ago. I'll repeat it below

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)

Thus if the X_i are unbiased estimators of constants x_i then Y is
an unbiased estimator for the sum of the x_i.

My estimate on the other hand is admittedly biased, but faster than the standard method.

If your estimator is biased then you cannot make it more accurate by using larger samples. You will converge to the wrong value.

[Daniel Shawul]

Of course it is unbiased. I thought we were through with this by now. If the multipliers are the inverses of the weights then you get an unbiased estimate. I even wrote a (trivial) proof a couple of posts ago. I'll repeat it below

OOpss my mistake you are saying it is unbiased ??
How do you then estimate 363 at every node!
I am talking about the method which miminizes the variance by giving different weights if that was not clear.
Forget your proof for Uniform PRNG, that is hisotry. I want you to explain the new method which lowers the variance using different weights and multipliers.

Skip the following because I thought you said it will be biased.

It blunders because gives the variance more priority than the mean. It does not take the legal moves in to the equation. It needs a perfect estimate of perft etc... What do you do when the first move is selected out of 10 possible moves, how about out of 100 moves etc... Clearly you need to adjust the weight not only based on sub-tree size but also based on the legal moves count.. Explain those please.

[Daniel Shawul]

Please say if your estimate will be biased/unbiased/blunder in most cases, then we can continu

Of course it is unbiased. I thought we were through with this by now. If the multipliers are the inverses of the weights then you get an unbiased estimate. I even wrote a (trivial) proof a couple of posts ago. I'll repeat it below

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)

Thus if the X_i are unbiased estimators of constants x_i then Y is
an unbiased estimator for the sum of the x_i.

My estimate on the other hand is admittedly biased, but faster than the standard method.

If your estimator is biased then you cannot make it more accurate by using larger samples. You will converge to the wrong value.

No i asked for your _new_ method with different weights and multipliers. Are you trying to evade the subject ?

[Michel]

It blunders because gives the variance more priority than the mean.

No it does not. It is first and foremost an unbiased estimator. So the mean
has priority over anything else.

After that you can try you can try to reduce the variance. With perfect
information you can (unsurprisingly) bring the variance down to zero.

With imperfect information you can still reduce the variance compared to uniform selection.