This example is interesting since with a little math one can calculate
it exactly (there are linear 2nd order recursion relations for both
the mean and variance propagation).
The following image gives SD(n)/SD(n-1) in terms of the weight of the non reduced moves (the first two).
We see that the optimal choice would have been p_1=p_2=1/4 and hence
p_3=...=p_10=1/16. No surprise as it is easy to see that the EBF is 4.
In this case
SD(n)/SD(n-1)=4.
Thus for the optimal choice the standard deviation seems to propagate
exactly as the mean.
HGM's choice yields SD(n)/SD(n-1)=4.06. Still pretty good.
Uniform selection yields SD(n)/SD(n-1)=4.84. Less good.
If we were to compute Perft(20) then HGM's choice would yield an SD
which is 33 times smaller compared to uniform selection.
EDIT: I forgot to say that all numbers are limits for n large. They
correspond to dominant roots in the relevant characteristic equations,
Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Michel, that is exactly the problem with the example. Now the mean is smartly shifted to the left where also more sampling is done to reduce the variance. Why not take a case where the two cases are confilicting like the d,d-1,d-2 ... 0, the mean is towards the centre, far away from the left end, where you have to sample more to get less variance.. With the 150 100 75 25 12 1 example I gave I don't need to much heuristic to estimate the mean with one game.
Edit:
The idea of my biased heuristic is to sample those games with perft values closer to the mean more. Yours is to sample bigger ones more.
Edit:
The idea of my biased heuristic is to sample those games with perft values closer to the mean more. Yours is to sample bigger ones more.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting pool
Recall that you have never unambiguously described your method. From what you write I gather it amounts to guessing the relative ordering of the sizes of the sub trees and then to give priority to the middle one....Michel, that is exactly the problem with the example. Now the mean is smartly shifted to the left where also more sampling is done to reduce the variance. Why not take a case where the two cases are confilicting like the d,d-1,d-2 ... 0, the mean is towards the centre, far away from the left end, where you have to sample more to get less variance.. With the 150 100 75 25 12 1 example I gave I don't need to much heuristic to estimate the mean with one game.
Next question: what probabilities/multiplicipliers do you use.
EDIT:
Ok I see. How do you know in advance what the mean is?The idea of my biased heuristic is to sample those games with perft values closer to the mean more. Yours is to sample bigger ones more.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
I did infact with an example I mentioned above. OTOH you never mentioned you needed an unbiased estimator even after I said it can be wrong which we don't need for perft estimation. So when you said for LMR perft like shown below that you are going to sample more to the left I was surprised, because I am using a constant multiplier of number of legal moves. This is very common in every other MC simulation other than perft because returned score is not related to tree size at all. So obviously in fixed iterations my method can perform better but yours will need correct multiplying factor estimation if the first move is picked.Michel wrote:Recall that you have never unambiguously described your method. From what you write I gather it amounts to guessing the relative ordering of the sizes of the sub trees and then to give priority to the middle one....Michel, that is exactly the problem with the example. Now the mean is smartly shifted to the left where also more sampling is done to reduce the variance. Why not take a case where the two cases are confilicting like the d,d-1,d-2 ... 0, the mean is towards the centre, far away from the left end, where you have to sample more to get less variance.. With the 150 100 75 25 12 1 example I gave I don't need to much heuristic to estimate the mean with one game.
Next question: what probabilities/multiplicipliers do you use.
Code: Select all
X
X X
X X
X X X
X X X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
The idea is to use a simple heuristic that the mean lies around the middle so try those more often. I don't esimate multiplying factors unlike yours.Ok I see. How do you know in advance what the mean is?
Obviously it will be biased but it can give good estimates in fixed iterations and is at least worth testing.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting pool
Oops that was wrong. p_1=5/18=0.27. I had done the computation for p_1=0.2.HGM's choice yields SD(n)/SD(n-1)=4.06. Still pretty good.
One now finds SD(n)/SD(n-1)=4.002 which is very close to the optimal
value.
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting pool
I don't believe this can even remotely work.The idea is to use a simple heuristic that the mean lies around the middle so try those more often. I don't esimate multiplying factors unlike yours.
In your [d d-1 d-2 ... 0] example the EBF is very close to 2 (if d is sufficiently large).
This means that the subtree sizes are proportional to
2^d 2^(d-1) .... 1
Perft is proportional to
2^(d+1).
The median however is 2^(d/2).
So if you sample around the median you will simply make it harder to discover the "interesting" large subtrees to the left which contribute most
to the value of Perft.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting pool
Well then shift a little to the left and sample there more often !?Michel wrote:I don't believe this can even remotely work.The idea is to use a simple heuristic that the mean lies around the middle so try those more often. I don't esimate multiplying factors unlike yours.
In your [d d-1 d-2 ... 0] example the EBF is very close to 2 (if d is sufficiently large).
This means that the subtree sizes are proportional to
2^d 2^(d-1) .... 1
Perft is proportional to
2^(d+1).
The median however is 2^(d/2).
So if you sample around the median you will simply make it harder to discover the "interesting" large subtrees to the left which contribute most
to the value of Perft.
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
Oh, so I was really lucky in guessing. It might have been more educational to make an obvious poor guess like 10 for the EBF. Then the weight of the first two moves would have been 10/28 = 0.357, and according to your graph the variance would be 4.25, only 6% larger than for the optimal p_i.Michel wrote:Oops that was wrong. p_1=5/18=0.27. I had done the computation for p_1=0.2.HGM's choice yields SD(n)/SD(n-1)=4.06. Still pretty good.
One now finds SD(n)/SD(n-1)=4.002 which is very close to the optimal
value.
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perft(13) betting pool
Why not just 'sample' the move that has the exact right size sub-tree, and disregard all others?Daniel Shawul wrote:Well then shift a little to the left and sample there more often !?