Perft(13) betting pool

[petero2]

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

Using "Peter1" with fw=4:

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

[Daniel Shawul]

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

[Daniel Shawul]

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.

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

3-ply

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

4-ply

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

5-ply

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

6-ply. Very early result

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

[Michel]

Inside the tree the simulations are proportioned by sub-tree size (no variance yet),

Can you make an attempt to clearly explain what you mean by "simulations"?
You are not doing random walks inside the tree so I am confused by "simulations inside the tree".

the second sequence of randome number

What do you mean by a second set of random numbers?

EDIT

Of course the results look very good! I forgot to say that.

[Michel]

6 ply

Code: Select all

6.285450e+016 +- 1.468664e+012  1553018009  

This is has sd*sqrt(moveGen)=5.787762e+16 and z value -0.32
So it does indeed look very good.

5 ply

Code: Select all

6.285681e+016 +- 4.231172e+012 502172276 

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).

[Michel]

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.)

[Daniel Shawul]

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

[Michel]

I always wonder what the third and fourth column are in your tables. Do they carry any information?

[Daniel Shawul]

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:

Code: Select all

Full-grown tree in memory + N-ply full wdith + Monte-carlo

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.

[Daniel Shawul]

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.