Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
Well there might still be a way around it. The major constraint is memory here so I am trying first to store all the ply 1 - 5 nodes in memory for a total of 5M nodes. Then instead of doing a single MC search do a 1-ply full width + MC, thereby simulating a 6-ply depth first search. We get the saving from move generator calls that way because we are doing >=20 simulation per move gen call now. An additional advantage is we can use any kind of weighing in the first 5-ply..
So the new method is Tree growth + N ply full width (currenlty 1) + MC
So the new method is Tree growth + N ply full width (currenlty 1) + MC
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
Well here are the result for 3-ply,4-ply and 5-ply searches.
N-ply == (N - 1)-ply tree + 1-ply full width.
It beats the Peter1 method for all plies at 500 mil move gen calls. I am now running the 6-ply simulation i.e 5-ply tree + 1ply full width, and it will probably beat it at that too. But it is taking a long time even to initialize.
Inside the tree the simulations are proportioned by sub-tree size (no variance yet), and I do 1 in BF extra work to guide the simulation towards the larger nodes. This new full-width addition make that a little beat neat because for the second sequence of randome number I just call pert(depth,0) instead of perft(depth,1) where the second parameter is the full-width depth.
Lets call this Daniel2 method.
Edit: I added a very early 6-ply result and it beats it! Cost will probably increase as more simulations are done.
3-ply
4-ply
5-ply
6-ply. Very early result
N-ply == (N - 1)-ply tree + 1-ply full width.
It beats the Peter1 method for all plies at 500 mil move gen calls. I am now running the 6-ply simulation i.e 5-ply tree + 1ply full width, and it will probably beat it at that too. But it is taking a long time even to initialize.
Inside the tree the simulations are proportioned by sub-tree size (no variance yet), and I do 1 in BF extra work to guide the simulation towards the larger nodes. This new full-width addition make that a little beat neat because for the second sequence of randome number I just call pert(depth,0) instead of perft(depth,1) where the second parameter is the full-width depth.
Lets call this Daniel2 method.
Edit: I added a very early 6-ply result and it beats it! Cost will probably increase as more simulations are done.
Code: Select all
3-ply: 6.286800e+016 +- 7.586481e+012 6.288038e+016 +- 4.054303e+013 500208240 cost 1.70e17
4-ply: 6.286032e+016 +- 5.702099e+012 6.264060e+016 +- 3.167983e+013 500199179 cost 1.27e17
5-ply: 6.285666e+016 +- 4.238790e+012 6.053662e+016 +- 2.272920e+013 500177513 cost 9.48e16
6-ply: 6.285457e+016 +- 1.460421e+012 6.220171e+016 +- 7.840821e+012 1573088359 cost 5.80e16
Code: Select all
=========Cycles 2150000 : Total nodes 421 ==========
0 h2h3 1.816437e+015 +- 1.516354e+012 62414 | 1.825237e+015 +- 7.555796e+012 62414 | 20
0 h2h4 2.620167e+015 +- 1.694351e+012 89862 | 2.627918e+015 +- 8.702081e+012 89862 | 20
0 g2g3 2.499736e+015 +- 1.621368e+012 85870 | 2.511210e+015 +- 8.218835e+012 85870 | 20
0 g2g4 2.219654e+015 +- 1.446357e+012 76148 | 2.226892e+015 +- 7.405339e+012 76148 | 20
0 f2f3 1.550880e+015 +- 1.261040e+012 52940 | 1.548187e+015 +- 6.071232e+012 52940 | 20
0 f2f4 2.051624e+015 +- 1.548011e+012 70175 | 2.052222e+015 +- 7.600253e+012 70175 | 20
0 e2e3 7.159616e+015 +- 2.318287e+012 245354 | 7.175195e+015 +- 1.400664e+013 245354 | 20
0 e2e4 7.265394e+015 +- 2.277278e+012 247242 | 7.230428e+015 +- 1.356439e+013 247242 | 20
0 d2d3 4.589375e+015 +- 1.690479e+012 156644 | 4.580952e+015 +- 9.235422e+012 156644 | 20
0 d2d4 6.323906e+015 +- 2.185788e+012 216184 | 6.322135e+015 +- 1.288516e+013 216184 | 20
0 c2c3 2.752453e+015 +- 1.705661e+012 94128 | 2.752715e+015 +- 8.649213e+012 94128 | 20
0 c2c4 3.123560e+015 +- 1.737934e+012 106991 | 3.128879e+015 +- 8.907060e+012 106991 | 20
0 b2b3 2.411202e+015 +- 1.630181e+012 82640 | 2.416761e+015 +- 8.450601e+012 82640 | 20
0 b2b4 2.410516e+015 +- 1.612745e+012 82144 | 2.402261e+015 +- 8.196439e+012 82144 | 20
0 a2a3 1.825314e+015 +- 1.528506e+012 62827 | 1.837312e+015 +- 7.660223e+012 62827 | 20
0 a2a4 2.574571e+015 +- 1.677280e+012 87801 | 2.567654e+015 +- 8.665106e+012 87801 | 20
0 g1h3 2.130785e+015 +- 1.538562e+012 72788 | 2.128650e+015 +- 7.657659e+012 72788 | 20
0 g1f3 2.704455e+015 +- 1.534585e+012 92553 | 2.706615e+015 +- 7.825380e+012 92553 | 20
0 b1c3 2.734342e+015 +- 1.766623e+012 93286 | 2.728083e+015 +- 9.245511e+012 93286 | 20
0 b1a3 2.102645e+015 +- 1.582323e+012 72028 | 2.106407e+015 +- 8.009812e+012 72028 | 20
Perft 6.286663e+016 +- 7.665370e+012 6.287571e+016 +- 4.095537e+013
wasted 0.00
6.286663e+016 +- 7.656936e+012 6.287598e+016 +- 4.091000e+013 491100695
6.286692e+016 +- 7.648189e+012 6.287817e+016 +- 4.086215e+013 492239383
6.286689e+016 +- 7.639079e+012 6.287891e+016 +- 4.081561e+013 493383235
6.286736e+016 +- 7.630168e+012 6.287805e+016 +- 4.076466e+013 494522799
6.286763e+016 +- 7.621055e+012 6.287597e+016 +- 4.071425e+013 495659349
6.286753e+016 +- 7.612527e+012 6.287656e+016 +- 4.066604e+013 496794317
6.286783e+016 +- 7.604004e+012 6.288076e+016 +- 4.063283e+013 497929187
6.286781e+016 +- 7.595069e+012 6.287930e+016 +- 4.058690e+013 499067483
6.286800e+016 +- 7.586481e+012 6.288038e+016 +- 4.054303e+013 500208240
6.286738e+016 +- 7.577834e+012 6.288004e+016 +- 4.049695e+013 501349145
Code: Select all
=========Cycles 2450000 : Total nodes 9323 ==========
0 h2h3 1.813992e+015 +- 1.001350e+012 70503 | 1.802493e+015 +- 5.506969e+012 70503 | 380
0 h2h4 2.618920e+015 +- 1.180801e+012 102151 | 2.611623e+015 +- 6.548085e+012 102151 | 420
0 g2g3 2.497781e+015 +- 1.136522e+012 97338 | 2.488588e+015 +- 6.342843e+012 97338 | 420
0 g2g4 2.218658e+015 +- 1.029162e+012 86378 | 2.208357e+015 +- 5.696243e+012 86378 | 421
0 f2f3 1.552853e+015 +- 8.645670e+011 60738 | 1.552828e+015 +- 4.879883e+012 60738 | 380
0 f2f4 2.051754e+015 +- 1.070416e+012 80063 | 2.046935e+015 +- 5.902686e+012 80063 | 401
0 e2e3 7.161137e+015 +- 1.972783e+012 280019 | 7.159072e+015 +- 1.096064e+013 280019 | 599
0 e2e4 7.263882e+015 +- 1.953337e+012 283250 | 7.241681e+015 +- 1.084864e+013 283250 | 600
0 d2d3 4.588350e+015 +- 1.371428e+012 179152 | 4.580279e+015 +- 7.857689e+012 179152 | 539
0 d2d4 6.329112e+015 +- 1.786558e+012 246114 | 6.292255e+015 +- 9.987906e+012 246114 | 560
0 c2c3 2.752284e+015 +- 1.217414e+012 107281 | 2.742793e+015 +- 6.728741e+012 107281 | 420
0 c2c4 3.121531e+015 +- 1.262177e+012 122195 | 3.124099e+015 +- 7.122845e+012 122195 | 441
0 b2b3 2.407437e+015 +- 1.127666e+012 93624 | 2.393594e+015 +- 6.267465e+012 93624 | 420
0 b2b4 2.412374e+015 +- 1.132433e+012 93352 | 2.386676e+015 +- 6.142358e+012 93352 | 421
0 a2a3 1.825209e+015 +- 1.016115e+012 71210 | 1.820595e+015 +- 5.596367e+012 71210 | 380
0 a2a4 2.571421e+015 +- 1.160920e+012 100418 | 2.567316e+015 +- 6.506417e+012 100418 | 420
0 g1h3 2.133932e+015 +- 1.061872e+012 83097 | 2.124504e+015 +- 5.811385e+012 83097 | 400
0 g1f3 2.704256e+015 +- 1.117966e+012 105407 | 2.694857e+015 +- 6.350189e+012 105407 | 440
0 b1c3 2.733591e+015 +- 1.277251e+012 106260 | 2.716678e+015 +- 6.893029e+012 106260 | 440
0 b1a3 2.101880e+015 +- 1.098028e+012 81469 | 2.082884e+015 +- 5.952896e+012 81469 | 400
Perft 6.286035e+016 +- 5.713582e+012 6.263810e+016 +- 3.174255e+013
wasted 0.00
6.286025e+016 +- 5.707846e+012 6.263946e+016 +- 3.171019e+013 499191478
6.286032e+016 +- 5.702099e+012 6.264060e+016 +- 3.167983e+013 500199179
6.286038e+016 +- 5.696163e+012 6.264007e+016 +- 3.164949e+013 501209023
6.286067e+016 +- 5.690592e+012 6.264084e+016 +- 3.161730e+013 502219392
6.286083e+016 +- 5.684859e+012 6.263957e+016 +- 3.158378e+013 503231435
6.286062e+016 +- 5.679009e+012 6.264234e+016 +- 3.155415e+013 504241387
Code: Select all
=========Cycles 2100000 : Total nodes 206604 ==========
0 h2h3 1.813539e+015 +- 7.574783e+011 59816 | 1.723225e+015 +- 3.740894e+012 59816 | 8457
0 h2h4 2.619993e+015 +- 8.926649e+011 87068 | 2.508337e+015 +- 4.577603e+012 87068 | 9329
0 g2g3 2.499931e+015 +- 8.559646e+011 82946 | 2.389548e+015 +- 4.386151e+012 82946 | 9345
0 g2g4 2.217592e+015 +- 7.744455e+011 73579 | 2.119727e+015 +- 3.954693e+012 73579 | 9328
0 f2f3 1.552812e+015 +- 6.809558e+011 51179 | 1.474412e+015 +- 3.182406e+012 51179 | 8457
0 f2f4 2.050979e+015 +- 8.271335e+011 67262 | 1.937730e+015 +- 3.996856e+012 67262 | 8929
0 e2e3 7.160790e+015 +- 1.405259e+012 242349 | 6.981759e+015 +- 8.403430e+012 242349 | 13134
0 e2e4 7.263839e+015 +- 1.408812e+012 245156 | 7.062648e+015 +- 8.341357e+012 245156 | 13160
0 d2d3 4.589002e+015 +- 1.054308e+012 155116 | 4.468710e+015 +- 5.646138e+012 155116 | 11959
0 d2d4 6.326555e+015 +- 1.294710e+012 215111 | 6.197081e+015 +- 7.537558e+012 215111 | 12435
0 c2c3 2.752712e+015 +- 9.273918e+011 91305 | 2.630384e+015 +- 4.831362e+012 91305 | 9272
0 c2c4 3.119772e+015 +- 9.739257e+011 104044 | 2.997345e+015 +- 5.048817e+012 104044 | 9744
0 b2b3 2.407401e+015 +- 8.526924e+011 79736 | 2.297107e+015 +- 4.346066e+012 79736 | 9345
0 b2b4 2.415146e+015 +- 8.541859e+011 79898 | 2.301770e+015 +- 4.379060e+012 79898 | 9332
0 a2a3 1.826118e+015 +- 7.687855e+011 60217 | 1.734765e+015 +- 3.789319e+012 60217 | 8457
0 a2a4 2.572738e+015 +- 8.774967e+011 85377 | 2.459620e+015 +- 4.488547e+012 85377 | 9329
0 g1h3 2.131796e+015 +- 8.059058e+011 70754 | 2.038347e+015 +- 4.018077e+012 70754 | 8881
0 g1f3 2.703661e+015 +- 8.577422e+011 90224 | 2.599254e+015 +- 4.385904e+012 90224 | 9748
0 b1c3 2.730982e+015 +- 9.546319e+011 89967 | 2.591828e+015 +- 4.961447e+012 89967 | 9755
0 b1a3 2.101094e+015 +- 8.476288e+011 68915 | 1.985355e+015 +- 4.166821e+012 68915 | 8885
Perft 6.285645e+016 +- 4.270784e+012 6.049895e+016 +- 2.288190e+013
wasted 0.00
6.285655e+016 +- 4.266770e+012 6.050210e+016 +- 2.286201e+013 493178805
6.285673e+016 +- 4.262946e+012 6.050672e+016 +- 2.284222e+013 494180536
6.285687e+016 +- 4.259199e+012 6.050931e+016 +- 2.282213e+013 495181109
6.285708e+016 +- 4.255470e+012 6.051476e+016 +- 2.280303e+013 496180557
6.285663e+016 +- 4.251481e+012 6.052065e+016 +- 2.278475e+013 497178862
6.285695e+016 +- 4.246480e+012 6.052721e+016 +- 2.276578e+013 498182385
6.285662e+016 +- 4.242646e+012 6.053237e+016 +- 2.274807e+013 499180306
6.285666e+016 +- 4.238790e+012 6.053662e+016 +- 2.272920e+013 500177513
6.285656e+016 +- 4.234939e+012 6.054024e+016 +- 2.271109e+013 501174200
6.285681e+016 +- 4.231172e+012 6.054363e+016 +- 2.269323e+013 502172276
Code: Select all
=========Cycles 200000 : Total nodes 5072213 ==========
0 h2h3 1.814344e+015 +- 2.201589e+011 4729 | 1.802638e+015 +- 1.268237e+012 4729 | 181044
0 h2h4 2.620801e+015 +- 2.787637e+011 7653 | 2.603552e+015 +- 1.613453e+012 7653 | 218829
0 g2g3 2.498487e+015 +- 2.659905e+011 6896 | 2.483066e+015 +- 1.531492e+012 6896 | 217210
0 g2g4 2.217473e+015 +- 2.281207e+011 5213 | 2.204288e+015 +- 1.331640e+012 5213 | 214052
0 f2f3 1.552603e+015 +- 1.781889e+011 3408 | 1.547076e+015 +- 1.076635e+012 3408 | 178891
0 f2f4 2.050649e+015 +- 2.365330e+011 5643 | 2.042938e+015 +- 1.385397e+012 5643 | 198475
0 e2e3 7.161826e+015 +- 5.959990e+011 29667 | 7.080242e+015 +- 3.176565e+012 29667 | 402988
0 e2e4 7.263510e+015 +- 5.938324e+011 29559 | 7.206160e+015 +- 3.170812e+012 29559 | 405385
0 d2d3 4.588112e+015 +- 3.536287e+011 13048 | 4.559797e+015 +- 2.106719e+012 13048 | 328511
0 d2d4 6.326948e+015 +- 5.138650e+011 23989 | 6.271870e+015 +- 2.856421e+012 23989 | 361790
0 c2c3 2.751522e+015 +- 3.034981e+011 8424 | 2.729663e+015 +- 1.692732e+012 8424 | 222861
0 c2c4 3.120311e+015 +- 3.155278e+011 9653 | 3.097067e+015 +- 1.812001e+012 9653 | 240082
0 b2b3 2.407656e+015 +- 2.571396e+011 6509 | 2.390842e+015 +- 1.487896e+012 6509 | 215255
0 b2b4 2.412369e+015 +- 2.612425e+011 6419 | 2.397583e+015 +- 1.477690e+012 6419 | 216145
0 a2a3 1.824939e+015 +- 2.232747e+011 4870 | 1.815357e+015 +- 1.287113e+012 4870 | 181046
0 a2a4 2.572201e+015 +- 2.731715e+011 7317 | 2.556886e+015 +- 1.577621e+012 7317 | 217832
0 g1h3 2.132567e+015 +- 2.402928e+011 5614 | 2.122531e+015 +- 1.381879e+012 5614 | 198502
0 g1f3 2.704775e+015 +- 2.614345e+011 6984 | 2.687237e+015 +- 1.541331e+012 6984 | 233491
0 b1c3 2.731588e+015 +- 3.049907e+011 8472 | 2.710960e+015 +- 1.697579e+012 8472 | 234656
0 b1a3 2.102079e+015 +- 2.520311e+011 5952 | 2.086796e+015 +- 1.422877e+012 5952 | 198572
Perft 6.285476e+016 +- 1.471995e+012 6.239655e+016 +- 8.248282e+012
wasted 0.00
6.285474e+016 +- 1.471651e+012 6.238878e+016 +- 8.231859e+012 1545654984
6.285475e+016 +- 1.471242e+012 6.238128e+016 +- 8.215821e+012 1546575476
6.285488e+016 +- 1.470884e+012 6.237380e+016 +- 8.200210e+012 1547496821
6.285483e+016 +- 1.470580e+012 6.236618e+016 +- 8.185017e+012 1548418301
6.285472e+016 +- 1.470343e+012 6.236008e+016 +- 8.169903e+012 1549339143
6.285465e+016 +- 1.469928e+012 6.235295e+016 +- 8.155214e+012 1550259386
6.285462e+016 +- 1.469468e+012 6.234621e+016 +- 8.140511e+012 1551179682
6.285456e+016 +- 1.469046e+012 6.233953e+016 +- 8.125811e+012 1552099258
6.285450e+016 +- 1.468664e+012 6.233290e+016 +- 8.111591e+012 1553018009
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
Can you make an attempt to clearly explain what you mean by "simulations"?Inside the tree the simulations are proportioned by sub-tree size (no variance yet),
You are not doing random walks inside the tree so I am confused by "simulations inside the tree".
What do you mean by a second set of random numbers?the second sequence of randome number
EDIT
Of course the results look very good! I forgot to say that.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
6 ply
This is has sd*sqrt(moveGen)=5.787762e+16 and z value -0.32
So it does indeed look very good.
5 ply
sd*sqrt(moveGen)=9.481718e+16
z value= 0.45
BTW I propose to call sd*sqrt(moveGen) the "normalized standard deviation" and perhaps denote it by sdn.
The expected standard deviation for an N nodes search is then sdn/sqrt(N).
Code: Select all
6.285450e+016 +- 1.468664e+012 1553018009
So it does indeed look very good.
5 ply
Code: Select all
6.285681e+016 +- 4.231172e+012 502172276
z value= 0.45
BTW I propose to call sd*sqrt(moveGen) the "normalized standard deviation" and perhaps denote it by sdn.
The expected standard deviation for an N nodes search is then sdn/sqrt(N).
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
I just deleted a long post by accidentally typing cntrl-W (close tab).
I had attempted to give a summary of the methods of Perft estimation which have been proposed so far. They are all built from an estimator for a sum which is invoke recursively. These estimators are not mutually exclusive and can be combined in a single perft search. Three estimators for a sum have been proposed (Peter, Daniel and HGM).
Let me just say here that I suspect Daniel's method is to run perft searches on the leaf nodes of a full width subtree of depth d (in memory) and take the sum of the averages of the perft searches in each leaf node.
In that case the number of searches in a leaf node should (optimally) be proportional to the standard deviation of the estimator used in that leaf node with the important caveat that the data used for the variance computation cannot be reused for perft computations or one introduces bias (as Peter's example shows in a very simplified setting).
(EDIT: replaced variance by standard deviation in the last paragraph.)
I had attempted to give a summary of the methods of Perft estimation which have been proposed so far. They are all built from an estimator for a sum which is invoke recursively. These estimators are not mutually exclusive and can be combined in a single perft search. Three estimators for a sum have been proposed (Peter, Daniel and HGM).
Let me just say here that I suspect Daniel's method is to run perft searches on the leaf nodes of a full width subtree of depth d (in memory) and take the sum of the averages of the perft searches in each leaf node.
In that case the number of searches in a leaf node should (optimally) be proportional to the standard deviation of the estimator used in that leaf node with the important caveat that the data used for the variance computation cannot be reused for perft computations or one introduces bias (as Peter's example shows in a very simplified setting).
(EDIT: replaced variance by standard deviation in the last paragraph.)
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
Code: Select all
3-ply: 6.286800e+016 +- 7.586481e+012 6.288038e+016 +- 4.054303e+013 500208240 cost 1.70e17
4-ply: 6.286032e+016 +- 5.702099e+012 6.264060e+016 +- 3.167983e+013 500199179 cost 1.27e17
5-ply: 6.285666e+016 +- 4.238790e+012 6.053662e+016 +- 2.272920e+013 500177513 cost 9.48e16
5-ply: 6.285285e+016 +- 2.172712e+012 6.227465e+016 +- 1.229267e+013 2000964271 cost 9.70e16
6-ply: 6.285457e+016 +- 1.460421e+012 6.220171e+016 +- 7.840821e+012 1573088359 cost 5.80e16
6-ply: 6.285517e+016 +- 1.366125e+012 6.127319e+016 +- 6.178263e+012 1894434711 cost 5.94e16
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
I always wonder what the third and fourth column are in your tables. Do they carry any information?
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
Well it is very similar to what I have been doing with one new addition that is : I do a one ply full width before doing monte carlo simulation. This way I can store only 5M nodes of the perft(5) tree. So:
I have plan to further break down the full-width section into selective and non-selective part, something like HG's.
Steps :
a) Grow an N - 1 ply tree in memory and do 1 or 2 simulations for a leaf node
b) Two sequences of random number are used. The one that guides the search calls perft(depth,0), meaning it skips the full width part. The first sequence calls perft(depth,1) so it calls the 1-ply full width part. So it means the second sequence costs only 1/BF ~ 1/27 or so (at depth=6) of the first sequence. Earlier I was using something like call perft(depth,0) 10 times for the first sequence, but this new addition makes this process neat.
c) I use proportioning by sub-tree size. If you use the Peter1 depth-first search it uses proportioning by sub-tree count of the leaf nodes. I haven't yet started to see if other formulas with variance term in it would improve it but I suspect mean proportioning is pretty good too.
d) mean and variance are back-propagated as usual and that is it I guess.
Code: Select all
Full-grown tree in memory + N-ply full wdith + Monte-carlo
Steps :
a) Grow an N - 1 ply tree in memory and do 1 or 2 simulations for a leaf node
b) Two sequences of random number are used. The one that guides the search calls perft(depth,0), meaning it skips the full width part. The first sequence calls perft(depth,1) so it calls the 1-ply full width part. So it means the second sequence costs only 1/BF ~ 1/27 or so (at depth=6) of the first sequence. Earlier I was using something like call perft(depth,0) 10 times for the first sequence, but this new addition makes this process neat.
c) I use proportioning by sub-tree size. If you use the Peter1 depth-first search it uses proportioning by sub-tree count of the leaf nodes. I haven't yet started to see if other formulas with variance term in it would improve it but I suspect mean proportioning is pretty good too.
d) mean and variance are back-propagated as usual and that is it I guess.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Summary of Monte Carlo results for perft(12) so far
No that is just the result of the second sequence of random numbers which gets dumped in the end. Well to my surprise it gave good values for the 3-ply result but of course it should be ignored since it is biased.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Summary of Monte Carlo results for perft(12) so far
Just for the record. As I was saying above. The optimal frequency is proportional to the standard deviation of the estimator used in the leaf node.I use proportioning by sub-tree size. If you use the Peter1 depth-first search it uses proportioning by sub-tree count of the leaf nodes. I haven't yet started to see if other formulas with variance term in it would improve it but I suspect mean proportioning is pretty good too.
But since it might be too expensive to get a good estimation of the standard deviation
(you cannot reuse those searches for perft) using the subtree size is probably a good idea.
Last edited by Michel on Tue Aug 16, 2011 1:20 pm, edited 1 time in total.