Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
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..
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
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.
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.
In reply to your EDIT: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.
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.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
I am not sure if is that extreme.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.
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.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
This is impossible. If you add unbiased estimators you get an unbiased estimator. This is basicallySo clearly it is unbiased but in practice you get a biased result if you do so.
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
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 .I am not sure if is that extreme.
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
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).
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
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
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.
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.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
No that is of course still biased. The correct procedure is: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
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_.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
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 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.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_.