Perft(13) betting pool

[Daniel Shawul]

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.

Sorry I didn't intend the second comment for your method only. The investement is for any splitting method including UCT as well. If my measurement is correct I lose about 20% for that. I have tried to combine them together but the result could be bad depending on the parameters I choose. If you still want to proportion the probabilities with node ratio , the second formula gives exactly what you need. However I am now beginning to think taking log for the nodes count may be more appropriate so trying the following instead.

Code: Select all

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

The idea is the tree size follows log-normal so taking log gives variances on summation of branching factors may be better. That is what I did when trying methods which try to estimate perft from BF estimate. First there are variances for each BF which increase from ply 0 to ply N, then I _added_ those variances to get the total variance. I am getting better result with this method after 85 iterations so far. Will post when it finishes..

Results after 100 million simulations for proportional to sub-tree size method. The uniform allocation gave slightly better result. It could be luck though.

Code: Select all

------------ 95 --------------
0 h2h3   1.814544e+015  2742303
0 h2h4   2.623413e+015  3964739
0 g2g3   2.500224e+015  3778565
0 g2g4   2.218248e+015  3352416
0 f2f3   1.552093e+015  2345663
0 f2f4   2.049980e+015  3098115
0 e2e3   7.164956e+015  10828328
0 e2e4   7.266781e+015  10982216
0 d2d3   4.588489e+015  6934539
0 d2d4   6.327995e+015  9563438
0 c2c3   2.750477e+015  4156769
0 c2c4   3.120184e+015  4715503
0 b2b3   2.405572e+015  3635517
0 b2b4   2.410683e+015  3643243
0 a2a3   1.822594e+015  2754468
0 a2a4   2.574147e+015  3890281
0 g1h3   2.132425e+015  3222713
0 g1f3   2.704350e+015  4087058
0 b1c3   2.731134e+015  4127537
0 b1a3   2.101906e+015  3176589
Perft 6.286019e+016
------------ 96 --------------
0 h2h3   1.814641e+015  2771285
0 h2h4   2.623305e+015  4006262
0 g2g3   2.500356e+015  3818497
0 g2g4   2.218137e+015  3387497
0 f2f3   1.552185e+015  2370469
0 f2f4   2.049706e+015  3130274
0 e2e3   7.164679e+015  10941765
0 e2e4   7.266678e+015  11097535
0 d2d3   4.588700e+015  7007777
0 d2d4   6.328278e+015  9664428
0 c2c3   2.750535e+015  4200566
0 c2c4   3.120124e+015  4764996
0 b2b3   2.405740e+015  3674002
0 b2b4   2.411026e+015  3682074
0 a2a3   1.822916e+015  2783924
0 a2a4   2.574031e+015  3931013
0 g1h3   2.132262e+015  3256351
0 g1f3   2.704242e+015  4129868
0 b1c3   2.731432e+015  4171391
0 b1a3   2.101929e+015  3210026
Perft 6.286090e+016
------------ 97 --------------
0 h2h3   1.814775e+015  2800387
0 h2h4   2.623186e+015  4047849
0 g2g3   2.500486e+015  3858511
0 g2g4   2.218157e+015  3422847
0 f2f3   1.552283e+015  2395335
0 f2f4   2.049790e+015  3163040
0 e2e3   7.164874e+015  11056147
0 e2e4   7.265970e+015  11212149
0 d2d3   4.588950e+015  7081227
0 d2d4   6.328184e+015  9765048
0 c2c3   2.750588e+015  4244444
0 c2c4   3.119923e+015  4814365
0 b2b3   2.405638e+015  3712150
0 b2b4   2.411057e+015  3720512
0 a2a3   1.823046e+015  2813145
0 a2a4   2.573643e+015  3971400
0 g1h3   2.132143e+015  3290119
0 g1f3   2.704147e+015  4172780
0 b1c3   2.731232e+015  4214575
0 b1a3   2.102237e+015  3243970
Perft 6.286031e+016
------------ 98 --------------
0 h2h3   1.814641e+015  2829047
0 h2h4   2.623313e+015  4089774
0 g2g3   2.500198e+015  3897838
0 g2g4   2.218002e+015  3457890
0 f2f3   1.552312e+015  2420072
0 f2f4   2.049749e+015  3195582
0 e2e3   7.165067e+015  11170420
0 e2e4   7.265782e+015  11327436
0 d2d3   4.588915e+015  7154171
0 d2d4   6.328136e+015  9865636
0 c2c3   2.750818e+015  4288556
0 c2c4   3.119750e+015  4863725
0 b2b3   2.405729e+015  3750558
0 b2b4   2.411040e+015  3758838
0 a2a3   1.823123e+015  2842270
0 a2a4   2.573906e+015  4012749
0 g1h3   2.132277e+015  3324244
0 g1f3   2.703970e+015  4215520
0 b1c3   2.731516e+015  4258465
0 b1a3   2.102107e+015  3277209
Perft 6.286035e+016
------------ 99 --------------
0 h2h3   1.814709e+015  2857992
0 h2h4   2.623696e+015  4132067
0 g2g3   2.500324e+015  3937768
0 g2g4   2.217998e+015  3493133
0 f2f3   1.552293e+015  2444711
0 f2f4   2.049898e+015  3228389
0 e2e3   7.164992e+015  11284171
0 e2e4   7.265571e+015  11442573
0 d2d3   4.588836e+015  7226972
0 d2d4   6.328361e+015  9966557
0 c2c3   2.750690e+015  4332071
0 c2c4   3.119796e+015  4913378
0 b2b3   2.405688e+015  3788726
0 b2b4   2.411155e+015  3797336
0 a2a3   1.823169e+015  2871316
0 a2a4   2.573770e+015  4053439
0 g1h3   2.132211e+015  3358027
0 g1f3   2.704066e+015  4258643
0 b1c3   2.731712e+015  4302183
0 b1a3   2.102065e+015  3310548
Perft 6.286100e+016
------------ 100 --------------
0 h2h3   1.814621e+015  2886734
0 h2h4   2.623826e+015  4174033
0 g2g3   2.500359e+015  3977618
0 g2g4   2.218248e+015  3528831
0 f2f3   1.552389e+015  2469571
0 f2f4   2.050037e+015  3261238
0 e2e3   7.164477e+015  11397385
0 e2e4   7.265748e+015  11558490
0 d2d3   4.589123e+015  7300463
0 d2d4   6.327834e+015  10066437
0 c2c3   2.750899e+015  4376182
0 c2c4   3.119530e+015  4962607
0 b2b3   2.405574e+015  3826832
0 b2b4   2.411089e+015  3835606
0 a2a3   1.823271e+015  2900494
0 a2a4   2.573868e+015  4094558
0 g1h3   2.132194e+015  3391934
0 g1f3   2.703864e+015  4301358
0 b1c3   2.731651e+015  4345563
0 b1a3   2.102104e+015  3344066
Perft 6.286071e+016

And for uniform method

Code: Select all

------------ 97 --------------
0 h2h3   1.815042e+015  4850000
0 h2h4   2.619363e+015  4850000
0 g2g3   2.498237e+015  4850000
0 g2g4   2.217988e+015  4850000
0 f2f3   1.552261e+015  4850000
0 f2f4   2.049596e+015  4850000
0 e2e3   7.162292e+015  4850000
0 e2e4   7.260897e+015  4850000
0 d2d3   4.588911e+015  4850000
0 d2d4   6.326541e+015  4850000
0 c2c3   2.755182e+015  4850000
0 c2c4   3.118986e+015  4850000
0 b2b3   2.407414e+015  4850000
0 b2b4   2.410232e+015  4850000
0 a2a3   1.825729e+015  4850000
0 a2a4   2.573096e+015  4850000
0 g1h3   2.132801e+015  4850000
0 g1f3   2.704456e+015  4850000
0 b1c3   2.730751e+015  4850000
0 b1a3   2.101375e+015  4850000
Perft 6.285115e+016
------------ 98 --------------
0 h2h3   1.815066e+015  4900000
0 h2h4   2.619217e+015  4900000
0 g2g3   2.498270e+015  4900000
0 g2g4   2.217694e+015  4900000
0 f2f3   1.552233e+015  4900000
0 f2f4   2.049623e+015  4900000
0 e2e3   7.162082e+015  4900000
0 e2e4   7.260816e+015  4900000
0 d2d3   4.588863e+015  4900000
0 d2d4   6.326479e+015  4900000
0 c2c3   2.754960e+015  4900000
0 c2c4   3.118811e+015  4900000
0 b2b3   2.407694e+015  4900000
0 b2b4   2.410463e+015  4900000
0 a2a3   1.826067e+015  4900000
0 a2a4   2.573269e+015  4900000
0 g1h3   2.132763e+015  4900000
0 g1f3   2.704381e+015  4900000
0 b1c3   2.730846e+015  4900000
0 b1a3   2.101331e+015  4900000
Perft 6.285093e+016
------------ 99 --------------
0 h2h3   1.815129e+015  4950000
0 h2h4   2.619106e+015  4950000
0 g2g3   2.498202e+015  4950000
0 g2g4   2.217786e+015  4950000
0 f2f3   1.552289e+015  4950000
0 f2f4   2.049872e+015  4950000
0 e2e3   7.162139e+015  4950000
0 e2e4   7.261046e+015  4950000
0 d2d3   4.589082e+015  4950000
0 d2d4   6.326175e+015  4950000
0 c2c3   2.755080e+015  4950000
0 c2c4   3.118961e+015  4950000
0 b2b3   2.407684e+015  4950000
0 b2b4   2.410508e+015  4950000
0 a2a3   1.825881e+015  4950000
0 a2a4   2.573285e+015  4950000
0 g1h3   2.132817e+015  4950000
0 g1f3   2.704492e+015  4950000
0 b1c3   2.730788e+015  4950000
0 b1a3   2.101291e+015  4950000
Perft 6.285162e+016
------------ 100 --------------
0 h2h3   1.815128e+015  5000000
0 h2h4   2.619224e+015  5000000
0 g2g3   2.498031e+015  5000000
0 g2g4   2.217873e+015  5000000
0 f2f3   1.552279e+015  5000000
0 f2f4   2.049860e+015  5000000
0 e2e3   7.161920e+015  5000000
0 e2e4   7.260682e+015  5000000
0 d2d3   4.589122e+015  5000000
0 d2d4   6.326493e+015  5000000
0 c2c3   2.755015e+015  5000000
0 c2c4   3.118646e+015  5000000
0 b2b3   2.407840e+015  5000000
0 b2b4   2.410368e+015  5000000
0 a2a3   1.825764e+015  5000000
0 a2a4   2.573327e+015  5000000
0 g1h3   2.133095e+015  5000000
0 g1f3   2.704518e+015  5000000
0 b1c3   2.730783e+015  5000000
0 b1a3   2.101400e+015  5000000
Perft 6.285137e+016

BTW in my previous post I skipped the first raw by mistake when calculating the node and visit ratio. Including that will give 100% instead of 99.7..

Edit:
Here is the result using proportioning by log instead of nodes ratio directly. It gave the least error compared to the exact value 6.2855e16. About 0.0002e16 error only!!

Code: Select all

------------ 95 --------------
0 h2h3   1.813367e+015  3668997
0 h2h4   2.622462e+015  4575112
0 g2g3   2.498003e+015  4455693
0 g2g4   2.218725e+015  4164504
0 f2f3   1.553246e+015  3288703
0 f2f4   2.051241e+015  3971733
0 e2e3   7.157253e+015  7041040
0 e2e4   7.260297e+015  7076148
0 d2d3   4.593762e+015  5951951
0 d2d4   6.330223e+015  6739457
0 c2c3   2.753395e+015  4694775
0 c2c4   3.120384e+015  5002082
0 b2b3   2.405178e+015  4362688
0 b2b4   2.410145e+015  4367754
0 a2a3   1.825742e+015  3685702
0 a2a4   2.572863e+015  4528215
0 g1h3   2.135132e+015  4070181
0 g1f3   2.705164e+015  4651371
0 b1c3   2.730754e+015  4674495
0 b1a3   2.099974e+015  4029399
Perft 6.285731e+016
------------ 96 --------------
0 h2h3   1.813458e+015  3707714
0 h2h4   2.622427e+015  4623209
0 g2g3   2.497879e+015  4502443
0 g2g4   2.218712e+015  4208298
0 f2f3   1.553496e+015  3323692
0 f2f4   2.051224e+015  4013491
0 e2e3   7.157017e+015  7115044
0 e2e4   7.260720e+015  7150748
0 d2d3   4.593719e+015  6014550
0 d2d4   6.330296e+015  6810397
0 c2c3   2.753466e+015  4744228
0 c2c4   3.120460e+015  5054766
0 b2b3   2.405024e+015  4408422
0 b2b4   2.410320e+015  4413882
0 a2a3   1.825850e+015  3724617
0 a2a4   2.572632e+015  4575628
0 g1h3   2.135044e+015  4112893
0 g1f3   2.705109e+015  4700252
0 b1c3   2.731131e+015  4724014
0 b1a3   2.099911e+015  4071712
Perft 6.285789e+016
------------ 97 --------------
0 h2h3   1.813474e+015  3746335
0 h2h4   2.622278e+015  4671201
0 g2g3   2.497869e+015  4549309
0 g2g4   2.218955e+015  4252384
0 f2f3   1.553503e+015  3358301
0 f2f4   2.051466e+015  4055569
0 e2e3   7.157632e+015  7189350
0 e2e4   7.260818e+015  7225245
0 d2d3   4.593745e+015  6077192
0 d2d4   6.330225e+015  6881286
0 c2c3   2.753416e+015  4793578
0 c2c4   3.120356e+015  5107313
0 b2b3   2.405015e+015  4454310
0 b2b4   2.410286e+015  4459800
0 a2a3   1.826017e+015  3763621
0 a2a4   2.572583e+015  4623219
0 g1h3   2.134935e+015  4155583
0 g1f3   2.705092e+015  4749173
0 b1c3   2.731008e+015  4773086
0 b1a3   2.099948e+015  4114145
Perft 6.285862e+016
------------ 98 --------------
0 h2h3   1.813519e+015  3785078
0 h2h4   2.622158e+015  4719300
0 g2g3   2.497882e+015  4596281
0 g2g4   2.218687e+015  4295975
0 f2f3   1.553645e+015  3393213
0 f2f4   2.051482e+015  4097457
0 e2e3   7.157869e+015  7263610
0 e2e4   7.260380e+015  7299638
0 d2d3   4.593652e+015  6139851
0 d2d4   6.330458e+015  6952380
0 c2c3   2.753096e+015  4842760
0 c2c4   3.120317e+015  5159991
0 b2b3   2.404553e+015  4499801
0 b2b4   2.410345e+015  4505897
0 a2a3   1.825961e+015  3802401
0 a2a4   2.572427e+015  4670786
0 g1h3   2.134814e+015  4198339
0 g1f3   2.705140e+015  4798237
0 b1c3   2.731136e+015  4822469
0 b1a3   2.099880e+015  4156536
Perft 6.285740e+016
------------ 99 --------------
0 h2h3   1.813451e+015  3823628
0 h2h4   2.622242e+015  4767561
0 g2g3   2.497800e+015  4643120
0 g2g4   2.218648e+015  4339790
0 f2f3   1.553630e+015  3427835
0 f2f4   2.051477e+015  4139284
0 e2e3   7.157845e+015  7337744
0 e2e4   7.260224e+015  7374093
0 d2d3   4.593317e+015  6202339
0 d2d4   6.330261e+015  7023267
0 c2c3   2.753179e+015  4892276
0 c2c4   3.120273e+015  5212632
0 b2b3   2.404770e+015  4545972
0 b2b4   2.410248e+015  4551797
0 a2a3   1.825954e+015  3841213
0 a2a4   2.572256e+015  4718300
0 g1h3   2.134895e+015  4241300
0 g1f3   2.705073e+015  4847159
0 b1c3   2.731118e+015  4871684
0 b1a3   2.099908e+015  4199006
Perft 6.285657e+016
------------ 100 --------------
0 h2h3   1.813502e+015  3862301
0 h2h4   2.622191e+015  4815647
0 g2g3   2.497554e+015  4689745
0 g2g4   2.218660e+015  4383619
0 f2f3   1.553711e+015  3462573
0 f2f4   2.051314e+015  4180870
0 e2e3   7.157988e+015  7411893
0 e2e4   7.260711e+015  7448731
0 d2d3   4.593310e+015  6264964
0 d2d4   6.330106e+015  7094123
0 c2c3   2.753393e+015  4941872
0 c2c4   3.120550e+015  5265493
0 b2b3   2.404953e+015  4592066
0 b2b4   2.410162e+015  4597661
0 a2a3   1.825955e+015  3879994
0 a2a4   2.572282e+015  4765965
0 g1h3   2.134757e+015  4283953
0 g1f3   2.705026e+015  4896054
0 b1c3   2.731204e+015  4920954
0 b1a3   2.100007e+015  4241522
Perft 6.285734e+016
Time : 4076766ms Tree : nodes 21 depth 0/0 pps 24529 visits 100000000
0 h2h3   1.813502e+015  3862301
0 h2h4   2.622191e+015  4815647
0 g2g3   2.497554e+015  4689745
0 g2g4   2.218660e+015  4383619
0 f2f3   1.553711e+015  3462573
0 f2f4   2.051314e+015  4180870
0 e2e3   7.157988e+015  7411893
0 e2e4   7.260711e+015  7448731
0 d2d3   4.593310e+015  6264964
0 d2d4   6.330106e+015  7094123
0 c2c3   2.753393e+015  4941872
0 c2c4   3.120550e+015  5265493
0 b2b3   2.404953e+015  4592066
0 b2b4   2.410162e+015  4597661
0 a2a3   1.825955e+015  3879994
0 a2a4   2.572282e+015  4765965
0 g1h3   2.134757e+015  4283953
0 g1f3   2.705026e+015  4896054
0 b1c3   2.731204e+015  4920954
0 b1a3   2.100007e+015  4241522
Perft 6.285734e+016
move e2e4

[Michel]

The reason I do not want to use UCB or UCT without proper justification
first is that these algorithms were designed for somewhat different problems.

In the multi armed bandit problem you ultimately want to find
the best arm to pull. This is a maximization problem with incomplete
information. The performance metric used is the "regret".

In perft you want to compute a sum with incomplete information.
I think here the performance metric is (cpu time)*variance.

[Daniel Shawul]

The reason I do not want to use UCB or UCT without proper justification
first is that these algorithms were designed for somewhat different problems.

In the multi armed bandit problem you ultimately want to find
the best arm to pull. This is a maximization problem with incomplete
information. The performance metric used is the "regret".

In perft you want to compute a sum with incomplete information.
I think here the performance metric is (cpu time)*variance.

I think it is similiar. Here also you want to pick the best node which will lead to the highest reduction of variance. And if it didn't there is regret. So quite similar. Anyway my point was even after eliminating UCB completely, and using a formula that we thought would reduce variance greatly i.e

Code: Select all

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

I didn't get favourable result. It is even worse than uniform sampling. Why? That is the best dynamic allocation so far isn't it? It exactly allocates visits to each node proportional to their size at each iteration and yet is worse than uniform sampling. Maybe variance is not proportional to sub-tree size after all?
UCB allocates visits exponentially more to the best selected node. That is the only difference with the other formulas I provided.

Code: Select all

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

And proportioning by the ratio of log of nodes

Code: Select all

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

This last one gave the best result for a non-splitting type of simulation.
But splitting adds more complexity infact I get the best result with the UCB formula with splitting. But I do not want to discuss that before we understand how the nodes should be proportioned given _exact_ sub-tree size for each move. I can even take the exact values from the perft(12) computation and construct proportions but I think they will exactly match with the first method I have which adjusts the probabilities to match the current sub-tree ratio estimates.

[Daniel Shawul]

And formula for uniform sampling

Code: Select all

X = (1 / no_of_moves) - (child_visits / parent_visits) 

You can see the UCB formula is very similar to the rest except that it adds an inverse of the second term instead of subtraction as the rest do. But the effect is the same.

Edit:
I see that all the methods I came up with have in fact a formal name "probability matching variants" which is used for solving MAB problems.
These are methods which choose levers (moves) according to a certain probability distribution. The uniform sampling is I think the simplest of these methods. Now I have no doubt that it is indeed an MAB problem with the reward being a reduction in variance. Since that was difficult to quantify I was using sub-tree size ratio to estimate possible rewards.

Here is another one SoftMax (Boltzman) exploration

Code: Select all

X = exp(mean_reward / T) / Sum( exp(mean_reward_i/ T)  - (child_visits / parent_visits) 

Another variant "decreasing SoftMax" decreases the temperature T based on the number of rounds.

More complicated variant known as "Exp3", exponential weight algorithm for exploration and exploitation, and other methods can be found here
http://www.cs.nyu.edu/~mohri/pub/bandit.pdf

[Daniel Shawul]

Uniform selection now with _tree splitting_ seems to be good too. Even better than UCT did. Here is the result after 14 million iterations.
As you can see the amount of wasted nodes can reach as high as 40% when a lot of splitting is done at a given iteration.
Edit: Despite promising results it ended up worse than its non-splitting counterpart with about 20% wasted simulations and expansion upto depth 4. All moves are probably expanded by the same amount.

Code: Select all

------------ 11 --------------
0 h2h3   1.814161e+015  317125
0 h2h4   2.616635e+015  317125
0 g2g3   2.497981e+015  317125
0 g2g4   2.213894e+015  317125
0 f2f3   1.551397e+015  317125
0 f2f4   2.054735e+015  317125
0 e2e3   7.174062e+015  317125
0 e2e4   7.263277e+015  317125
0 d2d3   4.590243e+015  317125
0 d2d4   6.324962e+015  317125
0 c2c3   2.756622e+015  317125
0 c2c4   3.118361e+015  317125
0 b2b3   2.407923e+015  317125
0 b2b4   2.409838e+015  317125
0 a2a3   1.827371e+015  317125
0 a2a4   2.578327e+015  317125
0 g1h3   2.128971e+015  317125
0 g1f3   2.700820e+015  317125
0 b1c3   2.731797e+015  317125
0 b1a3   2.099390e+015  317125
Perft 6.286077e+016
wasted 42.34
------------ 12 --------------
0 h2h3   1.814593e+015  366850
0 h2h4   2.614437e+015  366850
0 g2g3   2.497798e+015  366850
0 g2g4   2.215917e+015  366850
0 f2f3   1.551554e+015  366850
0 f2f4   2.054248e+015  366850
0 e2e3   7.177416e+015  366850
0 e2e4   7.264327e+015  366850
0 d2d3   4.590352e+015  366850
0 d2d4   6.320704e+015  366850
0 c2c3   2.755335e+015  366850
0 c2c4   3.118752e+015  366850
0 b2b3   2.408646e+015  366850
0 b2b4   2.410199e+015  366850
0 a2a3   1.828762e+015  366850
0 a2a4   2.576053e+015  366850
0 g1h3   2.129391e+015  366850
0 g1f3   2.701997e+015  366850
0 b1c3   2.732547e+015  366850
0 b1a3   2.099980e+015  366850
Perft 6.286301e+016
wasted 38.86
------------ 13 --------------
0 h2h3   1.814466e+015  416850
0 h2h4   2.612656e+015  416850
0 g2g3   2.497059e+015  416850
0 g2g4   2.216632e+015  416850
0 f2f3   1.551576e+015  416850
0 f2f4   2.053057e+015  416850
0 e2e3   7.170104e+015  416850
0 e2e4   7.269656e+015  416850
0 d2d3   4.590835e+015  416850
0 d2d4   6.321749e+015  416850
0 c2c3   2.752496e+015  416850
0 c2c4   3.119130e+015  416850
0 b2b3   2.408283e+015  416850
0 b2b4   2.410580e+015  416850
0 a2a3   1.827787e+015  416850
0 a2a4   2.575525e+015  416850
0 g1h3   2.128183e+015  416850
0 g1f3   2.704700e+015  416850
0 b1c3   2.731502e+015  416850
0 b1a3   2.099395e+015  416850
Perft 6.285537e+016
wasted 35.87 

------------ 98 --------------
0 h2h3   1.813782e+015  4038569
0 h2h4   2.620226e+015  4038569
0 g2g3   2.498180e+015  4038569
0 g2g4   2.217808e+015  4038569
0 f2f3   1.553984e+015  4038584
0 f2f4   2.051250e+015  4038569
0 e2e3   7.161325e+015  4038569
0 e2e4   7.259519e+015  4038569
0 d2d3   4.588241e+015  4038569
0 d2d4   6.325171e+015  4038569
0 c2c3   2.751366e+015  4038569
0 c2c4   3.120634e+015  4038569
0 b2b3   2.407401e+015  4038574
0 b2b4   2.412297e+015  4038571
0 a2a3   1.824810e+015  4038568
0 a2a4   2.574570e+015  4038568
0 g1h3   2.133448e+015  4038584
0 g1f3   2.704693e+015  4038568
0 b1c3   2.730602e+015  4038568
0 b1a3   2.100698e+015  4038568
Perft 6.285000e+016
wasted 17.58
------------ 99 --------------
0 h2h3   1.813770e+015  4051340
0 h2h4   2.620199e+015  4051340
0 g2g3   2.498106e+015  4051340
0 g2g4   2.217771e+015  4051350
0 f2f3   1.553832e+015  4051351
0 f2f4   2.051273e+015  4051340
0 e2e3   7.161171e+015  4051340
0 e2e4   7.259488e+015  4051340
0 d2d3   4.588558e+015  4051340
0 d2d4   6.325276e+015  4051340
0 c2c3   2.751539e+015  4051340
0 c2c4   3.120750e+015  4051340
0 b2b3   2.407378e+015  4051340
0 b2b4   2.412312e+015  4051340
0 a2a3   1.824811e+015  4051352
0 a2a4   2.574500e+015  4051339
0 g1h3   2.133262e+015  4051339
0 g1f3   2.704522e+015  4051339
0 b1c3   2.730558e+015  4051339
0 b1a3   2.100711e+015  4051339
Perft 6.284979e+016
wasted 18.15
------------ 100 --------------
0 h2h3   1.813818e+015  4066846
0 h2h4   2.620225e+015  4066837
0 g2g3   2.498103e+015  4066830
0 g2g4   2.217839e+015  4066828
0 f2f3   1.553586e+015  4066845
0 f2f4   2.051291e+015  4066828
0 e2e3   7.161178e+015  4066828
0 e2e4   7.259682e+015  4066828
0 d2d3   4.588529e+015  4066828
0 d2d4   6.325524e+015  4066828
0 c2c3   2.751428e+015  4066828
0 c2c4   3.120796e+015  4066828
0 b2b3   2.407281e+015  4066828
0 b2b4   2.412439e+015  4066828
0 a2a3   1.824787e+015  4066847
0 a2a4   2.574513e+015  4066827
0 g1h3   2.133173e+015  4066827
0 g1f3   2.704510e+015  4066827
0 b1c3   2.730586e+015  4066827
0 b1a3   2.100645e+015  4066827
Perft 6.284993e+016
wasted 18.66
Time : 3160953ms Tree : nodes 826359 depth 4/0 pps 25731 visits 81336620

[Daniel Shawul]

Tree splitting is introducing more puzzles. The best performing formula
so far for the non-splitting version was log-proportioning followed by uniform.
But for tree splitting uniform performs the best and by a huge margin at that.
Second comes regular UCT with Constant = 2. Here are the results

UCT

Code: Select all

------------ 18 --------------
0 h2h3   1.811549e+015  136165
0 h2h4   2.615054e+015  221580
0 g2g3   2.499273e+015  207246
0 g2g4   2.215468e+015  175228
0 f2f3   1.554187e+015  114568
0 f2f4   2.049758e+015  158359
0 e2e3   7.153889e+015  3711845
0 e2e4   7.260329e+015  4073208
0 d2d3   4.589652e+015  664142
0 d2d4   6.324741e+015  1953074
0 c2c3   2.746617e+015  238864
0 c2c4   3.114315e+015  293555
0 b2b3   2.402874e+015  195895
0 b2b4   2.412730e+015  197033
0 a2a3   1.822213e+015  137111
0 a2a4   2.573533e+015  216349
0 g1h3   2.132545e+015  166631
0 g1f3   2.696766e+015  232185
0 b1c3   2.730632e+015  236705
0 b1a3   2.099148e+015  163257
Perft 6.280527e+016
wasted 25.04

Sub-tree size proportion

Code: Select all

------------ 30 --------------
0 h2h3   1.805217e+015  695760
0 h2h4   2.609891e+015  1005895
0 g2g3   2.486378e+015  958290
0 g2g4   2.207506e+015  850808
0 f2f3   1.541694e+015  594194
0 f2f4   2.039275e+015  785969
0 e2e3   7.129478e+015  2747817
0 e2e4   7.235552e+015  2788699
0 d2d3   4.575589e+015  1763506
0 d2d4   6.307242e+015  2430913
0 c2c3   2.741543e+015  1056636
0 c2c4   3.111828e+015  1199350
0 b2b3   2.395352e+015  923207
0 b2b4   2.400402e+015  925154
0 a2a3   1.815267e+015  699633
0 a2a4   2.561420e+015  987213
0 g1h3   2.120870e+015  817418
0 g1f3   2.694805e+015  1038622
0 b1c3   2.718394e+015  1047762
0 b1a3   2.092015e+015  806297
Perft 6.258971e+016
wasted 19.59

Log-proportiong

Code: Select all

------------ 30 --------------
0 h2h3   1.809051e+015  979476
0 h2h4   2.614725e+015  1220883
0 g2g3   2.491752e+015  1189312
0 g2g4   2.211496e+015  1111117
0 f2f3   1.548691e+015  877638
0 f2f4   2.043582e+015  1059366
0 e2e3   7.126227e+015  1877964
0 e2e4   7.244924e+015  1888790
0 d2d3   4.577045e+015  1587816
0 d2d4   6.308511e+015  1798087
0 c2c3   2.741889e+015  1252006
0 c2c4   3.107435e+015  1334024
0 b2b3   2.400509e+015  1164864
0 b2b4   2.402718e+015  1165467
0 a2a3   1.819238e+015  983157
0 a2a4   2.566662e+015  1208725
0 g1h3   2.124773e+015  1084900
0 g1f3   2.696414e+015  1241044
0 b1c3   2.722250e+015  1247294
0 b1a3   2.093142e+015  1075070
Perft 6.265104e+016
wasted 15.51

The last two are orders of magnitude away from the true value after 30 million simulations.
I think I will go back to non-splitting version now and determine the best resource allocation
scheme i.e visit proportions.

[Daniel Shawul]

Here is a summary in case you are lost in the dispersed posts. The result with tree splitting seem bad when I do many iterations (100 mil) compared to doing it at the root only. Also surprisingly tree size proportioning does the worst in both cases.

Code: Select all

	At root without splitting		
			
Method	             Estimate	    Error	       Rank
Uniform	            6.285137E+16	3.599237E+12	2nd
Tree size	          6.286071E+16	5.740763E+12	3rd
Log(tree size)	     6.285734E+16	2.370763E+12	1st
UCT	                6.286654E+16	1.157076E+13	4th
			
	With Splitting		
			
Uniform	            6.284993E+16	5.039237E+12	1st
Tree size	          6.258971E+16	2.652592E+14	4th
Log(tree size)	     6.265104E+16	2.039292E+14	3rd
UCT	                6.280527E+16	4.969924E+13	2nd
			
Perft(12)	          6.285497E+16		

[Daniel Shawul]

Here is one more using calculated variance. Somehow I missed that it could be calculated along with the mean...

Code: Select all

X =  (variance / child_visits)  / Sum (variance_i / child_visits_i)  - child_visits / parent_visits

It has become the new number one for the non-splitting version. And the worst for the splitting version!!
I don't know what splitting is introducing that I can't grasp. The variance propagation is properly done as the summed variance seem to follow sub-tree sizes in general..

First the best non-splitting version

Code: Select all

Time : 4120313ms Tree : nodes 21 depth 0/0 pps 24270 visits 100000000
0 h2h3   1.813533e+015 +- 1.328352e+012 3055114
0 h2h4   2.621129e+015 +- 1.580081e+012 4322746
0 g2g3   2.494642e+015 +- 1.523933e+012 4020987
0 g2g4   2.219021e+015 +- 1.387811e+012 3334736
0 f2f3   1.552831e+015 +- 1.152052e+012 2297974
0 f2f4   2.049488e+015 +- 1.400011e+012 3393623
0 e2e3   7.161295e+015 +- 2.582134e+012 11544057
0 e2e4   7.264951e+015 +- 2.552920e+012 11284323
0 d2d3   4.592934e+015 +- 1.908713e+012 6307861
0 d2d4   6.329078e+015 +- 2.411968e+012 10072654
0 c2c3   2.752768e+015 +- 1.603579e+012 4452273
0 c2c4   3.118723e+015 +- 1.695955e+012 4980007
0 b2b3   2.407438e+015 +- 1.515040e+012 3974194
0 b2b4   2.410850e+015 +- 1.493831e+012 3863702
0 a2a3   1.825903e+015 +- 1.345136e+012 3132804
0 a2a4   2.571018e+015 +- 1.566121e+012 4246700
0 g1h3   2.133845e+015 +- 1.413254e+012 3458129
0 g1f3   2.703321e+015 +- 1.530569e+012 4056080
0 b1c3   2.731478e+015 +- 1.645993e+012 4690910
0 b1a3   2.102249e+015 +- 1.424042e+012 3511126
Perft 6.285650e+016
move e2e3
Error 1.530763E+12

And the worst tree splitting version

Code: Select all

0 h2h3   1.800930e+015 +- 1.355465e+012 721585
0 h2h4   2.606648e+015 +- 1.610572e+012 1018756
0 g2g3   2.484378e+015 +- 1.566538e+012 963811
0 g2g4   2.203276e+015 +- 1.448322e+012 823834
0 f2f3   1.540924e+015 +- 1.211465e+012 576411
0 f2f4   2.038142e+015 +- 1.439154e+012 813436
0 e2e3   7.140877e+015 +- 2.657810e+012 2774326
0 e2e4   7.242817e+015 +- 2.667809e+012 2795239
0 d2d3   4.573691e+015 +- 2.004847e+012 1578600
0 d2d4   6.301205e+015 +- 2.463362e+012 2383229
0 c2c3   2.737396e+015 +- 1.660987e+012 1083533
0 c2c4   3.107309e+015 +- 1.746783e+012 1198362
0 b2b3   2.392703e+015 +- 1.544036e+012 936319
0 b2b4   2.396221e+015 +- 1.546808e+012 939684
0 a2a3   1.812262e+015 +- 1.361867e+012 728416
0 a2a4   2.557232e+015 +- 1.593382e+012 997124
0 g1h3   2.122258e+015 +- 1.449905e+012 825637
0 g1f3   2.691013e+015 +- 1.584893e+012 986528
0 b1c3   2.715758e+015 +- 1.691837e+012 1124156
0 b1a3   2.087860e+015 +- 1.469426e+012 848014
Perft 6.255290e+016
wasted 19.61

[Ajedrecista]

Hi again:

I am glad to see how Shawul's UCT run and also new Adam Hair's estimate based in estimating BF with polynomials and logarithms suit in my interval. I have worked a little on my 'method' and I discovered that is a little better than I expected! It can also estimates Perft in even cases of n (at first I thought it only could estimate odd values of plies). I have adjust another polynomial for even values, because the 'odd - even effect' is brutal when I work with my alpha - beta couple of parameters. The idea is splitting odd and even values of n (I think I said that some weeks ago) and also Reinhard exposed this effect with his inverse interpolation.

First I worked with cubic functions of alpha and beta in both even and odd values of n; secondly, I switched to a quartic function in alpha and beta (odd case) when maintained cubic function for alpha and beta (in the case of even values of n). The results were incredibly similar (sure: less than 1% of difference between cases). I had no access to true known Perft values so I did the estimates in a clumsy way: I remembered all the Perft except Perft(10), which I remembered it was around 6.9352e+13, and I did the calculations (with a normal scientific calculator) assuming Perft(10) ~ 6.93525e+13 (trying to reduce the difference). I have rounded the final values because it is too messy giving all the numbers when they are not exact, because of the issue involving Perft(10). The estimates up to Perft(20) are:

Perft(13) ~ 1.980468096e+18 (I started from this value (my estimate), as it was the true one).
Perft(14) ~ 6.1861e+19
Perft(15) ~ 2.0134e+21
Perft(16) ~ 6.5013e+22
Perft(17) ~ 2.1729e+24
Perft(18) ~ 7.2067e+25
Perft(19) ~ 2.4604e+27
Perft(20) ~ 8.3348e+28

These estimates are like a copy of Labelle estimates, but all the math took me some hours (also adjusting by hand the polynomials, but it was fast) and the ways for reaching these numbers are completely independent.

http://wismuth.com/chess/statistics-games.html

It is amazing for me how similar are my values. BF's are almost the same as Labelle ones, and always my estimates are a little less than Labelle ones. These results are the arithmetic averages of the results given by alpha and beta estimates. They also have error bars that I have omitted, but there were smaller in even cases than in odd cases. Besides, error bars grow when n grows: Perft(14) to Perft(20) (only even values of n) gave error bars from ~ ± 0.0053% to ~ ± 0.0566%; Perft(15) to Perft(19) (only odd values of n) gave error bars from ~ ± 0.05% to ~ ± 0.17% (remember that error bar was ~ ± 0.01022% for n = 13).

Splitting polynomials is crucial: in a first momment I tried to estimate Perft(14) to Perft(20) with the help of an only polynomial and results were horrible! Althouh Perft(14) and Perft(15) were around 0.65% less than the final results I post, BF's from n = 16 to n = 20 were 26, 9(?), 18... and Perft(20) estimate was ~ 9.85912e+27 (horrible!).

Maybe it is better to increase one degree the polynomials ASAP it could be done (when new estimates are calculated). But it was simply too much work for me.

Fortunately, Mr. Edwards has posted again. His effort computing Perft(13) is very much appreciated here. Please keep the good work!

Regards from Spain.

Ajedrecista.

[sje]

Here's another piece of perft(13):
[D]rnbqkbnr/1ppppppp/p7/8/8/2NP4/PPP1PPPP/R1BQKBNR b KQkq - 0 2
The perft(10) for the above is 165,358,518,306,919. How well does your estimator algorithm do with this?