Perft(13) betting pool

[Michel]

I did a quick variance computation for a uniform tree and it seems
that in that case Peter's method with uniform sampling has a higher efficiency
(defined as effort x variance) than HGM's method unless the acceptance probability is 1....

Efficiency is a bad name of course since you want to the product effort x variance to be as _low_ as possible. I don't quite know what a good name
would be.

[hgm]

Experimental determination of the variance for the perft(10) estimate when I start sampling at ply 4 or ply 5 (so that I can quickly repeat it many hundreds of times with different seeds) are 0.7% and 0.095%, respectively. I don't know if that fits your theoretical calculation.

[Michel]

I don't know if that fits your theoretical calculation.

I assume you gave standard deviations. Not variances.

I get SD's which are a bit too big but the orders of magnitude seem correct.
Which is not so bad given the simplified model.

I computed how the variance propagates. With the usual
notation: if at a certain ply the acceptance probability
is p then the propagated variance is

sum_i [ (1/p)(x_i^2+s_i^2)-x_i^2 ]

(this assumes the X_i are independent).

Assuming the tree is completely uniform this translates into a linear recursion relation for the variance. I took EBF=perft(10)^(1/10)=30.9

I found the following standard deviations.

0.04% for sampling at ply 6
0.24% for sampling at ply 5
1.48% for sampling at ply 4

The fact that the actual sd's are smaller might indicate that the
tree is not really uniform and that your algorithm adapts to this
non uniformity.

[hgm]

Indeed, they were SD. Sorry.

[Michel]

0.04% for sampling at ply 6
0.24% for sampling at ply 5
1.48% for sampling at ply 4

I redid the computation with the correct EBF's at each ply. It does
make much of a difference. The SD's are still over estimated.
If I did not make a mistake then this means that the tree is not completely
uniform.

[Michel]

This quantity (s is the SD and x is the tree size)

d=sqrt(x^2+s^2)-x

which I proposed in my tree splitting heuristic here

http://talkchess.com/forum/viewtopic.ph ... 24&t=39678

has rather interesting properties with respect to MC sampling.
Let's call it the "defect" of a node.

(1) The defect of a node is greater or equal than the sum of
the defects of its children with equality if and only if sampling with
optimal weights is used.

(2) If the variance is zero then the defect is zero.

A quantity with such nice mathematical properties is bound to have applications!

[Michel]

The properties of the "defect" (see above post) give a new take
on my tree splitting heuristic.

Suppose we maintain a subtree around the root for which have determined
(close to) ideal weights. The defect of the root node is the sum of the defects
of the leaf nodes of this tree.

If we want to reduce the defect in the root node then it make sense
to grow the subtree in a leaf node with the greatest "potential" for total
defect reduction. I.e. the leaf node which has itself the largest defect.

[Daniel Shawul]

@ Michel
I have two comments. The first is the lack of "visits" in your formula. After a number of simulations are conducted on the sub-tree selected by your optimal formula, its priority should go down so that other siblings are explored. How do you intend to introduce that? Currently I have the constant in the UCT formula at 10 to get good exploration. Taking the ratio of logarithms for the mean value seems natural to bring down the Constant in the UCT formula to the level used in regular UCT search. The UCB formula works in such a way the optimal node is explored exponentially more than the others. The reward as you mentioned earlier should be the reduction in variance after a simulation. Since that is hard to calculate I just use the ratio of the child nodes to parent nodes (now by taking log) to estimate the mean reward.Here is the original UCB formula derivation explaining its application for a multi armed bandit problem

So right now the formula I use is

Code: Select all

X = (log(child_nodes) / log(parent_nodes))
      +  Constant * sqrt( log(parent_visits) / child_visits)

I think that your formula should include the visits count too.

Another problem I have with splitting for perft is that once a node is decided to be split (f.i after its visit count reaches 1000), then the previous result becomes almost void. I will just do (1000/number_of_moves) on each move and start with the new estimate. I tried to combine the old result into the new one but did not have success so far. If the splitting is done only after a lot of MC simulations , then the two results can be averaged using (new + old) / 2 because the MC simulation will almost give same number of games to each move with a uniform PRNG. So right now whenever I split , there are some "wasted" simulations. I still increment the simulations count properly though not to bias comparison of performance. Hope it is clear enough.

A suggestion for comparing different methodologies : We should compare estimates for fixed number of simulations to avoid for difference in speed of perft (hash tables , programming language etc..). Also when simulations start at ply=3, and the maximum allowed N = 1 million, then
each 8902 move should get only (1 million / 8902) simulations...

[Daniel Shawul]

Here is a simplistic formula for variance reduction.

Code: Select all

X = (child_nodes / parent_nodes) - (child_visits / parent_visits)

So this will try to match exactly the proportion of visits (probability p) with the ratio of nodes, which is what we think will reduce the variance significantly. I can also take the log if that makes more sense.. Anyway, I think you should modify your formula like that. The default UCB formula gives exponentially more visits to the selected node so it might not be optimum..

I did a test without splitting that is only at the root for perft(12). First for uniform allocation every x million simulations upto 20 million. The exact perft value is 6.2854e16 for comparison.

Code: Select all

------------ 8 --------------
0 h2h3   1.813302e+015  400000
0 h2h4   2.616134e+015  400000
0 g2g3   2.495857e+015  400000
0 g2g4   2.216429e+015  400000
0 f2f3   1.554160e+015  400000
0 f2f4   2.048562e+015  400000
0 e2e3   7.166771e+015  400000
0 e2e4   7.249186e+015  400000
0 d2d3   4.583958e+015  400000
0 d2d4   6.333048e+015  400000
0 c2c3   2.753783e+015  400000
0 c2c4   3.127248e+015  400000
0 b2b3   2.408044e+015  400000
0 b2b4   2.411038e+015  400000
0 a2a3   1.822216e+015  400000
0 a2a4   2.576983e+015  400000
0 g1h3   2.131080e+015  400000
0 g1f3   2.699393e+015  400000
0 b1c3   2.728673e+015  400000
0 b1a3   2.098231e+015  400000
Perft 6.283410e+016
------------ 9 --------------
0 h2h3   1.814723e+015  450000
0 h2h4   2.617783e+015  450000
0 g2g3   2.495254e+015  450000
0 g2g4   2.215698e+015  450000
0 f2f3   1.553956e+015  450000
0 f2f4   2.048454e+015  450000
0 e2e3   7.163548e+015  450000
0 e2e4   7.256218e+015  450000
0 d2d3   4.587213e+015  450000
0 d2d4   6.331049e+015  450000
0 c2c3   2.752864e+015  450000
0 c2c4   3.126464e+015  450000
0 b2b3   2.408961e+015  450000
0 b2b4   2.410975e+015  450000
0 a2a3   1.822817e+015  450000
0 a2a4   2.573954e+015  450000
0 g1h3   2.132079e+015  450000
0 g1f3   2.701815e+015  450000
0 b1c3   2.731700e+015  450000
0 b1a3   2.100345e+015  450000
Perft 6.284587e+016
------------ 10 --------------
0 h2h3   1.815171e+015  500000
0 h2h4   2.617650e+015  500000
0 g2g3   2.494990e+015  500000
0 g2g4   2.215388e+015  500000
0 f2f3   1.553766e+015  500000
0 f2f4   2.049380e+015  500000
0 e2e3   7.160351e+015  500000
0 e2e4   7.259996e+015  500000
0 d2d3   4.589976e+015  500000
0 d2d4   6.336715e+015  500000
0 c2c3   2.754723e+015  500000
0 c2c4   3.124217e+015  500000
0 b2b3   2.410776e+015  500000
0 b2b4   2.410020e+015  500000
0 a2a3   1.822980e+015  500000
0 a2a4   2.573983e+015  500000
0 g1h3   2.131692e+015  500000
0 g1f3   2.702720e+015  500000
0 b1c3   2.731418e+015  500000
0 b1a3   2.098746e+015  500000
Perft 6.285466e+016
------------ 11 --------------
0 h2h3   1.813940e+015  550000
0 h2h4   2.617958e+015  550000
0 g2g3   2.496539e+015  550000
0 g2g4   2.215605e+015  550000
0 f2f3   1.553451e+015  550000
0 f2f4   2.051968e+015  550000
0 e2e3   7.159425e+015  550000
0 e2e4   7.259527e+015  550000
0 d2d3   4.590969e+015  550000
0 d2d4   6.330726e+015  550000
0 c2c3   2.758148e+015  550000
0 c2c4   3.123013e+015  550000
0 b2b3   2.410686e+015  550000
0 b2b4   2.411235e+015  550000
0 a2a3   1.822786e+015  550000
0 a2a4   2.575811e+015  550000
0 g1h3   2.130972e+015  550000
0 g1f3   2.704258e+015  550000
0 b1c3   2.732802e+015  550000
0 b1a3   2.098855e+015  550000
Perft 6.285867e+016
------------ 12 --------------
0 h2h3   1.813440e+015  600000
0 h2h4   2.619919e+015  600000
0 g2g3   2.494971e+015  600000
0 g2g4   2.214365e+015  600000
0 f2f3   1.553487e+015  600000
0 f2f4   2.052206e+015  600000
0 e2e3   7.162753e+015  600000
0 e2e4   7.254358e+015  600000
0 d2d3   4.592824e+015  600000
0 d2d4   6.327676e+015  600000
0 c2c3   2.757145e+015  600000
0 c2c4   3.122555e+015  600000
0 b2b3   2.411423e+015  600000
0 b2b4   2.409885e+015  600000
0 a2a3   1.822653e+015  600000
0 a2a4   2.575090e+015  600000
0 g1h3   2.130967e+015  600000
0 g1f3   2.702950e+015  600000
0 b1c3   2.732230e+015  600000
0 b1a3   2.099691e+015  600000
Perft 6.285059e+016
------------ 13 --------------
0 h2h3   1.814229e+015  650000
0 h2h4   2.620978e+015  650000
0 g2g3   2.495462e+015  650000
0 g2g4   2.215475e+015  650000
0 f2f3   1.553379e+015  650000
0 f2f4   2.051682e+015  650000
0 e2e3   7.160288e+015  650000
0 e2e4   7.250356e+015  650000
0 d2d3   4.590598e+015  650000
0 d2d4   6.330433e+015  650000
0 c2c3   2.754787e+015  650000
0 c2c4   3.121723e+015  650000
0 b2b3   2.409998e+015  650000
0 b2b4   2.408850e+015  650000
0 a2a3   1.823009e+015  650000
0 a2a4   2.574284e+015  650000
0 g1h3   2.131403e+015  650000
0 g1f3   2.703566e+015  650000
0 b1c3   2.731481e+015  650000
0 b1a3   2.099698e+015  650000
Perft 6.284168e+016
------------ 14 --------------
0 h2h3   1.815404e+015  700000
0 h2h4   2.621107e+015  700000
0 g2g3   2.497124e+015  700000
0 g2g4   2.215094e+015  700000
0 f2f3   1.552745e+015  700000
0 f2f4   2.051714e+015  700000
0 e2e3   7.157191e+015  700000
0 e2e4   7.256448e+015  700000
0 d2d3   4.589509e+015  700000
0 d2d4   6.329140e+015  700000
0 c2c3   2.754336e+015  700000
0 c2c4   3.121496e+015  700000
0 b2b3   2.408253e+015  700000
0 b2b4   2.409516e+015  700000
0 a2a3   1.823545e+015  700000
0 a2a4   2.574178e+015  700000
0 g1h3   2.132176e+015  700000
0 g1f3   2.703329e+015  700000
0 b1c3   2.734887e+015  700000
0 b1a3   2.101075e+015  700000
Perft 6.284827e+016
------------ 15 --------------
0 h2h3   1.816503e+015  750000
0 h2h4   2.620579e+015  750000
0 g2g3   2.497220e+015  750000
0 g2g4   2.214367e+015  750000
0 f2f3   1.552321e+015  750000
0 f2f4   2.052038e+015  750000
0 e2e3   7.152168e+015  750000
0 e2e4   7.257143e+015  750000
0 d2d3   4.592314e+015  750000
0 d2d4   6.324743e+015  750000
0 c2c3   2.753150e+015  750000
0 c2c4   3.121696e+015  750000
0 b2b3   2.407816e+015  750000
0 b2b4   2.409532e+015  750000
0 a2a3   1.823040e+015  750000
0 a2a4   2.574209e+015  750000
0 g1h3   2.132449e+015  750000
0 g1f3   2.702751e+015  750000
0 b1c3   2.733749e+015  750000
0 b1a3   2.101213e+015  750000
Perft 6.283900e+016
------------ 16 --------------
0 h2h3   1.815944e+015  800000
0 h2h4   2.620315e+015  800000
0 g2g3   2.499890e+015  800000
0 g2g4   2.215288e+015  800000
0 f2f3   1.551713e+015  800000
0 f2f4   2.051139e+015  800000
0 e2e3   7.151355e+015  800000
0 e2e4   7.262185e+015  800000
0 d2d3   4.591226e+015  800000
0 d2d4   6.325666e+015  800000
0 c2c3   2.753631e+015  800000
0 c2c4   3.121308e+015  800000
0 b2b3   2.407670e+015  800000
0 b2b4   2.410392e+015  800000
0 a2a3   1.822743e+015  800000
0 a2a4   2.575083e+015  800000
0 g1h3   2.132846e+015  800000
0 g1f3   2.702652e+015  800000
0 b1c3   2.734292e+015  800000
0 b1a3   2.099795e+015  800000
Perft 6.284513e+016
------------ 17 --------------
0 h2h3   1.815288e+015  850000
0 h2h4   2.619383e+015  850000
0 g2g3   2.500610e+015  850000
0 g2g4   2.213982e+015  850000
0 f2f3   1.552783e+015  850000
0 f2f4   2.051022e+015  850000
0 e2e3   7.150560e+015  850000
0 e2e4   7.260795e+015  850000
0 d2d3   4.588434e+015  850000
0 d2d4   6.326281e+015  850000
0 c2c3   2.754893e+015  850000
0 c2c4   3.122189e+015  850000
0 b2b3   2.408502e+015  850000
0 b2b4   2.409861e+015  850000
0 a2a3   1.823433e+015  850000
0 a2a4   2.575755e+015  850000
0 g1h3   2.133033e+015  850000
0 g1f3   2.703218e+015  850000
0 b1c3   2.735026e+015  850000
0 b1a3   2.102021e+015  850000
Perft 6.284707e+016
------------ 18 --------------
0 h2h3   1.815656e+015  900000
0 h2h4   2.619418e+015  900000
0 g2g3   2.500655e+015  900000
0 g2g4   2.214291e+015  900000
0 f2f3   1.553066e+015  900000
0 f2f4   2.051256e+015  900000
0 e2e3   7.149329e+015  900000
0 e2e4   7.259226e+015  900000
0 d2d3   4.588728e+015  900000
0 d2d4   6.327667e+015  900000
0 c2c3   2.754532e+015  900000
0 c2c4   3.121963e+015  900000
0 b2b3   2.409020e+015  900000
0 b2b4   2.409387e+015  900000
0 a2a3   1.823615e+015  900000
0 a2a4   2.576327e+015  900000
0 g1h3   2.132703e+015  900000
0 g1f3   2.703474e+015  900000
0 b1c3   2.735448e+015  900000
0 b1a3   2.101198e+015  900000
Perft 6.284696e+016
------------ 19 --------------
0 h2h3   1.816246e+015  950000
0 h2h4   2.618368e+015  950000
0 g2g3   2.500863e+015  950000
0 g2g4   2.214835e+015  950000
0 f2f3   1.553202e+015  950000
0 f2f4   2.049946e+015  950000
0 e2e3   7.147544e+015  950000
0 e2e4   7.264825e+015  950000
0 d2d3   4.587508e+015  950000
0 d2d4   6.327325e+015  950000
0 c2c3   2.753856e+015  950000
0 c2c4   3.122839e+015  950000
0 b2b3   2.408637e+015  950000
0 b2b4   2.409409e+015  950000
0 a2a3   1.824127e+015  950000
0 a2a4   2.576294e+015  950000
0 g1h3   2.132834e+015  950000
0 g1f3   2.703278e+015  950000
0 b1c3   2.734808e+015  950000
0 b1a3   2.100417e+015  950000
Perft 6.284716e+016
------------ 20 --------------
0 h2h3   1.816109e+015  1000000
0 h2h4   2.617712e+015  1000000
0 g2g3   2.501489e+015  1000000
0 g2g4   2.216040e+015  1000000
0 f2f3   1.553030e+015  1000000
0 f2f4   2.049958e+015  1000000
0 e2e3   7.151964e+015  1000000
0 e2e4   7.264583e+015  1000000
0 d2d3   4.585124e+015  1000000
0 d2d4   6.324209e+015  1000000
0 c2c3   2.752492e+015  1000000
0 c2c4   3.121799e+015  1000000
0 b2b3   2.408474e+015  1000000
0 b2b4   2.409765e+015  1000000
0 a2a3   1.824919e+015  1000000
0 a2a4   2.575964e+015  1000000
0 g1h3   2.133127e+015  1000000
0 g1f3   2.702962e+015  1000000
0 b1c3   2.736287e+015  1000000
0 b1a3   2.100308e+015  1000000
Perft 6.284632e+016

And using the formula I proposed above. It seems to perform well in the earlier iterations but I am not sure if it is better overall. Infact after 13 million simulations it got 5 significant digist right but may have ended up worse.. (need to investigate it) The number of visits of each node seems to exactly match the node proportions as expected. BTW we don't use weights in the tree part of the search since we just add up all the sub-trees so that should be forgotten.

Code: Select all

0 d2d3   4.595497e+015  657923
0 d2d4   6.316675e+015  904338
0 c2c3   2.750965e+015  393847
0 c2c4   3.117351e+015  446302
0 b2b3   2.408188e+015  344772
0 b2b4   2.405799e+015  344430
0 a2a3   1.830297e+015  262038
0 a2a4   2.578775e+015  369195
0 g1h3   2.137554e+015  306028
0 g1f3   2.705512e+015  387340
0 b1c3   2.732411e+015  391191
0 b1a3   2.097368e+015  300273
Perft 6.286372e+016
------------ 10 --------------
0 h2h3   1.813059e+015  288428
0 h2h4   2.620649e+015  416901
0 g2g3   2.504079e+015  398357
0 g2g4   2.218685e+015  352956
0 f2f3   1.549584e+015  246513
0 f2f4   2.047378e+015  325704
0 e2e3   7.167063e+015  1140160
0 e2e4   7.262421e+015  1155331
0 d2d3   4.592701e+015  730622
0 d2d4   6.317081e+015  1004942
0 c2c3   2.752083e+015  437810
0 c2c4   3.117873e+015  496001
0 b2b3   2.409631e+015  383333
0 b2b4   2.405647e+015  382698
0 a2a3   1.832156e+015  291465
0 a2a4   2.579491e+015  410354
0 g1h3   2.137038e+015  339968
0 g1f3   2.705199e+015  430352
0 b1c3   2.727891e+015  433962
0 b1a3   2.100427e+015  334143
Perft 6.286013e+016
------------ 11 --------------
0 h2h3   1.813997e+015  317488
0 h2h4   2.621098e+015  458748
0 g2g3   2.503788e+015  438217
0 g2g4   2.219913e+015  388532
0 f2f3   1.549072e+015  271121
0 f2f4   2.047491e+015  358354
0 e2e3   7.167173e+015  1254408
0 e2e4   7.258842e+015  1270453
0 d2d3   4.593822e+015  804017
0 d2d4   6.317270e+015  1105657
0 c2c3   2.751479e+015  481567
0 c2c4   3.117819e+015  545686
0 b2b3   2.408365e+015  421516
0 b2b4   2.406613e+015  421208
0 a2a3   1.828823e+015  320083
0 a2a4   2.577085e+015  451045
0 g1h3   2.135356e+015  373734
0 g1f3   2.703714e+015  473207
0 b1c3   2.727331e+015  477341
0 b1a3   2.100421e+015  367618
Perft 6.284947e+016
------------ 12 --------------
0 h2h3   1.812292e+015  346021
0 h2h4   2.622347e+015  500685
0 g2g3   2.502575e+015  477817
0 g2g4   2.219905e+015  423847
0 f2f3   1.549419e+015  295830
0 f2f4   2.046605e+015  390759
0 e2e3   7.168725e+015  1368726
0 e2e4   7.258829e+015  1385929
0 d2d3   4.592223e+015  876793
0 d2d4   6.318268e+015  1206347
0 c2c3   2.751836e+015  525408
0 c2c4   3.117031e+015  595135
0 b2b3   2.409042e+015  459959
0 b2b4   2.405685e+015  459318
0 a2a3   1.828049e+015  349029
0 a2a4   2.576190e+015  491872
0 g1h3   2.136554e+015  407933
0 g1f3   2.705915e+015  516640
0 b1c3   2.726956e+015  520658
0 b1a3   2.101784e+015  401294
Perft 6.285023e+016
------------ 13 --------------
0 h2h3   1.811803e+015  374729
0 h2h4   2.618846e+015  541646
0 g2g3   2.504188e+015  517930
0 g2g4   2.220471e+015  459252
0 f2f3   1.548924e+015  320359
0 f2f4   2.046215e+015  423211
0 e2e3   7.169890e+015  1482923
0 e2e4   7.261306e+015  1501830
0 d2d3   4.594948e+015  950356
0 d2d4   6.316519e+015  1306423
0 c2c3   2.752095e+015  569206
0 c2c4   3.118487e+015  644985
0 b2b3   2.409069e+015  498259
0 b2b4   2.405068e+015  497432
0 a2a3   1.828397e+015  378161
0 a2a4   2.574745e+015  532525
0 g1h3   2.136591e+015  441903
0 g1f3   2.704993e+015  559465
0 b1c3   2.728415e+015  564308
0 b1a3   2.103684e+015  435097
Perft 6.285465e+016
------------ 14 --------------
0 h2h3   1.813291e+015  403891
0 h2h4   2.620117e+015  583601
0 g2g3   2.502080e+015  557310
0 g2g4   2.220889e+015  494678
0 f2f3   1.548103e+015  344823
0 f2f4   2.045591e+015  455633
0 e2e3   7.171794e+015  1597435
0 e2e4   7.263690e+015  1617904
0 d2d3   4.592061e+015  1022829
0 d2d4   6.318092e+015  1407278
0 c2c3   2.751921e+015  612959
0 c2c4   3.116581e+015  694183
0 b2b3   2.409730e+015  536740
0 b2b4   2.403458e+015  535343
0 a2a3   1.827671e+015  407094
0 a2a4   2.575980e+015  573770
0 g1h3   2.137585e+015  476123
0 g1f3   2.705148e+015  602542
0 b1c3   2.727396e+015  607496
0 b1a3   2.102771e+015  468368
Perft 6.285395e+016
------------ 15 --------------
0 h2h3   1.813036e+015  432652
0 h2h4   2.622403e+015  625795
0 g2g3   2.503675e+015  597463
0 g2g4   2.220766e+015  529950
0 f2f3   1.550062e+015  369898
0 f2f4   2.045958e+015  488236
0 e2e3   7.170076e+015  1711025
0 e2e4   7.261934e+015  1732945
0 d2d3   4.593117e+015  1096074
0 d2d4   6.317087e+015  1507471
0 c2c3   2.751558e+015  656616
0 c2c4   3.117043e+015  743832
0 b2b3   2.410570e+015  575244
0 b2b4   2.402488e+015  573316
0 a2a3   1.828604e+015  436367
0 a2a4   2.574928e+015  614466
0 g1h3   2.137888e+015  510173
0 g1f3   2.705798e+015  645696
0 b1c3   2.728363e+015  651080
0 b1a3   2.102386e+015  501701
Perft 6.285774e+016
------------ 16 --------------
0 h2h3   1.814018e+015  461744
0 h2h4   2.623417e+015  667770
0 g2g3   2.503974e+015  637367
0 g2g4   2.221177e+015  565383
0 f2f3   1.551175e+015  394840
0 f2f4   2.046955e+015  521037
0 e2e3   7.167191e+015  1824351
0 e2e4   7.264443e+015  1849106
0 d2d3   4.593504e+015  1169240
0 d2d4   6.316697e+015  1607865
0 c2c3   2.750663e+015  700160
0 c2c4   3.116618e+015  793310
0 b2b3   2.411340e+015  613787
0 b2b4   2.402587e+015  611559
0 a2a3   1.828773e+015  465500
0 a2a4   2.573638e+015  655099
0 g1h3   2.137460e+015  544074
0 g1f3   2.706000e+015  688791
0 b1c3   2.726595e+015  694033
0 b1a3   2.101748e+015  534984
Perft 6.285798e+016
------------ 17 --------------
0 h2h3   1.813638e+015  490492
0 h2h4   2.624576e+015  709807
0 g2g3   2.503000e+015  676927
0 g2g4   2.221308e+015  600744
0 f2f3   1.552404e+015  419842
0 f2f4   2.046949e+015  553589
0 e2e3   7.167069e+015  1938306
0 e2e4   7.264421e+015  1964635
0 d2d3   4.593359e+015  1242256
0 d2d4   6.319374e+015  1709050
0 c2c3   2.749583e+015  743615
0 c2c4   3.115050e+015  842454
0 b2b3   2.411415e+015  652158
0 b2b4   2.404495e+015  650286
0 a2a3   1.826844e+015  494064
0 a2a4   2.572587e+015  695747
0 g1h3   2.137674e+015  578126
0 g1f3   2.705651e+015  731733
0 b1c3   2.727820e+015  737728
0 b1a3   2.101865e+015  568441
Perft 6.285908e+016
------------ 18 --------------
0 h2h3   1.815725e+015  519894
0 h2h4   2.625884e+015  751866
0 g2g3   2.502382e+015  716504
0 g2g4   2.221896e+015  636192
0 f2f3   1.553130e+015  444706
0 f2f4   2.048007e+015  586402
0 e2e3   7.168234e+015  2052470
0 e2e4   7.264676e+015  2080084
0 d2d3   4.593371e+015  1315213
0 d2d4   6.319948e+015  1809581
0 c2c3   2.748922e+015  787095
0 c2c4   3.115832e+015  892151
0 b2b3   2.412455e+015  690755
0 b2b4   2.404762e+015  688552
0 a2a3   1.826525e+015  522986
0 a2a4   2.572899e+015  736694
0 g1h3   2.136722e+015  611804
0 g1f3   2.705012e+015  774522
0 b1c3   2.726329e+015  780625
0 b1a3   2.102156e+015  601904
Perft 6.286487e+016
------------ 19 --------------
0 h2h3   1.815107e+015  548552
0 h2h4   2.625603e+015  793495
0 g2g3   2.501708e+015  756052
0 g2g4   2.222109e+015  671553
0 f2f3   1.553298e+015  469429
0 f2f4   2.049418e+015  619364
0 e2e3   7.167926e+015  2166250
0 e2e4   7.266628e+015  2196080
0 d2d3   4.593653e+015  1388268
0 d2d4   6.320792e+015  1910234
0 c2c3   2.748679e+015  830690
0 c2c4   3.115870e+015  941661
0 b2b3   2.412186e+015  728997
0 b2b4   2.405768e+015  727058
0 a2a3   1.826682e+015  552050
0 a2a4   2.572771e+015  777528
0 g1h3   2.136955e+015  645818
0 g1f3   2.705180e+015  817545
0 b1c3   2.726352e+015  823943
0 b1a3   2.102589e+015  635433
Perft 6.286927e+016
------------ 20 --------------
0 h2h3   1.815710e+015  577626
0 h2h4   2.625207e+015  835150
0 g2g3   2.502826e+015  796217
0 g2g4   2.221826e+015  706823
0 f2f3   1.553493e+015  494208
0 f2f4   2.048690e+015  651743
0 e2e3   7.167533e+015  2280186
0 e2e4   7.267550e+015  2312004
0 d2d3   4.593755e+015  1461397
0 d2d4   6.320145e+015  2010608
0 c2c3   2.748152e+015  874261
0 c2c4   3.115947e+015  991267
0 b2b3   2.410237e+015  766761
0 b2b4   2.406517e+015  765579
0 a2a3   1.826718e+015  581128
0 a2a4   2.573466e+015  818684
0 g1h3   2.136368e+015  679636
0 g1f3   2.704945e+015  860516
0 b1c3   2.726488e+015  867369
0 b1a3   2.102422e+015  668837
Perft 6.286800e+016

And the visit allocation at iteration 20 are exact as the last two columns show.

Code: Select all

				                   % node	% visit
0	h2h3	1.82E+15	577626		
0	h2h4	2.63E+15	835150	4.1757	4.1758
0	g2g3	2.50E+15	796217	3.9811	3.9811
0	g2g4	2.22E+15	706823	3.5341	3.5341
0	f2f3	1.55E+15	494208	2.4710	2.4710
0	f2f4	2.05E+15	651743	3.2587	3.2587
0	e2e3	7.17E+15	2280186	11.4009	11.4009
0	e2e4	7.27E+15	2312004	11.5600	11.5600
0	d2d3	4.59E+15	1461397	7.3070	7.3070
0	d2d4	6.32E+15	2010608	10.0530	10.0530
0	c2c3	2.75E+15	874261	4.3713	4.3713
0	c2c4	3.12E+15	991267	4.9563	4.9563
0	b2b3	2.41E+15	766761	3.8338	3.8338
0	b2b4	2.41E+15	765579	3.8279	3.8279
0	a2a3	1.83E+15	581128	2.9056	2.9056
0	a2a4	2.57E+15	818684	4.0934	4.0934
0	g1h3	2.14E+15	679636	3.3982	3.3982
0	g1f3	2.70E+15	860516	4.3026	4.3026
0	b1c3	2.73E+15	867369	4.3368	4.3368
0	b1a3	2.10E+15	668837	3.3442	3.3442
					
	Total	6.29E+16	20000000	97.1119	97.1119

Daniel

[Michel]

Daniel,

I haven't read your posts in detail yet (I am traveling today) but it is true that I have no heuristic to balance exploitation versus exploration. I have to
look into the UCT approach for this.

In my (proposed) method exploitation amounts to using the weights in the known subtree (and making them closer to optimal along the way).
Exploration amounts to splitting leaf nodes (selected by their estimated
defect). This is an "investment".

Your comment that splitting a leaf node in my method seems to lose information from prior visits is true. I have to look into that as well.

But before I do anything more I have to make an implementation.