Perft(13) betting pool
Moderators: hgm, Harvey Williamson, bob
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
 hgm
 Posts: 22338
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
Whether Peter1 or HGMtype sampling is better depends how strongly the sizes of subtrees correlate with each other. If the avarage variance within the set of subtrees hanging from the same node is much smaller than the size variance of all subtrees at that level it becomes attractive to force an equal number of accepted moves (e.g. 1) for each node, to eliminate the variance associated with the distribution of moves over the nodes.
To my surprise I could not really detect much correlation between mobility and subtree sizes. (Tested by trying if the subtree size divided by some power of the mobility would have smaller variance as the raw subtree sizes.) And if the subtree sizes do not correlate with the mobility of their parent, why would they correlate with each other? Perhaps they correlate mostly with the mobility of the grandparent. Or perhaps with the opponent mobility in the parent.
To my surprise I could not really detect much correlation between mobility and subtree sizes. (Tested by trying if the subtree size divided by some power of the mobility would have smaller variance as the raw subtree sizes.) And if the subtree sizes do not correlate with the mobility of their parent, why would they correlate with each other? Perhaps they correlate mostly with the mobility of the grandparent. Or perhaps with the opponent mobility in the parent.

 Posts: 3437
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
@Peter,
Well that is more like it Yes it is a good summary.
From now on, I think we should compare apples with apples due to unexpected surprises. Comparison should be made under the same circumstances. I am just not very sure about a lot of things right now. Does backpropagating variance give higher values than calculating it directly like we just did? How is the node count to be determined when f.i UCT generates the upper tree ones and doesn't generate moves again? Also I found a mistake in Michel's calculation for the UCT version. If the UCT expanded to depth 5 f.i then 100 mil simulations is equivalent to 100mil * (12  5 + 1) = 800mil nodes not 1200 mil nodes. The tree on the top part narrows exponentially so only the last layer of leaf nodes have significant effect.
Concerning my use of second sequence of random numbers, I use the first sequence to guide the paths but dump its result. It is not finished yet but the idea is to compute the first perft less frequently. I didn't have problems when using the limited version so I don't need that but with the _free_ splitting version it does have an effect. I have asked about that effect many times here and I don't see why it is only my method that got affected by it. Anyway I am now experimenting with a 100x less frequent sample.
Well that is more like it Yes it is a good summary.
From now on, I think we should compare apples with apples due to unexpected surprises. Comparison should be made under the same circumstances. I am just not very sure about a lot of things right now. Does backpropagating variance give higher values than calculating it directly like we just did? How is the node count to be determined when f.i UCT generates the upper tree ones and doesn't generate moves again? Also I found a mistake in Michel's calculation for the UCT version. If the UCT expanded to depth 5 f.i then 100 mil simulations is equivalent to 100mil * (12  5 + 1) = 800mil nodes not 1200 mil nodes. The tree on the top part narrows exponentially so only the last layer of leaf nodes have significant effect.
Concerning my use of second sequence of random numbers, I use the first sequence to guide the paths but dump its result. It is not finished yet but the idea is to compute the first perft less frequently. I didn't have problems when using the limited version so I don't need that but with the _free_ splitting version it does have an effect. I have asked about that effect many times here and I don't see why it is only my method that got affected by it. Anyway I am now experimenting with a 100x less frequent sample.

 Posts: 3437
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
@HGM,
It seems that you do less work (nodes count) per iteration so you have about 588 total iterations. That is about twice as much as mine. So it seems you prune a lot. Do you have the log files for the depth 4 calculation you did?
It seems that you do less work (nodes count) per iteration so you have about 588 total iterations. That is about twice as much as mine. So it seems you prune a lot. Do you have the log files for the depth 4 calculation you did?
Re: Summary of Monte Carlo results for perft(12) so far
That's not a mistake.Also I found a mistake in Michel's calculation for the UCT version.
It depends on the implementation. In my implementation I do non uniform weighted MC from the root so for my implementation the 12 is correct
(I also get sd=4e12 for 100e6 random walks btw).
If you recursively traverse the known tree (like a fullDepth search) then
of course you can use a smaller value than 12.
The reason I did it my way is that there was no consensus what the correct measure for the work load would be. So I was using leaf nodes.
In that case it makes no difference.
BTW. Can you fill in the blanks in Peter's chart regarding your method
(mainly moveGen)?
EDIT:
I don't understand why you keep saying we are comparing apples with
oranges. I think the metric sd*sqrt(moveGen) is very fair.

 Posts: 3437
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
I will fill it later if it is applicable. But comparison is a waste of time IMHO if the conditions are not similar. For example here I am doing an experiment with 10x less frequent sample for the firsts sequence and expecting a somewhat larger std but look what I got even at the 25th iteration... Now that is only 1.1 times more work than any other but std is already 2.37e12! How do you explain this ?? I will finish and come back once 100 iterations are done.
 25 
0 h2h3 1.792243e+015 + 1.275609e+012 1.809019e+015 + 4.809923e+011 771980 67863
0 h2h4 2.593603e+015 + 1.502095e+012 2.629264e+015 + 5.336330e+011 1070270 103861
0 g2g3 2.476076e+015 + 1.468997e+012 2.506294e+015 + 5.269766e+011 1023653 97917
0 g2g4 2.194926e+015 + 1.371342e+012 2.202700e+015 + 5.114002e+011 892053 80445
0 f2f3 1.535176e+015 + 1.163391e+012 1.549249e+015 + 4.574004e+011 642214 49306
0 f2f4 2.029887e+015 + 1.362334e+012 2.052263e+015 + 5.043099e+011 880458 78436
0 e2e3 7.070764e+015 + 2.393185e+012 7.157848e+015 + 6.924508e+011 2716757 328684
0 e2e4 7.180308e+015 + 2.400450e+012 7.259155e+015 + 6.917240e+011 2733480 334837
0 d2d3 4.551544e+015 + 1.873513e+012 4.587937e+015 + 6.217199e+011 1665187 190332
0 d2d4 6.259868e+015 + 2.230689e+012 6.346726e+015 + 6.701827e+011 2360348 282855
0 c2c3 2.726847e+015 + 1.551936e+012 2.751958e+015 + 5.310865e+011 1142474 117052
0 c2c4 3.091163e+015 + 1.631546e+012 3.109441e+015 + 5.451844e+011 1262690 130301
0 b2b3 2.379469e+015 + 1.443511e+012 2.405850e+015 + 5.290365e+011 988634 93481
0 b2b4 2.384539e+015 + 1.445030e+012 2.412742e+015 + 5.255737e+011 990673 94724
0 a2a3 1.802316e+015 + 1.281117e+012 1.828648e+015 + 4.811082e+011 778530 68654
0 a2a4 2.545170e+015 + 1.488402e+012 2.559519e+015 + 5.311045e+011 1050846 102228
0 g1h3 2.112560e+015 + 1.366877e+012 2.124583e+015 + 5.020061e+011 886408 80572
0 g1f3 2.678755e+015 + 1.497514e+012 2.718280e+015 + 5.454293e+011 1063750 100184
0 b1c3 2.702863e+015 + 1.571582e+012 2.727765e+015 + 5.584280e+011 1171584 115623
0 b1a3 2.078655e+015 + 1.383581e+012 2.114943e+015 + 5.182571e+011 908044 83304
Perft 6.218673e+016 + 7.259539e+012 6.285418e+016 + 2.468077e+012
wasted 0.00
6.218668e+016 + 7.205414e+012 6.285396e+016 + 2.439323e+012
6.218681e+016 + 7.187222e+012 6.285169e+016 + 2.429468e+012
6.218754e+016 + 7.151536e+012 6.284688e+016 + 2.410510e+012
6.218663e+016 + 7.133765e+012 6.284417e+016 + 2.401778e+012
6.218663e+016 + 7.116136e+012 6.284967e+016 + 2.394142e+012
6.218675e+016 + 7.098667e+012 6.284726e+016 + 2.385896e+012
6.218750e+016 + 7.081582e+012 6.284703e+016 + 2.377851e+012

 Posts: 3437
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
It has reached 1.45e12 on the 50th iteration. Might break the 1e11 barrier after 100 mil simulations (110 mil to be exact)... weird.
Re: Summary of Monte Carlo results for perft(12) so far
I don't know how to interprete your printouts.
mean=6.284703e+016
sd=2.377851e+012
If so then the z value of the true value of Perft(12) is
(6.284703e+01662854969236701747)/2.377851e+012=3.33
which is extremely large (a probability of around 0.05%).
I would tend to assume that there is something wrong with your computations.
Does this mean:6.284703e+016 + 2.377851e+012
mean=6.284703e+016
sd=2.377851e+012
If so then the z value of the true value of Perft(12) is
(6.284703e+01662854969236701747)/2.377851e+012=3.33
which is extremely large (a probability of around 0.05%).
I would tend to assume that there is something wrong with your computations.
 hgm
 Posts: 22338
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
Log files???Daniel Shawul wrote:@HGM,
It seems that you do less work (nodes count) per iteration so you have about 588 total iterations. That is about twice as much as mine. So it seems you prune a lot. Do you have the log files for the depth 4 calculation you did?
I accept 1/32 of the moves, and the branching ratio is less than 32. So not every perft(4) leaf will create a path to the end.
Re: Summary of Monte Carlo results for perft(12) so far
The conditions are similar. The conditions are to construct an unbiased estimator for Perft(12) with the lowest possible value for sd*sqrt(moveGen).But comparison is a waste of time IMHO if the conditions are not similar.
Last edited by Michel on Sat Aug 13, 2011 2:14 pm, edited 1 time in total.

 Posts: 3437
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Summary of Monte Carlo results for perft(12) so far
Maybe I made a mistake I don't know. But the code is the one I used to generate the other data I have been posting. There are lots of issues to discuss but you guys insist on comparing methods... I will make the plot when it is done and see if there are obvious problems.