I agree with this. In retrospect, it would have been better to measure the effect of increased full-width search in the HGM and Peter1 methods before spending too much time on the UCT/weighted sampling methods.Daniel Shawul wrote:I think the reason for the sudden jump in performance of full_width +MC is because up to now for depth <= 3, it was same as _uniform_ allocation. But for depth = 5 and more it becomes proportioning by sub-tree nodes count up to leaf nodes. It was a sub-tree count proportioning all along but we didn't notice it because sub-trees are uniform for depth<=3. So with that in mind it can be beaten f.i if I do full-width expansion to depth=5. Depth=6 would require too much memory though , which is a disadvantage for any breadth first searcher. Having said that it can perform bad for a selective tree where the shape of the upper portion of the tree is not related with the sub-tree size. Another idea applicable for the perft(13) competition would be to take the exact perft(12) results for 2-plies from the root and use that to determine the proportions for the monte-carlo simulations. The depth-first search does a static allocation, so a static allocation based on the real sub-tree size may perform better.
Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 690
- Joined: Mon Apr 19, 2010 7:07 pm
- Location: Sweden
- Full name: Peter Osterlund
Re: Summary of Monte Carlo results for perft(12) so far
-
- Posts: 690
- Joined: Mon Apr 19, 2010 7:07 pm
- Location: Sweden
- Full name: Peter Osterlund
Re: A few more records
sje wrote:The perft(13) run has been going for just over 12 days and has produced 210 draft ten records. Here are the most recent ten of these:How well do your estimation algorithms perform on the above?Code: Select all
rnbqkbnr/1ppppppp/8/p7/1P6/2P5/P2PPPPP/RNBQKBNR b KQkq - 0 2 10 154068837107809 rnbqkbnr/1ppppppp/8/p7/2P5/7N/PP1PPPPP/RNBQKB1R b KQkq - 0 2 10 126452584569476 rnbqkbnr/1ppppppp/8/p7/8/1P1P4/P1P1PPPP/RNBQKBNR b KQkq - 0 2 10 197935747435700 rnbqkbnr/1ppppppp/8/p7/8/P2P4/1PP1PPPP/RNBQKBNR b KQkq - 0 2 10 163777451315240 rnbqkbnr/1ppppppp/8/p7/2P5/5N2/PP1PPPPP/RNBQKB1R b KQkq - 0 2 10 161971799868266 rnbqkbnr/1ppppppp/8/p7/P7/3P4/1PP1PPPP/RNBQKBNR b KQkq - 0 2 10 166336655168294 rnbqkbnr/1ppppppp/8/p7/8/N3P3/PPPP1PPP/R1BQKBNR b KQkq - 0 2 10 290223899535804 rnbqkbnr/1ppppppp/8/p7/1PP5/8/P2PPPPP/RNBQKBNR b KQkq - 0 2 10 185603264146369 rnbqkbnr/1ppppppp/8/p7/8/3P3N/PPP1PPPP/RNBQKB1R b KQkq - 0 2 10 181649457773953 rnbqkbnr/1ppppppp/8/p7/8/2N1P3/PPPP1PPP/R1BQKBNR b KQkq - 0 2 10 406608149434105
Using "Peter1" with fw=4:sje wrote:The average time for calculating a draft 10 record in the current run is about 5,013 seconds. It would be interesting to see the quality of estimations that can be computed in, say, one percent of the actual full calculation time.
Code: Select all
pos m relerr movGens cycles t
1 154093378234301 1.593e-04 31099978 17 53.073
2 126467517170116 1.181e-04 33530832 21 50.747
3 197915769847456 -1.009e-04 34568046 15 52.250
4 163820486561991 2.628e-04 34776633 17 52.521
5 161965379089192 -3.964e-05 35094578 19 51.665
6 166368914541236 1.939e-04 34560150 17 52.240
7 290318396860821 3.256e-04 32154093 12 52.511
8 185597417904519 -3.150e-05 33747973 17 52.674
9 181579829695344 -3.833e-04 34778534 16 52.431
10 406543544328447 -1.589e-04 31748598 10 52.491
-
- Posts: 134
- Joined: Mon May 16, 2011 6:58 pm
- Location: Denmark
Re: Summary of Monte Carlo results for perft(12) so far
Here is a idea to create upper limit:
Make an engine only using AB , and then search to depth 13, call it x
Then because AB can prune down to sqrt(n) , where n is the number of nodes searched in minimax
So , the upper limit is x*x !!
Now, i only need to find lower limit, then i will place my bet.
I dont know if this idea was written before, i didnt look through the 51 pages
Make an engine only using AB , and then search to depth 13, call it x
Then because AB can prune down to sqrt(n) , where n is the number of nodes searched in minimax
So , the upper limit is x*x !!
Now, i only need to find lower limit, then i will place my bet.
I dont know if this idea was written before, i didnt look through the 51 pages
-
- Posts: 690
- Joined: Mon Apr 19, 2010 7:07 pm
- Location: Sweden
- Full name: Peter Osterlund
Re: Four more draft 11 results
Using "Peter1" with fw=4:sje wrote:Four more draft 11 results:Code: Select all
rnbqkbnr/1ppppppp/p7/8/8/7N/PPPPPPPP/RNBQKB1R w KQkq - 0 2 11 1882390155585040 rnbqkbnr/1ppppppp/p7/8/8/5N2/PPPPPPPP/RNBQKB1R w KQkq - 0 2 11 2373558610955814 rnbqkbnr/1ppppppp/p7/8/P7/8/1PPPPPPP/RNBQKBNR w KQkq - 0 2 11 2250225134770081 rnbqkbnr/1ppppppp/p7/8/1P6/8/P1PPPPPP/RNBQKBNR w KQkq - 0 2 11 2178802463490013
Code: Select all
pos m relerr movGens cycles t
1 1882187511466999 -1.077e-04 31976759 25 51.595
2 2373493606651359 -2.739e-05 34480301 23 50.017
3 2250889179435356 2.951e-04 33629253 24 50.388
4 2180070932865356 5.822e-04 33522770 24 51.678
-
- 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