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.Michel wrote: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.
Code: Select all
X = (log(child_nodes) / log(parent_nodes)) - (child_visits / parent_visits)
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
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
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