Perft(13) betting pool

[Michel]

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,

[Daniel Shawul]

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.

[Michel]

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.

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

Next question: what probabilities/multiplicipliers do you use.

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.

Ok I see. How do you know in advance what the mean is?

[Daniel Shawul]

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.

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

Next question: what probabilities/multiplicipliers do you use.

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.

Code: Select all

X
X      X 
X              X  
X              X          X
X              X                  X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Ok I see. How do you know in advance what the mean is?

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.
Obviously it will be biased but it can give good estimates in fixed iterations and is at least worth testing.

[Michel]

HGM's choice yields SD(n)/SD(n-1)=4.06. Still pretty good.

Oops that was wrong. p_1=5/18=0.27. I had done the computation for p_1=0.2.

One now finds SD(n)/SD(n-1)=4.002 which is very close to the optimal
value.

[smrf]

There has been a little bug in the calculating scheme, thus here are the corrected tables:



Now Perft(13) ≈ 1,98112079E+18 for the standard Chess starting position.

[Michel]

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.

I don't believe this can even remotely work.

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.

[Daniel Shawul]

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.

I don't believe this can even remotely work.

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.

Well then shift a little to the left and sample there more often !?

[hgm]

HGM's choice yields SD(n)/SD(n-1)=4.06. Still pretty good.

Oops that was wrong. p_1=5/18=0.27. I had done the computation for p_1=0.2.

One now finds SD(n)/SD(n-1)=4.002 which is very close to the optimal
value.

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.

[hgm]

Well then shift a little to the left and sample there more often !?

Why not just 'sample' the move that has the exact right size sub-tree, and disregard all others?