Perft(15) estimates thread

[Ajedrecista]

Hello:

I ran a MonteCarlo Perft for estimate Perft(15): I used Nebiyu 1.42 this time.

Code: Select all

========== nebiyu.ini =======
log on
ht 64
mt  1
smp_depth           4
cluster_depth       8
message_poll_nodes  200 
resign              2000
==============================
ht 1048576 X 64 = 64MB
<COMMAND LINE>
==============================
<000000012078> nebiyuchess perftmc 15
Illegal move: nebiyuchess
1.{2.005561e+021} 2.005561e+021 +- 0.000000e+000 205075 0.00 sec
2.{1.980044e+021} 1.992802e+021 +- 9.021608e+018 410172 0.00 sec
3.{2.024441e+021} 2.003349e+021 +- 1.050357e+019 615225 0.00 sec
4.{1.985136e+021} 1.998795e+021 +- 8.809392e+018 820285 0.00 sec
5.{2.022494e+021} 2.003535e+021 +- 8.224297e+018 1025351 0.00 sec
6.{1.968165e+021} 1.997640e+021 +- 8.713797e+018 1230454 0.00 sec
7.{2.003171e+021} 1.998430e+021 +- 7.504698e+018 1435563 0.00 sec
8.{2.004777e+021} 1.999224e+021 +- 6.608415e+018 1640628 0.00 sec
9.{2.017054e+021} 2.001205e+021 +- 6.163954e+018 1845714 0.00 sec

[...]

2430.{2.014170e+021} 2.015238e+021 +- 5.103281e+017 498339283 0.00 sec
2431.{2.017086e+021} 2.015239e+021 +- 5.101187e+017 498544369 0.00 sec
2432.{2.014235e+021} 2.015239e+021 +- 5.099092e+017 498749465 0.00 sec
2433.{2.020088e+021} 2.015241e+021 +- 5.097035e+017 498954540 0.00 sec
2434.{2.039108e+021} 2.015250e+021 +- 5.095884e+017 499159607 0.00 sec
2435.{2.005434e+021} 2.015246e+021 +- 5.093950e+017 499364707 0.00 sec
2436.{2.010789e+021} 2.015245e+021 +- 5.091892e+017 499569742 0.00 sec
2437.{2.049706e+021} 2.015259e+021 +- 5.091766e+017 499774829 0.00 sec
2438.{2.005343e+021} 2.015255e+021 +- 5.089840e+017 499979862 0.00 sec
2439.{2.024066e+021} 2.015258e+021 +- 5.087881e+017 500184922 0.00 sec
time 4981.81 sec

I finally understood more less the difference between the value in braces {} and the other value: the first value is an estimate and the other value is the average of estimates. For example:

Code: Select all

1.{2.005561e+021} 2.005561e+021 +- 0.000000e+000 205075 0.00 sec
2.{1.980044e+021} 1.992802e+021 +- 9.021608e+018 410172 0.00 sec

(2.005561e+021 + 1.980044e+021)/2 = 1.9928025e+21

----------------------------------------------------------------

1.{2.005561e+021} 2.005561e+021 +- 0.000000e+000 205075 0.00 sec
2.{1.980044e+021} 1.992802e+021 +- 9.021608e+018 410172 0.00 sec
3.{2.024441e+021} 2.003349e+021 +- 1.050357e+019 615225 0.00 sec

(2.005561e+021 + 1.980044e+021 + 2.024441e+021)/3 ~ 2.003349e+21

----------------------------------------------------------------

And so on.

Knowing that sdn = std_dev*sqrt(nodes):

Code: Select all

Iteration       std_dev           Nodes       std_dev*sqrt(nodes)
 
   1         0.0000000E+00         205075        0.0000000E+00
   2         0.9021608E+19         410172        0.5777859E+22
   3         0.1050357E+20         615225        0.8238610E+22
   4         0.8809392E+19         820285        0.7978630E+22
   5         0.8224297E+19        1025351        0.8327892E+22
   6         0.8713797E+19        1230454        0.9665852E+22
   7         0.7504698E+19        1435563        0.8991753E+22
   8         0.6608415E+19        1640628        0.8464521E+22
   9         0.6163954E+19        1845714        0.8374167E+22

[...]

2430         0.5103281E+18      498339283        0.1139232E+23
2431         0.5101187E+18      498544369        0.1138998E+23
2432         0.5099092E+18      498749465        0.1138765E+23
2433         0.5097035E+18      498954540        0.1138540E+23
2434         0.5095884E+18      499159607        0.1138516E+23
2435         0.5093950E+18      499364707        0.1138318E+23
2436         0.5091892E+18      499569742        0.1138092E+23
2437         0.5091766E+18      499774829        0.1138297E+23
2438         0.5089840E+18      499979862        0.1138100E+23
2439         0.5087881E+18      500184922        0.1137895E+23

Logically, sdn is very unstable with few nodes; with more than 100 million nodes, 1.12e+22 < sdn < 1.14e+22 most of the time.

Considering lower and upper bounds for 95% confidence (z value copied from Wikipedia):

Code: Select all

For 95% confidence level:
z = 1.95996398454
Lower bound = (Average perft estimate) - z*(standard deviation).
Upper bound = (Average perft estimate) + z*(standard deviation).
 
Iteration    Lower bound        Estimate         Upper bound
 
   1        0.2005561E+22     0.2005561E+22     0.2005561E+22
   2        0.1975120E+22     0.1992803E+22     0.2010485E+22
   3        0.1982762E+22     0.2003349E+22     0.2023935E+22
   4        0.1981529E+22     0.1998796E+22     0.2016062E+22
   5        0.1987416E+22     0.2003535E+22     0.2019655E+22
   6        0.1980561E+22     0.1997640E+22     0.2014719E+22
   7        0.1983721E+22     0.1998430E+22     0.2013139E+22
   8        0.1986271E+22     0.1999224E+22     0.2012176E+22
   9        0.1989124E+22     0.2001205E+22     0.2013286E+22

[...]

2430        0.2014238E+22     0.2015238E+22     0.2016239E+22
2431        0.2014239E+22     0.2015239E+22     0.2016239E+22
2432        0.2014239E+22     0.2015239E+22     0.2016238E+22
2433        0.2014242E+22     0.2015241E+22     0.2016240E+22
2434        0.2014252E+22     0.2015250E+22     0.2016249E+22
2435        0.2014248E+22     0.2015246E+22     0.2016245E+22
2436        0.2014247E+22     0.2015245E+22     0.2016243E+22
2437        0.2014261E+22     0.2015259E+22     0.2016257E+22
2438        0.2014257E+22     0.2015255E+22     0.2016252E+22
2439        0.2014261E+22     0.2015258E+22     0.2016255E+22

The narrowing of the interval (upper bound) - (lower bound) is slow (it should be proportional to 1/sqrt(nodes) more less). Sorry for the ugly output from Fortran.

Disgracefully the run automatically stops when it reaches 500 million nodes. Anyway, this MonteCarlo run seems consistent with others.

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hello again:

I ran a long Perft(15) UCT estimate using Nebiyu 1.42 yesterday. I stopped Nebiyu after a little more than four hours in an Intel i5-760 at 2.8 GHz:

Code: Select all

[...]

=========Cycles 76500000 : Total nodes 421 ==========
0 h2h3   5.237601e+019 +- 4.234275e+016   1987228 | 5.235153e+019 +- 4.145165e+016   1987228 |        20
0 h2h4   8.166043e+019 +- 4.968445e+016   3101158 | 8.169691e+019 +- 4.982203e+016   3101158 |        20
0 g2g3   7.536394e+019 +- 4.643026e+016   2857801 | 7.528591e+019 +- 4.604559e+016   2857801 |        20
0 g2g4   6.307673e+019 +- 3.978412e+016   2396443 | 6.313190e+019 +- 3.996890e+016   2396443 |        20
0 f2f3   3.966320e+019 +- 3.085606e+016   1505978 | 3.967349e+019 +- 3.082885e+016   1505978 |        20
0 f2f4   5.901920e+019 +- 4.222674e+016   2242204 | 5.906862e+019 +- 4.213778e+016   2242204 |        20
0 e2e3   2.559381e+020 +- 8.177559e+016   9710498 | 2.558133e+020 +- 8.182872e+016   9710498 |        20
0 e2e4   2.633475e+020 +- 8.047917e+016   9994474 | 2.632944e+020 +- 8.046332e+016   9994474 |        20
0 d2d3   1.413029e+020 +- 5.185528e+016   5358993 | 1.411773e+020 +- 5.178359e+016   5358993 |        20
0 d2d4   2.288858e+020 +- 7.683928e+016   8685891 | 2.288211e+020 +- 7.684760e+016   8685891 |        20
0 c2c3   8.526175e+019 +- 4.657653e+016   3238596 | 8.531754e+019 +- 4.656293e+016   3238596 |        20
0 c2c4   9.880043e+019 +- 4.804009e+016   3751557 | 9.883098e+019 +- 4.810574e+016   3751557 |        20
0 b2b3   7.166490e+019 +- 4.829699e+016   2717197 | 7.158181e+019 +- 4.813501e+016   2717197 |        20
0 b2b4   7.265866e+019 +- 4.710659e+016   2763166 | 7.279284e+019 +- 4.756332e+016   2763166 |        20
0 a2a3   5.313903e+019 +- 4.339429e+016   2012687 | 5.302220e+019 +- 4.262906e+016   2012687 |        20
0 a2a4   7.979521e+019 +- 4.995543e+016   3027778 | 7.976376e+019 +- 4.998602e+016   3027778 |        20
0 g1h3   6.395862e+019 +- 4.403482e+016   2424533 | 6.387190e+019 +- 4.381285e+016   2424533 |        20
0 g1f3   8.191261e+019 +- 4.335729e+016   3108517 | 8.189073e+019 +- 4.350337e+016   3108517 |        20
0 b1c3   8.499089e+019 +- 5.483502e+016   3229863 | 8.508747e+019 +- 5.512561e+016   3229863 |        20
0 b1a3   6.266282e+019 +- 4.454163e+016   2385457 | 6.284245e+019 +- 4.483518e+016   2385457 |        20
Perft 2.015479e+021 +- 2.339013e+017  2.015316e+021 +- 2.337521e+017
2.015479e+021 +- 2.338939e+017  2.015317e+021 +- 2.337445e+017 3823739901 1.446e+022
2.015476e+021 +- 2.338854e+017  2.015319e+021 +- 2.337377e+017 3823989810 1.446e+022
2.015477e+021 +- 2.338777e+017  2.015319e+021 +- 2.337300e+017 3824239714 1.446e+022
2.015476e+021 +- 2.338702e+017  2.015318e+021 +- 2.337221e+017 3824489603 1.446e+022
2.015478e+021 +- 2.338629e+017  2.015319e+021 +- 2.337155e+017 3824739433 1.446e+022

I am not sure about all the numbers but it seems that the number of visited nodes where almost 3825 million, while the number of cycles for make the last estimate were 76.5 million. Please correct me if I am wrong.

Taking a look to the last line: if I suppose that numbers preceded by '+-' are one standard deviations, then for 95% confidence I obtain more less:

Code: Select all

(2.015478 ± 0.000458)e+21 ~ ]2.015020e+21, 2.015936e+21[
(2.015319 ± 0.000458)e+21 ~ ]2.014861e+21, 2.015777e+21[

These UCT estimates are in line with other estimates in this thread, as expected.

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hello:

I used 11277 iterations of my old method with 6 full-width plys. This corresponds to approximately 1.34e12 random walks. The result is:

Code: Select all

mean  : 2.0150985437710440e+21
stddev: 0.0000017422002093e+21

I follow the approach of Peter and I run several MonteCarlo samples. I use Nebiyu 1.42 w32 and its command perftmc this time. I use seed 0 (seconds since 1970) before running each sample.

I want to correct an error in that thread: I calculated wrongly the resultant standard deviations (the correct formula is here, equation 22), so the correct standard variations those MC samples in that thread should be more less the numbers I reported divided by sqrt(samples). Sorry for the inconvenience.

Now I weight each sample using the factor (nodes)/[Σ(nodes)] for each sample; in the practice, this factor is more less 1/N, where N is the number of samples.

I have ran 200 MC samples. I know that it is not a high number but running a MC sample is expensive to me in terms of elapsed time (I started on May, 21st or May, 22nd IIRC). Here are the averaged results after 200 MC samples:

Code: Select all

200 MonteCarlo samples for Perft(15), done with Nebiyu 1.42 w32:
 
Minimum value: 0.2013608E+22
Maximum value: 0.2016398E+22
 
----------------------------------------------
 
<µ> ~ 2015150780145183584400.0 ~ 0.2015151E+22
<σ> ~      36079394823706779.5 ~ 0.3607939E+17
 
----------------------------------------------------------------------------
 
Averaged value of a single standard deviation of a single MonteCarlo sample:
 
 
 
 
        sqrt{Σ[(nodes*σ²]}
s_200 ~ __________________ ~ 510239697369906955.5 ~ 0.5102397E+18
          sqrt[Σ(nodes)]
 
 
 
 
This result is very similar to <σ>*[sqrt(200)]:
 
s = <σ>*[sqrt(200)] ~ 510239694818997720.3 ~ 0.5102397E+18
 
(s_200)/s - 1 ~ 1/(200022677.3) ~ 0.4999433E-08
 
----------------------------------------------------------
 
|z| ~ 1.95996398454 for a confidence level of 95%:
 
<µ> - |z|*<σ> ~ 2015080065830745120100.0 ~ 0.2015080E+22
<µ> + |z|*<σ> ~ 2015221494459622048700.0 ~ 0.2015221E+22
 
--------------------------------------------------------
 
|z| ~ 2.575829303549 for a confidence level of 99%:
 
<µ> - |z|*<σ> ~ 2015057845782742366400.0 ~ 0.2015058E+22
<µ> + |z|*<σ> ~ 2015243714507624802400.0 ~ 0.2015244E+22

Sorry for the ugly, raw Fortran output. I hope no typos.

My results do not differ so much with Peter's ones, but of course his standard deviation is unreachable for me! Furthermore, his method is more efficient: <σ>*sqrt[Σ(nodes)] ~ 1.7422e+15 * sqrt(1.34e+12) < 2.02e+21, while in my case <σ>*sqrt[Σ(nodes)] > 1.14e+22. I think that GNU 5.50 w32 will bring smaller standard deviations than Nebiyu 1.42 and the elapsed time for a single MC sample is almost the same with both engines, but I choosed Nebiyu this time for the possibility of record the results and the automatic stop after 500 million nodes more less. I lost dozens of MC samples with GNU in the past because I forgot that these samples kept running, so this time I prefer to sacrifice a lower standard deviation in favour of not lose any samples, which translates into a waste of time for other samples.

I will try to raise the number of MC samples for lowering <σ>, but the pace will slow down during the summer. I do not promise anything.

Regards from Spain.

Ajedrecista.

[Daniel Shawul]

Hi Jesus,
You should probably use Nebiyu 1.45 as I have fixed the maximum 500 million nodes issue that you previously had problems with. But you can specify the number of nodes you want to search by 'nodes' command when you are comparing algorithms. I do not like comparing in time because one implementation may be poortly implemented. There are are other undocumented settings that you can use to control the perft estimation displays perft-uct, whch lots of verbose if you are only interested in the final result. I think i may have settled on displaying every x milliseconds or so which is possible to do in UCT since you go back to the root quite frequently. The monte-carlo perft OTOH has to wait one full iteration which could be too much for perft(6) for instance. One other feature is that it dumps the tree part of perft-uct in XML format. You can look at it with any xml viewer and get all the estimates of its sub-trees. That was a good tool to debug perft estimations with, but i am not sure if that is controllable from outside.
Daniel

[Ajedrecista]

Hello:

I will try to raise the number of MC samples for lowering <σ>, but the pace will slow down during the summer. I do not promise anything.

I have just reached 500 MonteCarlo estimates, so I leave the results here:

Code: Select all

500 MonteCarlo samples for Perft(15), done with Nebiyu 1.42 w32: 
  
Minimum value: 0.2013608E+22 
Maximum value: 0.2016398E+22 
  
---------------------------------------------- 
  
<µ> ~ 2015102978035254521200.0 ~ 0.2015103E+22
<σ> ~      22810563618756228.2 ~ 0.2281056E+17
  
---------------------------------------------------------------------------- 
  
Averaged value of a single standard deviation of a single MonteCarlo sample: 
  
  
  
  
        sqrt{Σ[(nodes*σ²]} 
s_500 ~ __________________ ~ 510059708698538517.3 ~ 0.5100597E+18 
          sqrt[Σ(nodes)] 
  
  
  
  
This result is very similar to <σ>*[sqrt(500)]: 
  
s = <σ>*[sqrt(500)] ~ 510059708566225229.0 ~ 0.5100597E+18
  
(s_500)/s - 1 ~ 1/(3854939403.7) ~ 0.2594074E-09
  
---------------------------------------------------------- 
  
|z| ~ 1.95996398454 for a confidence level of 95%: 
  
<µ> - |z|*<σ> ~ 2015058270152094700600.0 ~ 0.2015058E+22
<µ> + |z|*<σ> ~ 2015147685918414341900.0 ~ 0.2015148E+22
  
-------------------------------------------------------- 
  
|z| ~ 2.575829303549 for a confidence level of 99%: 
  
<µ> - |z|*<σ> ~ 2015044221917054860200.0 ~ 0.2015044E+22
<µ> + |z|*<σ> ~ 2015161734153454182300.0 ~ 0.2015162E+22

-------------------------------------------------------- 

               n(µ < 0.20139E+22) =   4 ( 0.80 %)
n(0.20139E+22 =< µ < 0.20141E+22) =   9 ( 1.80 %)
n(0.20141E+22 =< µ < 0.20143E+22) =  15 ( 3.00 %)
n(0.20143E+22 =< µ < 0.20145E+22) =  40 ( 8.00 %)
n(0.20145E+22 =< µ < 0.20147E+22) =  35 ( 7.00 %)
n(0.20147E+22 =< µ < 0.20149E+22) =  55 (11.00 %)
n(0.20149E+22 =< µ < 0.20151E+22) =  83 (16.60 %)
n(0.20151E+22 =< µ < 0.20153E+22) =  77 (15.40 %)
n(0.20153E+22 =< µ < 0.20155E+22) =  83 (16.60 %)
n(0.20155E+22 =< µ < 0.20157E+22) =  51 (10.20 %)
n(0.20157E+22 =< µ < 0.20159E+22) =  23 ( 4.60 %)
n(0.20159E+22 =< µ < 0.20161E+22) =  16 ( 3.20 %)
n(0.20161E+22 =< µ < 0.20163E+22) =   7 ( 1.40 %)
              n(µ >= 0.20163E+22) =   2 ( 0.40 %)
                                    ---
                                    500

As a bonus, I give intermediate results after each 50 MC samples:

Code: Select all

N =  50: <µ> ~ 2.015158e+21; <σ> ~ 7.197400e+16
N = 100: <µ> ~ 2.015164e+21; <σ> ~ 5.101032e+16
N = 150: <µ> ~ 2.015167e+21; <σ> ~ 4.163927e+16
N = 200: <µ> ~ 2.015151e+21; <σ> ~ 3.607939e+16
N = 250: <µ> ~ 2.015122e+21; <σ> ~ 3.228897e+16
N = 300: <µ> ~ 2.015111e+21; <σ> ~ 2.947578e+16
N = 350: <µ> ~ 2.015104e+21; <σ> ~ 2.728343e+16
N = 400: <µ> ~ 2.015102e+21; <σ> ~ 2.550291e+16
N = 450: <µ> ~ 2.015104e+21; <σ> ~ 2.404604e+16
N = 500: <µ> ~ 2.015103e+21; <σ> ~ 2.281056e+16

Please note two things:

- The similarity of the mean with Peter's result.
- The apparent stability of the mean since N = 350.

I will try to increase the number of samples but I do not promise anything.

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hello:

I will try to increase the number of samples but I do not promise anything.

I reached 800 MC samples yesterday (almost two months for 300 new MC samples) and I think I will stop here.

Code: Select all

800 MonteCarlo samples for Perft(15), done with Nebiyu 1.42 w32: 
  
Minimum value: 2.013478E+21
Maximum value: 2.016704E+21

---------------------------------------------

<µ> ~ 2015107631301193211900.0 ~ 2.015108E+21
<σ> ~      18031760188265340.7 ~ 1.803176E+16

----------------------------------------------------------------------------

Averaged value of a single standard deviation of a single MonteCarlo sample:




        sqrt{Σ[(nodes*σ²]}
s_800 ~ __________________ ~ 510015195982477022.7 ~ 5.100152E+17
          sqrt[Σ(nodes)]




This result is very similar to <σ>*[sqrt(800)]:

s = <σ>*[sqrt(800)] ~ 510015196234081569.1 ~ 5.100152E+17

(s_800)/s - 1 ~ 1/(  -2027050796.6) ~ -4.933275E-10

---------------------------------------------------------

|z| ~ 1.95996398454 for a confidence level of 95%:

<µ> - |z|*<σ> ~ 2015072289700646349600.0 ~ 2.015072E+21
<µ> + |z|*<σ> ~ 2015142972901740074300.0 ~ 2.015143E+21

-------------------------------------------------------

|z| ~ 2.575829303549 for a confidence level of 99%:

<µ> - |z|*<σ> ~ 2015061184564905709800.0 ~ 2.015061E+21
<µ> + |z|*<σ> ~ 2015154078037480714000.0 ~ 2.015154E+21

-------------------------------------------------------

              n(µ < 2.0139E+21) =   8 ( 1.00 %)
n(2.0139E+21 =< µ < 2.0141E+21) =  19 ( 2.38 %)
n(2.0141E+21 =< µ < 2.0143E+21) =  26 ( 3.25 %)
n(2.0143E+21 =< µ < 2.0145E+21) =  57 ( 7.13 %)
n(2.0145E+21 =< µ < 2.0147E+21) =  61 ( 7.63 %)
n(2.0147E+21 =< µ < 2.0149E+21) =  96 (12.00 %)
n(2.0149E+21 =< µ < 2.0151E+21) = 107 (13.38 %)
n(2.0151E+21 =< µ < 2.0153E+21) = 119 (14.88 %)
n(2.0153E+21 =< µ < 2.0155E+21) = 137 (17.13 %)
n(2.0155E+21 =< µ < 2.0157E+21) =  86 (10.75 %)
n(2.0157E+21 =< µ < 2.0159E+21) =  36 ( 4.50 %)
n(2.0159E+21 =< µ < 2.0161E+21) =  29 ( 3.63 %)
n(2.0161E+21 =< µ < 2.0163E+21) =  14 ( 1.75 %)
             n(µ >= 2.0163E+21) =   5 ( 0.63 %)
                                  ---
                                  800

As a bonus, I give intermediate results after each 50 MC samples:

Code: Select all

N =  50: <µ> ~ 2.015158e+21; <σ> ~ 7.197400e+16 
N = 100: <µ> ~ 2.015164e+21; <σ> ~ 5.101032e+16
N = 150: <µ> ~ 2.015167e+21; <σ> ~ 4.163927e+16
N = 200: <µ> ~ 2.015151e+21; <σ> ~ 3.607939e+16
N = 250: <µ> ~ 2.015122e+21; <σ> ~ 3.228897e+16
N = 300: <µ> ~ 2.015111e+21; <σ> ~ 2.947578e+16
N = 350: <µ> ~ 2.015104e+21; <σ> ~ 2.728343e+16
N = 400: <µ> ~ 2.015102e+21; <σ> ~ 2.550291e+16
N = 450: <µ> ~ 2.015104e+21; <σ> ~ 2.404604e+16
N = 500: <µ> ~ 2.015103e+21; <σ> ~ 2.281056e+16
N = 550: <µ> ~ 2.015114e+21; <σ> ~ 2.174943e+16
N = 600: <µ> ~ 2.015113e+21; <σ> ~ 2.082034e+16
N = 650: <µ> ~ 2.015112e+21; <σ> ~ 2.000490e+16
N = 700: <µ> ~ 2.015104e+21; <σ> ~ 1.927415e+16
N = 750: <µ> ~ 2.015106e+21; <σ> ~ 1.862360e+16
N = 800: <µ> ~ 2.015108e+21; <σ> ~ 1.803176e+16

This bunch of simulations are in line with Peter's results, so I can safely say that the first numbers of Perft(15) will be 20150... or 20151... Nothing new at this point.

Regards from Spain.

Ajedrecista.

[Daniel Shawul]

As a side note, Richard Delorme sent me a link to Knuth's paper that uses monte-carlo for estimating cost of backtracking. I will try to update the perft paper with that literature and others when I have time. It currently has no literature review aside from the discussions we had. Here is the link to knuth's "Estimating efficiency of backtrack programs" ftp://reports.stanford.edu/www/pub/publ ... 74-442.pdf

[Daniel Shawul]

Hi Jesus,
I see you are still using 1.42. I think 1.45 is better and the older version may even have a bug with stalemate counting or something that I forgot about. It probably doesn't make much difference but you should use >=1.44 or above for your future tests.
Cheers

[Ajedrecista]

Hello Daniel:

Hi Jesus,
I see you are still using 1.42. I think 1.45 is better and the older version may even have a bug with stalemate counting or something that I forgot about. It probably doesn't make much difference but you should use >=1.44 or above for your future tests.
Cheers

I am aware that Nebiyu 1.45 exists; by the way, I only use Nebiyu for perft estimating purposes (mainly chess and checkers). I guess that the perft estimates obtained with version 1.42 are not heavily biased with respect to the case if I will use version 1.45. The next perft estimate that makes sense is Perft(16) but it is too far in the horizon and I assume that better versions of Nebiyu will be available if I have some interest in running those future estimates.

Anyway, thanks for the reminder. Good luck with the update of your paper!

Regards from Spain.

Ajedrecista.

[petero2]

As a side note, Richard Delorme sent me a link to Knuth's paper that uses monte-carlo for estimating cost of backtracking. I will try to update the perft paper with that literature and others when I have time. It currently has no literature review aside from the discussions we had. Here is the link to knuth's "Estimating efficiency of backtrack programs" ftp://reports.stanford.edu/www/pub/publ ... 74-442.pdf

Very interesting. So it turns out that the Monte Carlo part of my algorithm from 2011 is in fact just a special case (corollary 1, page 12) of a procedure that Knuth worked out in 1962. The full width part of my algorithm is covered by his "stratified sampling" comment on page 21.

This means I didn't invent anything new in that algorithm, I just re-invented something old.