Perft(13) betting pool

[Daniel Shawul]

The tide has shifted against uniform selection after my improvements. The uniform selection now takes the last place.
All of the methods give very good results with a fixed depth of 3, that is with 8902 leaf nodes.
Uniform selection has the biggest variance after 100 million iterations. First here is the summary of results in order of decreasing performance.

Calculated Variance:

Code: Select all

		Mean	6.285742E+16						
		StdDev	5.024237E+12						
		Error	2.5155E+12

Sub-tree size:

Code: Select all

		Mean	6.285823E+16						
		StdDev	5.047898E+12						
		Error	3.3345E+12

Log-tree size

Code: Select all

		Mean	6.285624E+16						
		StdDev	5.725446E+12						
		Error	1.337E+12

Uniform:

Code: Select all

		Mean	6.284984E+16						
		StdDev	6.919680E+12						
		Error	5.0615E+12

Note that the Log-tree gave the least error to the actual result but I think that was luck.
Some time the default UCB formula also gives very small errors to the actual mean but has
the biggest variance since it explores the best nodes exponentially more. Other than that it is clear
uniform selection is being whopped even in this simple perft with more or less unifrom tree.

Note that the only reason non-splitting methods seem competitive is because of the fact that the perft
on the initial position is more or less a uniform tree. I am pretty sure the story
will be _hugely_ different on an LMR perft. Well one can go for a faster perft for the _current_
perft(13) competition with non-splitting method but method will do badly for other positions/search.

Also any method which guides its search based on a result of one sequence of random numbers will
fail sooner or later. Reusing results of a sequence of random numbers will bias results badly
be it in pure MC part of upper tree splitting section.

I have two more ideas to reduce the 2x work load. One is to update the first perft computation used
for guiding the search tree only very rarely. I can do that say 10x-100x less frequently.
Another improvement is that the simulations I was considering as wasted upto now can be
used! (old_value + value) / 2 started giving better results after I made the two improvements
I mentioned above.

------------------------------------------------------------------------------------------------------
And here follows the detailed result after 100 million simulations. Actually 200 since I do two parallel perfts.

Code: Select all

Uniform	
0	h2h3	1.82E+15	+-	8.32E+11	1.81E+15	4989500	380		6.91E+23
	0	h2h4	2.62E+15	+-	1.18E+12	2.62E+15	4989500	420		1.39E+24
	0	g2g3	2.50E+15	+-	1.10E+12	2.50E+15	4989500	420		1.20E+24
	0	g2g4	2.22E+15	+-	9.08E+11	2.22E+15	4989500	421		8.24E+23
	0	f2f3	1.55E+15	+-	6.38E+11	1.55E+15	4989500	380		4.08E+23
	0	f2f4	2.05E+15	+-	9.31E+11	2.05E+15	4989500	401		8.66E+23
	0	e2e3	7.16E+15	+-	3.17E+12	7.16E+15	4989500	599		1.01E+25
	0	e2e4	7.26E+15	+-	3.11E+12	7.27E+15	4989500	600		9.65E+24
	0	d2d3	4.58E+15	+-	1.74E+12	4.59E+15	4989500	539		3.03E+24
	0	d2d4	6.33E+15	+-	2.73E+12	6.33E+15	4989500	560		7.44E+24
	0	c2c3	2.75E+15	+-	1.21E+12	2.75E+15	4989500	420		1.47E+24
	0	c2c4	3.12E+15	+-	1.36E+12	3.12E+15	4989500	441		1.86E+24
	0	b2b3	2.41E+15	+-	1.08E+12	2.41E+15	4989500	420		1.17E+24
	0	b2b4	2.41E+15	+-	1.05E+12	2.41E+15	4989500	421		1.11E+24
	0	a2a3	1.83E+15	+-	8.48E+11	1.83E+15	4989500	380		7.20E+23
	0	a2a4	2.57E+15	+-	1.15E+12	2.57E+15	4989500	420		1.32E+24
	0	g1h3	2.13E+15	+-	9.38E+11	2.13E+15	4989500	400		8.80E+23
	0	g1f3	2.70E+15	+-	1.10E+12	2.70E+15	4989500	440		1.22E+24
	0	b1c3	2.73E+15	+-	1.28E+12	2.73E+15	4989500	440		1.63E+24
	0	b1a3	2.10E+15	+-	9.62E+11	2.10E+15	4989500	400		9.25E+23
										
			6.284119E+16			6.285849E+16	99790000	8902		4.788197E+25
										
			Mean	6.284984E+16						
			StdDev	6.919680E+12						
			Error	5.0615E+12						
										
Tree	
0	h2h3	1.81E+15	+-	8.82E+11	1.82E+15	2879147	380		7.78E+23
	0	h2h4	2.62E+15	+-	1.05E+12	2.62E+15	4160729	420		1.10E+24
	0	g2g3	2.50E+15	+-	1.01E+12	2.50E+15	3964834	420		1.02E+24
	0	g2g4	2.22E+15	+-	9.08E+11	2.22E+15	3520057	421		8.24E+23
	0	f2f3	1.55E+15	+-	7.71E+11	1.55E+15	2465449	380		5.95E+23
	0	f2f4	2.05E+15	+-	9.43E+11	2.05E+15	3254839	401		8.89E+23
	0	e2e3	7.16E+15	+-	1.73E+12	7.16E+15	11367648	599		2.99E+24
	0	e2e4	7.27E+15	+-	1.71E+12	7.26E+15	11537522	600		2.93E+24
	0	d2d3	4.59E+15	+-	1.25E+12	4.59E+15	7285937	539		1.56E+24
	0	d2d4	6.33E+15	+-	1.59E+12	6.33E+15	10046803	560		2.53E+24
	0	c2c3	2.75E+15	+-	1.07E+12	2.75E+15	4367764	420		1.14E+24
	0	c2c4	3.12E+15	+-	1.13E+12	3.12E+15	4954089	441		1.28E+24
	0	b2b3	2.41E+15	+-	9.97E+11	2.41E+15	3822851	420		9.93E+23
	0	b2b4	2.41E+15	+-	9.83E+11	2.41E+15	3828821	421		9.67E+23
	0	a2a3	1.82E+15	+-	8.92E+11	1.83E+15	2896066	380		7.95E+23
	0	a2a4	2.57E+15	+-	1.03E+12	2.57E+15	4087075	420		1.07E+24
	0	g1h3	2.13E+15	+-	9.30E+11	2.13E+15	3385055	400		8.66E+23
	0	g1f3	2.70E+15	+-	1.01E+12	2.70E+15	4292715	440		1.01E+24
	0	b1c3	2.73E+15	+-	1.11E+12	2.73E+15	4336847	440		1.23E+24
	0	b1a3	2.10E+15	+-	9.58E+11	2.10E+15	3335752	400		9.18E+23
										
			6.285881E+16			6.285766E+16	99790000	8902		2.548127E+25
										
			Mean	6.285823E+16						
			StdDev	5.047898E+12						
			Error	3.3345E+12						
										
Logtree	
0	h2h3	1.82E+15	+-	7.99E+11	1.82E+15	3856976	380		6.38E+23
	0	h2h4	2.62E+15	+-	1.02E+12	2.62E+15	4803792	420		1.04E+24
	0	g2g3	2.50E+15	+-	9.68E+11	2.50E+15	4680828	420		9.36E+23
	0	g2g4	2.22E+15	+-	8.42E+11	2.22E+15	4373054	421		7.08E+23
	0	f2f3	1.55E+15	+-	6.75E+11	1.55E+15	3453734	380		4.56E+23
	0	f2f4	2.05E+15	+-	8.71E+11	2.05E+15	4171414	401		7.59E+23
	0	e2e3	7.16E+15	+-	2.47E+12	7.16E+15	7396843	599		6.08E+24
	0	e2e4	7.25E+15	+-	2.61E+12	7.27E+15	7431135	600		6.79E+24
	0	d2d3	4.59E+15	+-	1.39E+12	4.59E+15	6250336	539		1.93E+24
	0	d2d4	6.33E+15	+-	1.96E+12	6.33E+15	7077848	560		3.85E+24
	0	c2c3	2.75E+15	+-	1.05E+12	2.75E+15	4931151	420		1.10E+24
	0	c2c4	3.12E+15	+-	1.18E+12	3.12E+15	5253665	441		1.38E+24
	0	b2b3	2.41E+15	+-	9.51E+11	2.41E+15	4585989	420		9.05E+23
	0	b2b4	2.41E+15	+-	9.37E+11	2.41E+15	4592763	421		8.79E+23
	0	a2a3	1.82E+15	+-	8.11E+11	1.83E+15	3870170	380		6.58E+23
	0	a2a4	2.57E+15	+-	1.00E+12	2.58E+15	4757167	420		1.00E+24
	0	g1h3	2.13E+15	+-	8.64E+11	2.13E+15	4272879	400		7.47E+23
	0	g1f3	2.70E+15	+-	9.76E+11	2.70E+15	4885180	440		9.52E+23
	0	b1c3	2.73E+15	+-	1.09E+12	2.73E+15	4910426	440		1.18E+24
	0	b1a3	2.10E+15	+-	8.90E+11	2.10E+15	4234650	400		7.93E+23
										
			6.284526E+16			6.286721E+16	99790000	8902		3.278073E+25
										
			Mean	6.285624E+16						
			StdDev	5.725446E+12						
			Error	1.337E+12						
										
Variance	
0	h2h3	1.82E+15	+-	8.66E+11	1.81E+15	2967226	380		7.51E+23
	0	h2h4	2.62E+15	+-	1.03E+12	2.62E+15	4232487	420		1.07E+24
	0	g2g3	2.50E+15	+-	1.00E+12	2.50E+15	3972088	420		1.00E+24
	0	g2g4	2.22E+15	+-	9.24E+11	2.22E+15	3372593	421		8.53E+23
	0	f2f3	1.55E+15	+-	7.78E+11	1.55E+15	2394864	380		6.06E+23
	0	f2f4	2.05E+15	+-	9.24E+11	2.05E+15	3372213	401		8.53E+23
	0	e2e3	7.16E+15	+-	1.71E+12	7.16E+15	11541501	599		2.92E+24
	0	e2e4	7.27E+15	+-	1.71E+12	7.26E+15	11515344	600		2.91E+24
	0	d2d3	4.59E+15	+-	1.30E+12	4.59E+15	6662688	539		1.69E+24
	0	d2d4	6.33E+15	+-	1.59E+12	6.33E+15	9983994	560		2.53E+24
	0	c2c3	2.75E+15	+-	1.06E+12	2.75E+15	4425732	420		1.12E+24
	0	c2c4	3.12E+15	+-	1.12E+12	3.12E+15	4993828	441		1.26E+24
	0	b2b3	2.41E+15	+-	9.87E+11	2.41E+15	3849977	420		9.74E+23
	0	b2b4	2.41E+15	+-	9.82E+11	2.41E+15	3811127	421		9.64E+23
	0	a2a3	1.83E+15	+-	8.72E+11	1.83E+15	3003259	380		7.60E+23
	0	a2a4	2.57E+15	+-	1.02E+12	2.57E+15	4132693	420		1.05E+24
	0	g1h3	2.13E+15	+-	9.27E+11	2.13E+15	3397418	400		8.59E+23
	0	g1f3	2.71E+15	+-	1.02E+12	2.70E+15	4126985	440		1.04E+24
	0	b1c3	2.73E+15	+-	1.07E+12	2.73E+15	4566754	440		1.16E+24
	0	b1a3	2.10E+15	+-	9.37E+11	2.10E+15	3467229	400		8.77E+23
										
			6.285595E+16			6.285888E+16	99790000	8902		2.524295E+25
										
			Mean	6.285742E+16						
			StdDev	5.024237E+12						
			Error	2.5155E+12																	

If you need log files for all iterations, I will upload them.
Next test will be with a non-stop expansion for all formulas ...

Daniel

[Daniel Shawul]

Hi Jesus

Thanks for the detailed work. I also tried something similar by taking result of perft(12) and perft(11) with two consecutive moves. At the time I tried it I didn't include the odd-even effect so my result wasn't good. But with your formula which takes care of that effect you should be able to get a fine grained result. Please upload the Excel workbooks.

Adam's approach to include actual games from FICS also sound interesting.

cheers
Daniel

[Ajedrecista]

Hi Jesus

Thanks for the detailed work. I also tried something similar by taking result of perft(12) and perft(11) with two consecutive moves. At the time I tried it I didn't include the odd-even effect so my result wasn't good. But with your formula which takes care of that effect you should be able to get a fine grained result. Please upload the Excel workbooks.

Adam's approach to include actual games from FICS also sound interesting.

cheers
Daniel

Hi Daniel:

Here is the link:

http://www.megaupload.com/?d=1VLUGB78

As you see, the name of the file is Perft_percentages.rar and I add: 'The name of the file is telltale'. As usual I am wrong: the name of the file should be Perft_percentages_for_the_game_of_chess.rar (because there are Perft values for chess, checkers, Othello/Reversi... ).

I hope it will be useful for you and not only for you...

Regards from Spain.

Ajedrecista.

[sje]

These ever larger draft 10 records keep on going:
[d]rnbqkbnr/1ppppppp/p7/8/8/2N1P3/PPPP1PPP/R1BQKBNR b KQkq - 0 2
Perft(10): 296,867,706,070,158

The first draft 11 subtotals should appear in about a week.

[hgm]

And here's another with the largest perft(10) found so far:
[d]rnbqkbnr/1ppppppp/p7/8/3P4/N7/PPP1PPPP/R1BQKBNR b KQkq - 0 2
The perft(10) for the above is 180,064,345,219,110.

perft(10)= ca.1.800791e+14 (1903.170 sec) 30.983062

That is an error of +0.0082%. Extrapolated empirical SD=0.0056%.

[hgm]

These ever larger draft 10 records keep on going:
[d]rnbqkbnr/1ppppppp/p7/8/8/2N1P3/PPPP1PPP/R1BQKBNR b KQkq - 0 2
Perft(10): 296,867,706,070,158

The first draft 11 subtotals should appear in about a week.

perft(10)= ca.2.968756e+14 (-1356.077 sec) 30.979567

Error = +0.0027%

[Daniel Shawul]

I have a possilbe new number one using proportioning by standard error instead of the variance.
Calculated variance and proportioning by tree size are more or less similar with
many number of games. But using the standard deviation instead gave a better result (I think) atleast in estimating the mean..

Code: Select all

			Mean	6.285437E+16						
			StdDev	5.212337E+12						
			Error	5.3E+11

Its standard deviation is slightly larger than both tree and calc. variance version but the error
with the actual mean is magnitudes smaller. It had very good intermediate results for both perft values but
got a little bit worse in the end.

Another variant I tried is to have the same standard deviation for all moves! (see the 1.55e12 stderror for all moves below). This weird looking constraint has revealed a possible problem.
It has done an irreparable damage to the first perft estimate which is used for move selection.
Even after 100 million iterations the first estimate is at 6.282e16. Intermediate estimates are much worse.
So I think not using the first estimate all in all even when having a split depth constraint is something to consider.

Code: Select all

			Mean	6.283614E+16						
			StdDev	6.916737E+12						
			Error	1.87625E+13

Code: Select all

Equal std	
	0	h2h3	1.81E+15	+-	1.55E+12	1.82E+15	1425865	380		2.39E+24
	0	h2h4	2.62E+15	+-	1.55E+12	2.62E+15	2884306	420		2.39E+24
	0	g2g3	2.50E+15	+-	1.55E+12	2.49E+15	2502763	420		2.39E+24
	0	g2g4	2.22E+15	+-	1.55E+12	2.22E+15	1705969	421		2.39E+24
	0	f2f3	1.55E+15	+-	1.55E+12	1.55E+15	846748	380		2.39E+24
	0	f2f4	2.05E+15	+-	1.55E+12	2.05E+15	1796446	401		2.39E+24
	0	e2e3	7.16E+15	+-	1.55E+12	7.16E+15	20995846	599		2.39E+24
	0	e2e4	7.26E+15	+-	1.55E+12	7.26E+15	20142018	600		2.39E+24
	0	d2d3	4.59E+15	+-	1.55E+12	4.59E+15	6366435	539		2.39E+24
	0	d2d4	6.33E+15	+-	1.55E+12	6.33E+15	15512703	560		2.39E+24
	0	c2c3	2.75E+15	+-	1.55E+12	2.75E+15	3068007	420		2.39E+24
	0	c2c4	3.12E+15	+-	1.55E+12	3.12E+15	3859430	441		2.39E+24
	0	b2b3	2.40E+15	+-	1.55E+12	2.41E+15	2417406	420		2.39E+24
	0	b2b4	2.41E+15	+-	1.55E+12	2.41E+15	2320316	421		2.39E+24
	0	a2a3	1.82E+15	+-	1.55E+12	1.82E+15	1497705	380		2.39E+24
	0	a2a4	2.57E+15	+-	1.55E+12	2.57E+15	2756916	420		2.39E+24
	0	g1h3	2.13E+15	+-	1.55E+12	2.13E+15	1827200	400		2.39E+24
	0	g1f3	2.71E+15	+-	1.55E+12	2.71E+15	2547848	440		2.39E+24
	0	b1c3	2.73E+15	+-	1.55E+12	2.73E+15	3390280	440		2.39E+24
	0	b1a3	2.10E+15	+-	1.55E+12	2.10E+15	1925793	400		2.39E+24
										
			6.282292E+16			6.284936E+16	99790000	8902		4.784125E+25
										
			Mean	6.283614E+16						
			StdDev	6.916737E+12						
			Error	1.87625E+13			

Stddev	
	0	h2h3	1.81E+15	+-	8.03E+11	1.81E+15	3623153	380		6.44E+23
	0	h2h4	2.62E+15	+-	1.02E+12	2.62E+15	4594931	420		1.04E+24
	0	g2g3	2.50E+15	+-	9.76E+11	2.50E+15	4405621	420		9.52E+23
	0	g2g4	2.22E+15	+-	8.73E+11	2.22E+15	3938972	421		7.61E+23
	0	f2f3	1.55E+15	+-	6.94E+11	1.55E+15	3132723	380		4.82E+23
	0	f2f4	2.05E+15	+-	8.73E+11	2.05E+15	3942728	401		7.63E+23
	0	e2e3	7.16E+15	+-	1.98E+12	7.16E+15	8958211	599		3.94E+24
	0	e2e4	7.27E+15	+-	1.98E+12	7.26E+15	8928458	600		3.91E+24
	0	d2d3	4.59E+15	+-	1.37E+12	4.59E+15	6183808	539		1.88E+24
	0	d2d4	6.33E+15	+-	1.80E+12	6.33E+15	8129509	560		3.24E+24
	0	c2c3	2.75E+15	+-	1.05E+12	2.75E+15	4728075	420		1.10E+24
	0	c2c4	3.12E+15	+-	1.13E+12	3.12E+15	5119144	441		1.29E+24
	0	b2b3	2.41E+15	+-	9.57E+11	2.41E+15	4319738	420		9.16E+23
	0	b2b4	2.41E+15	+-	9.50E+11	2.41E+15	4287109	421		9.02E+23
	0	a2a3	1.83E+15	+-	8.11E+11	1.82E+15	3660697	380		6.57E+23
	0	a2a4	2.57E+15	+-	1.00E+12	2.57E+15	4516322	420		1.00E+24
	0	g1h3	2.13E+15	+-	8.78E+11	2.13E+15	3964579	400		7.71E+23
	0	g1f3	2.71E+15	+-	9.98E+11	2.70E+15	4503755	440		9.95E+23
	0	b1c3	2.73E+15	+-	1.07E+12	2.73E+15	4831800	440		1.15E+24
	0	b1a3	2.10E+15	+-	8.91E+11	2.10E+15	4020667	400		7.93E+23
										
			6.285870E+16			6.285004E+16	99790000	8902		2.716845E+25
										
			Mean	6.285437E+16						
			StdDev	5.212337E+12						
			Error	5.3E+11

[Daniel Shawul]

New number one(s) with free splitting All of them are better than their previous
counterparts that had splitting limited to depth=3. The variances are consistently lower. With free splitting all reached depth=5 in different degree (some methods split more than others with uniform being the least splitter.).
As you can see the sub-tree node counts in the last column are between perft(4) and perft(5) so some moves reached depth = 5.
Also now with the free splitting version, the first perft result is _magnitudes_ lower (about 6.26e16)
which was remedied by fixing split depth to 3 in the previous test. Now I only take the _second_ perft result because
the first one is corrupt. I think this was a crucial reason for all the pessimism with splitting.
Again the same order is maintained with uniform taking the last place yet again! It is also the least expanding of all (has smallest leaf nodes in last column). So expanding is good !!

Calculated variance:

Code: Select all

			Mean	6.284884E+16						
			StdDev	4.228939E+12						
			Error	6.065E+12

Tree:

Code: Select all

			Mean	6.285686E+16						
			StdDev	4.296145E+12						
			Error	1.961E+12

Uniform:

Code: Select all

			Mean	6.286074E+16						
			StdDev	6.560454E+12						
			Error	5.8415E+12

The sub-tree size method has surprisingly very low error which I think is due to luck.
I forgot to test Log-tree formula so that is running now. Also I have one more promising formula.
Upto now we were assuming the biggest variance implies biggest reduction. But calculating the actual
reduction if one more game is played yields the following:

Code: Select all

Original variance = sigma^2 / N
After one game = sigma^2 / (N + 1)

Reduction = sigma^2 / N - sigma^2 / (N + 1)
          = sigma^2 (1 / N - 1 / N + 1)
          = sigma^2 (1 / N * (N + 1) 
          = (sigma^2 / N) / (N + 1)
          = Original variance / (N + 1)

So the new method proportions variance / (visits + 1) instead of proportioning variance or sub-tree size
which are giving close results up to now. But this new formula may give even more reductions of variance. So instead of
proportioning sub-tree size directly proportion sub-tree_size / (visits + 1). This gives a new bread of formulas where the variance estimate is divided by the number of visits. If variance is calculated a simple direct formula like below will suffice.

Code: Select all

X = variance / (visits + 1)

When we have relative magnitudes of variance as in case of sub-tree size formula will be something like

Code: Select all

(sub_tree / (visits + 1)) / Sum(sub_tree_i / (visits_i + 1) - visits / parent_visits

This and the log-tree size are being tested now. Results tomorrow.

------------------------------------------------------------------------------------------
Finally the detailed results after

Code: Select all

Variance	
	0	h2h3	1.81E+15	+-	7.45E+11	1.81E+15	2246679	30401		5.56E+23
	0	h2h4	2.61E+15	+-	8.74E+11	2.62E+15	3088588	52908		7.64E+23
	0	g2g3	2.49E+15	+-	8.53E+11	2.50E+15	2940879	48150		7.27E+23
	0	g2g4	2.21E+15	+-	7.97E+11	2.22E+15	2570588	36249		6.36E+23
	0	f2f3	1.55E+15	+-	6.78E+11	1.55E+15	1860964	19121		4.60E+23
	0	f2f4	2.04E+15	+-	7.94E+11	2.05E+15	2547363	35374		6.30E+23
	0	e2e3	7.12E+15	+-	1.40E+12	7.16E+15	7944677	235545		1.96E+24
	0	e2e4	7.23E+15	+-	1.41E+12	7.26E+15	8004922	241199		1.98E+24
	0	d2d3	4.57E+15	+-	1.09E+12	4.59E+15	4762806	104410		1.18E+24
	0	d2d4	6.30E+15	+-	1.30E+12	6.33E+15	6872198	192250		1.70E+24
	0	c2c3	2.74E+15	+-	9.00E+11	2.75E+15	3276770	60860		8.10E+23
	0	c2c4	3.11E+15	+-	9.45E+11	3.12E+15	3612423	69277		8.93E+23
	0	b2b3	2.40E+15	+-	8.41E+11	2.41E+15	2860325	46234		7.07E+23
	0	b2b4	2.40E+15	+-	8.41E+11	2.41E+15	2858815	47922		7.07E+23
	0	a2a3	1.82E+15	+-	7.47E+11	1.83E+15	2259511	31910		5.59E+23
	0	a2a4	2.56E+15	+-	8.65E+11	2.57E+15	3029070	51751		7.49E+23
	0	g1h3	2.12E+15	+-	7.95E+11	2.13E+15	2557315	36773		6.32E+23
	0	g1f3	2.70E+15	+-	8.69E+11	2.70E+15	3051072	46839		7.54E+23
	0	b1c3	2.72E+15	+-	9.12E+11	2.73E+15	3366765	65087		8.32E+23
	0	b1a3	2.09E+15	+-	8.04E+11	2.10E+15	2615814	39991		6.47E+23
										
			6.259669E+16			6.284884E+16	72327544	1492251		1.788393E+25
										
			Mean	6.284884E+16						
			StdDev	4.228939E+12						
			Error	6.065E+12						
										
Tree	
	0	h2h3	1.81E+15	+-	7.80E+11	1.81E+15	2153105	27774		6.08E+23
	0	h2h4	2.61E+15	+-	8.98E+11	2.62E+15	3113078	46170		8.06E+23
	0	g2g3	2.49E+15	+-	8.73E+11	2.50E+15	2967735	43368		7.62E+23
	0	g2g4	2.21E+15	+-	8.02E+11	2.22E+15	2633698	35531		6.43E+23
	0	f2f3	1.55E+15	+-	6.91E+11	1.55E+15	1845527	19363		4.77E+23
	0	f2f4	2.04E+15	+-	8.31E+11	2.05E+15	2435554	30220		6.91E+23
	0	e2e3	7.11E+15	+-	1.41E+12	7.16E+15	8478978	215574		1.98E+24
	0	e2e4	7.21E+15	+-	1.41E+12	7.26E+15	8600537	223083		1.99E+24
	0	d2d3	4.57E+15	+-	1.03E+12	4.59E+15	5445860	119953		1.07E+24
	0	d2d4	6.29E+15	+-	1.29E+12	6.33E+15	7499461	181871		1.67E+24
	0	c2c3	2.74E+15	+-	9.27E+11	2.75E+15	3263329	53607		8.60E+23
	0	c2c4	3.11E+15	+-	9.56E+11	3.12E+15	3702790	64214		9.15E+23
	0	b2b3	2.40E+15	+-	8.66E+11	2.41E+15	2860760	41119		7.50E+23
	0	b2b4	2.40E+15	+-	8.62E+11	2.41E+15	2866607	43407		7.44E+23
	0	a2a3	1.82E+15	+-	7.85E+11	1.83E+15	2167989	27894		6.17E+23
	0	a2a4	2.56E+15	+-	8.88E+11	2.57E+15	3053980	45286		7.88E+23
	0	g1h3	2.13E+15	+-	8.19E+11	2.13E+15	2533876	33173		6.71E+23
	0	g1f3	2.70E+15	+-	8.65E+11	2.70E+15	3213441	46427		7.48E+23
	0	b1c3	2.72E+15	+-	9.74E+11	2.73E+15	3241380	49567		9.48E+23
	0	b1a3	2.09E+15	+-	8.50E+11	2.10E+15	2494315	32696		7.22E+23
										
			6.254641E+16			6.285686E+16	74572000	1380297		1.845686E+25
										
			Mean	6.285686E+16						
			StdDev	4.296145E+12						
			Error	1.961E+12						
										
Uniform
	0	h2h3	1.81E+15	+-	7.71E+11	1.81E+15	4066875	94451		5.95E+23
	0	h2h4	2.62E+15	+-	1.11E+12	2.62E+15	4066875	39809		1.24E+24
	0	g2g3	2.50E+15	+-	1.04E+12	2.50E+15	4066875	31266		1.08E+24
	0	g2g4	2.22E+15	+-	8.63E+11	2.22E+15	4066875	38420		7.45E+23
	0	f2f3	1.55E+15	+-	5.91E+11	1.55E+15	4066875	91295		3.50E+23
	0	f2f4	2.05E+15	+-	8.80E+11	2.05E+15	4066875	56694		7.74E+23
	0	e2e3	7.16E+15	+-	3.02E+12	7.16E+15	4066875	13539		9.13E+24
	0	e2e4	7.27E+15	+-	2.98E+12	7.26E+15	4066875	13571		8.87E+24
	0	d2d3	4.59E+15	+-	1.61E+12	4.59E+15	4066875	11959		2.60E+24
	0	d2d4	6.32E+15	+-	2.57E+12	6.33E+15	4066875	12435		6.59E+24
	0	c2c3	2.75E+15	+-	1.16E+12	2.75E+15	4066875	35487		1.34E+24
	0	c2c4	3.12E+15	+-	1.28E+12	3.12E+15	4066875	14817		1.63E+24
	0	b2b3	2.41E+15	+-	1.03E+12	2.41E+15	4066875	30355		1.06E+24
	0	b2b4	2.41E+15	+-	1.01E+12	2.41E+15	4066875	38012		1.02E+24
	0	a2a3	1.83E+15	+-	7.91E+11	1.82E+15	4066875	94786		6.26E+23
	0	a2a4	2.57E+15	+-	1.08E+12	2.57E+15	4066875	39616		1.17E+24
	0	g1h3	2.13E+15	+-	8.82E+11	2.13E+15	4066875	54557		7.78E+23
	0	g1f3	2.70E+15	+-	1.03E+12	2.70E+15	4066875	12372		1.07E+24
	0	b1c3	2.73E+15	+-	1.24E+12	2.73E+15	4066875	11639		1.53E+24
	0	b1a3	2.10E+15	+-	9.15E+11	2.10E+15	4066875	53797		8.38E+23
										
			6.286164E+16			6.285985E+16	81337500	788877		4.303955E+25
										
			Mean	6.286074E+16						
			StdDev	6.560454E+12						
			Error	5.8415E+12						

[Daniel Shawul]

The sub-tree size method has surprisingly very low error which I think is due to luck.
I forgot to test Log-tree formula so that is running now. Also I have one more promising formula.
Upto now we were assuming the biggest variance implies biggest reduction. But calculating the actual
reduction if one more game is played yields the following:
Code:

Original variance = sigma^2 / N
After one game = sigma^2 / (N + 1)

Reduction = sigma^2 / N - sigma^2 / (N + 1)
= sigma^2 (1 / N - 1 / N + 1)
= sigma^2 (1 / N * (N + 1)
= (sigma^2 / N) / (N + 1)
= Original variance / (N + 1)

So the new method proportions variance / (visits + 1) instead of proportioning variance or sub-tree size
which are giving close results up to now. But this new formula may give even more reductions of variance. So instead of
proportioning sub-tree size directly proportion sub-tree_size / (visits + 1). This gives a new bread of formulas where the variance estimate is divided by the number of visits. If variance is calculated a simple direct formula like below will suffice.

This has become the new number one ! It improved the leader of both the limited splitting version and the free splitting version by the tiniest of margins possible But it clearly makes the point that the accepted concept that "picking the node with biggest variance" is wrong. It should have been defined "pick the node that results in biggest reduction in variance". The smallest node could be picked depending on the number of visits.. The improvement is minute but it is still an improvement ..

Limited split version

Mean 6.284999E+16
StdDev 5.023038E+12
Error 4.908E+12

Free split version:

Mean 6.284786E+16
StdDev 4.227828E+12
Error 7.04E+12

For comparison previous best had 5.024237E+12 and 4.228939E+12 , so you can see the improvements are only in the third significant in both cases! What matters is that it is consistent.

Code: Select all

Limited	
	0	h2h3	1.81E+15	+-	8.66E+11	1.81E+15	2963618	380		7.49E+23	
	0	h2h4	2.62E+15	+-	1.03E+12	2.62E+15	4226457	420		1.07E+24	
	0	g2g3	2.50E+15	+-	1.00E+12	2.50E+15	3970767	420		1.00E+24	
	0	g2g4	2.22E+15	+-	9.24E+11	2.22E+15	3378481	421		8.54E+23	
	0	f2f3	1.55E+15	+-	7.78E+11	1.55E+15	2395142	380		6.06E+23	
	0	f2f4	2.05E+15	+-	9.24E+11	2.05E+15	3373205	401		8.53E+23	
	0	e2e3	7.16E+15	+-	1.71E+12	7.16E+15	11544830	599		2.92E+24	
	0	e2e4	7.26E+15	+-	1.71E+12	7.27E+15	11511685	600		2.91E+24	
	0	d2d3	4.59E+15	+-	1.30E+12	4.59E+15	6659446	539		1.68E+24	
	0	d2d4	6.33E+15	+-	1.59E+12	6.33E+15	9985348	560		2.52E+24	
	0	c2c3	2.75E+15	+-	1.06E+12	2.75E+15	4437864	420		1.12E+24	
	0	c2c4	3.12E+15	+-	1.12E+12	3.12E+15	4989436	441		1.26E+24	
	0	b2b3	2.41E+15	+-	9.87E+11	2.41E+15	3852285	420		9.74E+23	
	0	b2b4	2.41E+15	+-	9.82E+11	2.41E+15	3815679	421		9.65E+23	
	0	a2a3	1.82E+15	+-	8.71E+11	1.83E+15	3002267	380		7.59E+23	
	0	a2a4	2.57E+15	+-	1.02E+12	2.57E+15	4136616	420		1.05E+24	
	0	g1h3	2.13E+15	+-	9.27E+11	2.13E+15	3401499	400		8.60E+23	
	0	g1f3	2.70E+15	+-	1.02E+12	2.70E+15	4121596	440		1.04E+24	
	0	b1c3	2.73E+15	+-	1.07E+12	2.73E+15	4556724	440		1.15E+24	
	0	b1a3	2.10E+15	+-	9.36E+11	2.10E+15	3467055	400		8.77E+23	
											
			6.284704E+16			6.285295E+16	99790000	8902		2.523091E+25	
											
			Mean	6.284999E+16							
			StdDev	5.023038E+12							
			Error	4.908E+12							
Free	
	0	h2h3	1.81E+15	+-	7.45E+11	1.81E+15	2247932	30085		5.55E+23	
	0	h2h4	2.61E+15	+-	8.74E+11	2.62E+15	3090436	52975		7.63E+23	
	0	g2g3	2.49E+15	+-	8.52E+11	2.50E+15	2941248	48070		7.26E+23	
	0	g2g4	2.21E+15	+-	7.97E+11	2.22E+15	2571397	35908		6.35E+23	
	0	f2f3	1.55E+15	+-	6.78E+11	1.55E+15	1862377	19373		4.60E+23	
	0	f2f4	2.04E+15	+-	7.92E+11	2.05E+15	2541593	35576		6.28E+23	
	0	e2e3	7.12E+15	+-	1.40E+12	7.16E+15	7948046	236421		1.96E+24	
	0	e2e4	7.23E+15	+-	1.41E+12	7.27E+15	8011660	241655		1.98E+24	
	0	d2d3	4.57E+15	+-	1.09E+12	4.59E+15	4766317	104671		1.18E+24	
	0	d2d4	6.30E+15	+-	1.30E+12	6.33E+15	6877990	192311		1.70E+24	
	0	c2c3	2.74E+15	+-	9.00E+11	2.75E+15	3279578	60794		8.10E+23	
	0	c2c4	3.11E+15	+-	9.44E+11	3.12E+15	3610423	69145		8.92E+23	
	0	b2b3	2.40E+15	+-	8.41E+11	2.41E+15	2863543	45732		7.07E+23	
	0	b2b4	2.40E+15	+-	8.41E+11	2.41E+15	2861656	48135		7.07E+23	
	0	a2a3	1.82E+15	+-	7.47E+11	1.83E+15	2261152	31129		5.58E+23	
	0	a2a4	2.56E+15	+-	8.65E+11	2.57E+15	3027060	51219		7.48E+23	
	0	g1h3	2.12E+15	+-	7.95E+11	2.13E+15	2557694	36641		6.32E+23	
	0	g1f3	2.70E+15	+-	8.69E+11	2.70E+15	3054686	47059		7.54E+23	
	0	b1c3	2.72E+15	+-	9.12E+11	2.73E+15	3370326	64958		8.32E+23	
	0	b1a3	2.09E+15	+-	8.05E+11	2.10E+15	2622886	39487		6.48E+23	
											
			6.259693E+16			6.284786E+16	72368000	1491344		1.787453E+25	
											
			Mean	6.284786E+16							
			StdDev	4.227828E+12							
			Error	7.04E+12

[hgm]

I have completely lost track of what you are doing. Which is OK, because I am only interested in comparing the outcome tomy own results. But the standard deviations and errors you quote, how many games did you have to play to obtain those?