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.
Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 27829
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
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.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.
Why? can't we calculate variance for a biased estimate?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.
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..
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
More to clarify this ridiculous claim of low variance and unbiased estimate
Please do finish the example and calculate the unbiased mean if that is what you claim as HG does.
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.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!!!
Please do finish the example and calculate the unbiased mean if that is what you claim as HG does.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Ok I will finish it for youDaniel Shawul wrote:More to clarify this ridiculous claim of low variance and unbiased estimateSo 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.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!!!
Please do finish the example and calculate the unbiased mean if that is what you claim as HG does.
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
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**.
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.So any conclusion you base upon it regarding variance is meaningless. It no longer satisfies your primary goal of being correct.
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..
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting pool
As I wrote: this was a hypothetical example. But it shows you what to strive for. The next paragraph in my post reads.So clearly which ever move gets selected 363 is the perft estimate ?? This is typical circular reasoning.
And then I proceeded to show that you get indeed a smaller variance with those weights.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
I don't know why you keep arguing with what is a simple mathematical
fact (confirmed by HGM).
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Confirmed of what ?? HG is saying the estimate should be unbiased first..Michel wrote:As I wrote: this was a hypothetical example. But it shows you what to strive for. The next paragraph in my post reads.So clearly which ever move gets selected 363 is the perft estimate ?? This is typical circular reasoning.
And then I proceeded to show that you get indeed a smaller variance with those weights.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
I don't know why you keep arguing with what is a simple mathematical
fact (confirmed by HGM).
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.
So any conclusion you base upon it regarding variance is meaningless. It no longer satisfies your primary goal of being correct.
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.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting pool
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 belowPlease say if your estimate will be biased/unbiased/blunder in most cases, then we can continu
Thus if the X_i are unbiased estimators of constants x_i then Y isSuppose 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)
an unbiased estimator for the sum of the x_i.
If your estimator is biased then you cannot make it more accurate by using larger samples. You will converge to the wrong value.My estimate on the other hand is admittedly biased, but faster than the standard method.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
OOpss my mistake you are saying it is unbiased ??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
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
No i asked for your _new_ method with different weights and multipliers. Are you trying to evade the subject ?Michel wrote: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 belowPlease say if your estimate will be biased/unbiased/blunder in most cases, then we can continu
Thus if the X_i are unbiased estimators of constants x_i then Y isSuppose 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)
an unbiased estimator for the sum of the x_i.
If your estimator is biased then you cannot make it more accurate by using larger samples. You will converge to the wrong value.My estimate on the other hand is admittedly biased, but faster than the standard method.
Last edited by Daniel Shawul on Mon Jul 25, 2011 3:51 am, edited 3 times in total.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting pool
No it does not. It is first and foremost an unbiased estimator. So the meanIt blunders because gives the variance more priority than 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.