Perft(13) betting pool

Daniel Shawul · Post by **Daniel Shawul** » Sat Aug 06, 2011 11:53 pm

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 · Post by **Daniel Shawul** » Sun Aug 07, 2011 3:39 am

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 / &#40;N + 1&#41;

Reduction = sigma^2 / N - sigma^2 / &#40;N + 1&#41;
          = sigma^2 &#40;1 / N - 1 / N + 1&#41;
          = sigma^2 &#40;1 / N * &#40;N + 1&#41; 
          = &#40;sigma^2 / N&#41; / &#40;N + 1&#41;
          = Original variance / &#40;N + 1&#41;

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 / &#40;visits + 1&#41;

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

Code: Select all

&#40;sub_tree / &#40;visits + 1&#41;) / Sum&#40;sub_tree_i / &#40;visits_i + 1&#41; - 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 · Post by **Daniel Shawul** » Sun Aug 07, 2011 5:18 am

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 · Post by **hgm** » Sun Aug 07, 2011 10:13 am

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?

Daniel Shawul · Post by **Daniel Shawul** » Sun Aug 07, 2011 1:20 pm

hgm wrote: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?

I am not sure what you want to compare. Well what I am doing is comparing the effect of splitting using different formulas available to me. AFAIK you expand to a fixed depth uniformly so that will be "uniform" in my tests. All tests are done with a fixed number of simulations so the actual number doesn't matter. Anyway I have mentioned it many times already 100 mil

Daniel Shawul · Post by **Daniel Shawul** » Sun Aug 07, 2011 1:35 pm

And here is the missing Log-tree size result with free splitting versions. I think it has come in fourth place (i.e after the new number one is added) .

Code: Select all

Mean	6.286348E+16							
			StdDev	4.966971E+12							
			Error	8.583E+12

And detailed result

Code: Select all

Log-tree size	
0	h2h3	1.81E+15	+-	6.93E+11	1.81E+15	2939466	33797		4.80E+23	
	0	h2h4	2.61E+15	+-	8.55E+11	2.62E+15	3660969	58215		7.30E+23	
	0	g2g3	2.49E+15	+-	8.18E+11	2.50E+15	3566734	54204		6.68E+23	
	0	g2g4	2.21E+15	+-	7.32E+11	2.22E+15	3335250	42521		5.36E+23	
	0	f2f3	1.55E+15	+-	6.03E+11	1.55E+15	2636787	20806		3.63E+23	
	0	f2f4	2.04E+15	+-	7.52E+11	2.05E+15	3179819	39369		5.66E+23	
	0	e2e3	7.10E+15	+-	2.17E+12	7.16E+15	5629451	141422		4.70E+24	
	0	e2e4	7.20E+15	+-	2.35E+12	7.27E+15	5657350	141739		5.52E+24	
	0	d2d3	4.57E+15	+-	1.17E+12	4.59E+15	4763097	84516		1.37E+24	
	0	d2d4	6.28E+15	+-	1.65E+12	6.33E+15	5388945	125126		2.73E+24	
	0	c2c3	2.74E+15	+-	8.93E+11	2.75E+15	3756436	67732		7.97E+23	
	0	c2c4	3.10E+15	+-	1.00E+12	3.12E+15	4001560	72858		1.00E+24	
	0	b2b3	2.40E+15	+-	8.08E+11	2.41E+15	3494193	51282		6.52E+23	
	0	b2b4	2.40E+15	+-	8.00E+11	2.41E+15	3499493	52710		6.39E+23	
	0	a2a3	1.82E+15	+-	6.99E+11	1.83E+15	2951167	34338		4.89E+23	
	0	a2a4	2.56E+15	+-	8.42E+11	2.57E+15	3623677	57003		7.10E+23	
	0	g1h3	2.12E+15	+-	7.44E+11	2.13E+15	3257143	42625		5.54E+23	
	0	g1f3	2.69E+15	+-	8.31E+11	2.70E+15	3723154	53329		6.91E+23	
	0	b1c3	2.72E+15	+-	9.35E+11	2.73E+15	3741753	59205		8.75E+23	
	0	b1a3	2.09E+15	+-	7.69E+11	2.10E+15	3226556	42175		5.91E+23	
											
			6.252344E+16			6.286348E+16	76033000	1274972		2.467080E+25	
											
			Mean	6.286348E+16							
			StdDev	4.966971E+12							
			Error	8.583E+12

sje · Post by **sje** » Sun Aug 07, 2011 3:49 pm

Yet another piece of perft(13), the first draft 11 result from the current run:
[D]rnbqkbnr/1ppppppp/p7/8/8/N7/PPPPPPPP/R1BQKBNR w KQkq - 0 2
perft(11): 1,865,423,942,798,492

One down, 399 to go.

hgm · Post by **hgm** » Sun Aug 07, 2011 4:08 pm

Daniel Shawul wrote:
hgm wrote: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?
I am not sure what you want to compare. Well what I am doing is comparing the effect of splitting using different formulas available to me. AFAIK you expand to a fixed depth uniformly so that will be "uniform" in my tests. All tests are done with a fixed number of simulations so the actual number doesn't matter. Anyway I have mentioned it many times already 100 mil

So this would be comparable (in effort) as when I start from a 6-ply full-with from the opening position, which is about 119M paths? The errors you quote do seem all larger, which made me wonder.

Daniel Shawul · Post by **Daniel Shawul** » Sun Aug 07, 2011 5:02 pm

hgm wrote:
Daniel Shawul wrote:
hgm wrote: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?
I am not sure what you want to compare. Well what I am doing is comparing the effect of splitting using different formulas available to me. AFAIK you expand to a fixed depth uniformly so that will be "uniform" in my tests. All tests are done with a fixed number of simulations so the actual number doesn't matter. Anyway I have mentioned it many times already 100 mil
So this would be comparable (in effort) as when I start from a 6-ply full-with from the opening position, which is about 119M paths? The errors you quote do seem all larger, which made me wonder.

No. Your MC part is heavy. Peter's (a.k.a pure monte-carlo) simulation considers only one move. So it is not comparable in effort. Also I am not sure how you do your tests ,but do you visit the perft(6) nodes only once to get your result? And the maximum depth of expansion for the uniform selector is 5 not 6 (i.e the maximum number of nodes I store in memory). See the column second from last which prints the number of nodes stored for each move.
Edit: I see that with the expansion method a certain number of simulations are required for a node before split . So the equivalent
will be to visit each perft(5) node 100,000,000 / perft(5) ~= 20.55 times. And that with a simple MC should be the equivalent.

Anyway you are missing the whole point. The MC part is a black box to me and I am only comparing different ways of splitting. Your version of MC does more work but doesn't mean it is better.
(a) Pure MC gave better results (lower variance) per _simulation time_ or so I read, and also is easier to implement.
(b) If indeed you have a better MC simulator I can use that and I should be able to get better results with one of the non-unirorm splitters because uniform method ,as you do it now, is consistently performing as the worst now.
(c) I have tested doing 2 monte carlo simulations instead of 1 for the leaf nodes and it gives lower variance as expected. Obviously the more work you do in the MC part the lower the variance.
Given all of the above, it is good to take the MC part out of the equation unless there is some interaction with upper part.

hgm · Post by **hgm** » Sun Aug 07, 2011 5:51 pm

Well, there is obviously more than one point I don't get. Like what you mean by "MC part" or "heavy". Also, with 1 move you cannot get perft(12) in any method.That needs at least 12 moves, and the std deviation would be huge (close to 100%, or even larger) in that case.

When I am talking about 119M paths I do indeed mean I visit every perft(6) leaf exactly once. But in fact the number of paths that make it all the way to 11 ply is only 62M (because the acceptance probability 1/32 is smaller than the inverse average branching factor). On the 12th ply I don't do any move at all, of course, but I count (and thus have to generate) moves in the 11-ply nodes. But I guess Peter's method has to do that too, to get the factor for that ply.

So it seems my effort is some where between 62M and 119M 12-ply games (the initial 5 plies being highly combined,and thus not really contributing to the effort). Why is that more effort than your generation of 100M games?

Perft(13) betting pool

Re: Defect of a node?

Re: Defect of a node?

Re: Defect of a node?

Re: Defect of a node?

Re: Defect of a node?

Re: Defect of a node?

Yet another piece of perft(13)

Re: Defect of a node?

Re: Defect of a node?

Re: Defect of a node?