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
Code: Select all
Mean 6.285823E+16
StdDev 5.047898E+12
Error 3.3345E+12
Code: Select all
Mean 6.285624E+16
StdDev 5.725446E+12
Error 1.337E+12
Code: Select all
Mean 6.284984E+16
StdDev 6.919680E+12
Error 5.0615E+12
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
Next test will be with a non-stop expansion for all formulas ...
Daniel