Perft(13) betting pool

[Daniel Shawul]

Ok we do the same thing for the second part. For the first part, do you just select a child node and multiply the perft value by its weights like you did in weighted MC ? Or do you just add up the perfts of child nodes to get the value for its parent. If you do the latter we are doing exactly the same thing. Same goes for variance? Do you add or use weights for that too ? Be specific..

[Michel]

Or do you just add up the perfts of child nodes to get the value for its parent. If you do the latter we are doing exactly the same thing. Same goes for variance? Do you add or use weights for that too ? Be specific..

No, because the Peter2 method does a series of random walks from the root.

The random walks start from the root. Nothing is added.

EDIT.

Of course adding would be ok. That is what the full width searches do.
However you are only allowed to add unbiased estimators.

EDIT2

Peter has just shown with a very nice example how easy it is
to ruin an unbiased estimator by seemingly making it smarter.

[Daniel Shawul]

So the following post implies means and variances are added but you are saying it is just to determine the weights and is never used for the perft estimate. You reuse your perft estimates to determine your weights, from which you get multipliers for each move to do the multiplication. You clearly have child perft estimates that you can just sum up but prefered not to use it! You never use the back-propagated mean in any other way but to estimate the weights. Ok.

6. As the recursion unwinds, the mean and variance estimates are updated for all visited in-memory tree nodes.

Same. I do exactly that and is easy for perft. But this back propagation step is more difficult
for tree search. Remi coulom had a complex Backup operator before UCT was invented.

In reply to your EDIT:

I do add and get a biased result if I reuse the same sequence of random number. All of them are unbiased but non-uniformly selected. More visits to one node than the other so the variances are different... So clearly it is unbiased but in practice you get a biased result if you do so.

In reply to your EDIT2:
I tried the wasted nodes idea before . It helped a bit when I used limited test but is found irrelevant with unbiased estimates. When I split , I just recompute the perft estimates from scratch, I don't average. So his post is irrelevant.

[Michel]

You clearly have child perft estimates that you can just sum up but prefered not to use it! You never use the back-propagated mean in any other way but to estimate the weights. Ok.

I am not sure if is that extreme.

In my method I first do a number of tree expansion steps
(e.g first 100e3 tree expansions and then 100e6 random walks).
When I expand a node I discard the accumulated data in that node and do a number of scout searches (30) in each of the children to get new data. If these children remain leaf nodes then the data accumulated in the scout searches will be kept.

Using this method I get a variance of 4e12 with 100e6 random walks with
seems to be in the same ballpark as what you and Peter have reported.

I am not happy with this method and have stopped working on it.
I did it only to test my sqrt(mean^2+variance)-mean theory
but perft trees seem to be too regular for this theory to be effective.

[Michel]

So clearly it is unbiased but in practice you get a biased result if you do so.

This is impossible. If you add unbiased estimators you get an unbiased estimator. This is basically

E(X_1+...+X_n)=E(X_1)+....+E(X_n)

For the variances it is more tricky. If the variables (X_i)_i are not independent
you get covariance terms. This is what I think happens in HGM's method.

[Daniel Shawul]

I am not sure if is that extreme.

I will do the test some time next week.I believe it is a waste of lots of information. Also since you determine the weights from the same random number sequence that got your estimates from, the biasedeness I am observing got solved some other way. In my case it gives me disastrous results from the get go .

PS:The test for 10x less often sequence finished at about 3.95e12 std, with 100mil simulations. Don't know how many move gens that is but I saved about 90% of simulations required for the first sequence. Previous best was 3.75e12 with two parallel perfts.

[Daniel Shawul]

Why are you going back ? Well we both observed the phenomenon
Peter's explanation was IIRC, at any time during the iterations, we have more number of smaller perft size thus underestimating our perft. That was the reason why he quit.I didn't and apparently a different sequence fixes it.
Here is the result when I calculate only from one sequence and the other is just equal to the first one. The result 6.22e16 for perft(12).

Code: Select all

0 h2h3   1.798450e+015 +- 1.025796e+012   1178925 | 1.798450e+015 +- 1.025796e+012   1178925 |    117868
0 h2h4   2.598333e+015 +- 1.278024e+012   1468914 | 2.598333e+015 +- 1.278024e+012   1468914 |    158300
0 g2g3   2.479094e+015 +- 1.237764e+012   1422546 | 2.479094e+015 +- 1.237764e+012   1422546 |    152430
0 g2g4   2.203376e+015 +- 1.130601e+012   1299436 | 2.203376e+015 +- 1.130601e+012   1299436 |    136143
0 f2f3   1.541429e+015 +- 9.100452e+011   1045915 | 1.541429e+015 +- 9.100452e+011   1045915 |     97820
0 f2f4   2.033330e+015 +- 1.121068e+012   1288426 | 2.033330e+015 +- 1.121068e+012   1288426 |    131093
0 e2e3   7.080468e+015 +- 2.419738e+012   2781137 | 7.080468e+015 +- 2.419738e+012   2781137 |    368903
0 e2e4   7.192061e+015 +- 2.428439e+012   2791012 | 7.192061e+015 +- 2.428439e+012   2791012 |    373273
0 d2d3   4.561720e+015 +- 1.728666e+012   1986749 | 4.561720e+015 +- 1.728666e+012   1986749 |    252859
0 d2d4   6.261507e+015 +- 2.190091e+012   2517122 | 6.261507e+015 +- 2.190091e+012   2517122 |    330035
0 c2c3   2.728786e+015 +- 1.330213e+012   1528801 | 2.728786e+015 +- 1.330213e+012   1528801 |    171890
0 c2c4   3.095651e+015 +- 1.427362e+012   1640455 | 3.095651e+015 +- 1.427362e+012   1640455 |    187939
0 b2b3   2.392368e+015 +- 1.213032e+012   1394119 | 2.392368e+015 +- 1.213032e+012   1394119 |    147361
0 b2b4   2.394621e+015 +- 1.210115e+012   1390890 | 2.394621e+015 +- 1.210115e+012   1390890 |    148538
0 a2a3   1.809262e+015 +- 1.031282e+012   1185321 | 1.809262e+015 +- 1.031282e+012   1185321 |    118202
0 a2a4   2.550647e+015 +- 1.260374e+012   1448532 | 2.550647e+015 +- 1.260374e+012   1448532 |    155472
0 g1h3   2.115881e+015 +- 1.123133e+012   1290839 | 2.115881e+015 +- 1.123133e+012   1290839 |    133034
0 g1f3   2.687009e+015 +- 1.274737e+012   1465040 | 2.687009e+015 +- 1.274737e+012   1465040 |    157953
0 b1c3   2.706023e+015 +- 1.358927e+012   1561903 | 2.706023e+015 +- 1.358927e+012   1561903 |    170012
0 b1a3   2.085711e+015 +- 1.143134e+012   1313918 | 2.085711e+015 +- 1.143134e+012   1313918 |    135966
Perft 6.231573e+016 +- 6.523242e+012  6.231573e+016 +- 6.523242e+012
wasted 0.00
6.231016e+016 +- 6.494490e+012  6.231016e+016 +- 6.494490e+012 

[Michel]

Ok I finally understand what you are saying.

The data used for tree splitting is not used for perft computations. If you want a new estimate after splitting a node then you do new Peter1 searches in the new leaf nodes and back propagate the mean. Yes this is unbiased I think.

In Peter's example this would be: if X1>0 then you compute a new unbiased estimator X2 _independent of X1_ with hopefully smaller variance

There is a bit of danger in back propagating the variance (how do you compute it?) since the perft numbers in the leaf nodes are not independent there might be covariance terms.

You really should include moveGen data in you tables (just increase a counter whenever you call moveGen). Otherwise it is impossible to compare the performance of your method with other methods.

[Michel]

In Peter's example this would be: if X1>0 then you compute a new unbiased estimator X2 _independent of X1_ with hopefully smaller variance

No that is of course still biased. The correct procedure is:

If X1>0 compute X2
If X1<=0 compute X3

where X2 and X3 are unbiased estimators, independent of X1. Then we get

E((X1<=0)X3+(X1>0)X2)=E(X1<=0)E(X3)+E(X1>0)E(X2)
=mean (E(X1<=0)+E(X1>0))=mean.

This means: if you ever look at a node for the purposes of possibly
splitting it, _you have to recompute it even if you don't split_.

[Daniel Shawul]

What Peter's example is talking about is averaging a new estimate and a second opinion. Like I said even when I decide to waste all nodes during split and recompute, it is still biased as long as I use the same sequence of random numbers.

This means: if you ever look at a node for the purposes of possibly
splitting it, _you have to recompute it even if you don't split_.

This is confusing. If I don't split, I just move on with MC simulation. How does that affect it ? You compute weights from it, I compute proportion of visits from it.