Perft(13) betting pool

[hgm]

Whether Peter1 or HGM-type sampling is better depends how strongly the sizes of sub-trees correlate with each other. If the avarage variance within the set of sub-trees hanging from the same node is much smaller than the size variance of all sub-trees 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 sub-tree sizes. (Tested by trying if the sub-tree size divided by some power of the mobility would have smaller variance as the raw sub-tree sizes.) And if the sub-tree 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 grand-parent. Or perhaps with the opponent mobility in the parent.

[Daniel Shawul]

@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 back-propagating 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.

[Daniel Shawul]

@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?

[Michel]

Also I found a mistake in Michel's calculation for the UCT version.

That's not a mistake.

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.

[Daniel Shawul]

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

[Daniel Shawul]

It has reached 1.45e12 on the 50th iteration. Might break the 1e11 barrier after 100 mil simulations (110 mil to be exact)... weird.

[Michel]

I don't know how to interprete your printouts.

6.284703e+016 +- 2.377851e+012

Does this mean:

mean=6.284703e+016
sd=2.377851e+012

If so then the z value of the true value of Perft(12) is

(6.284703e+016-62854969236701747)/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]

@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?

Log files???

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.

[Michel]

But comparison is a waste of time IMHO if the conditions are not similar.

The conditions are similar. The conditions are to construct an unbiased estimator for Perft(12) with the lowest possible value for sd*sqrt(moveGen).

[Daniel Shawul]

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.