Perft(15) estimates thread

[Daniel Shawul]

It is weird but for the default policy i am getting proportioning by mean is the best?! I also used Lagrange multiplier to arrive at that and it seems standard deviation has no effect to the selection when used in the monte carlo part. I very much doubt this will hold but what i have right now is
Tree policy:

Code: Select all

p_i = mu sd_i

Default policy:

Code: Select all

p_i = mu X_i

The simplicity will be beautiful if it holds. Your formula that says

Code: Select all

p_i = mu sqrt(X_i^2 + sd_i^2)

is a combinaion of the above two. I will give the details later. But it would be great if you do it too.

Cheers

[Daniel Shawul]

Here is how i arrived at it. It is most probable that i made a mistake but i want to get to the bottom of it.
[/img]

[petero2]

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

[Gerd Isenberg]

I have added interesting stuff to the Document for your reading pleasure I went philosophical on it in section 2.3, which may be a bit overboard. I have also added a review of the selection formula that i talked about in this thread. Hope you enjoy it as I do.

Thanks, great paper! I will incorporate some your research in cpw, which states Bob Hyatt introduced Perft in Cray Blitz. Along with Franklin D. Ceruti, Rolf C. Smith is co-author of the early program Schach which played ACM 71, 72, and 73.

[Daniel Shawul]

I have added interesting stuff to the Document for your reading pleasure I went philosophical on it in section 2.3, which may be a bit overboard. I have also added a review of the selection formula that i talked about in this thread. Hope you enjoy it as I do.

Thanks, great paper! I will incorporate some your research in cpw, which states Bob Hyatt introduced Perft in Cray Blitz. Along with Franklin D. Ceruti, Rolf C. Smith is co-author of the early program Schach which played ACM 71, 72, and 73.

Thanks Gerd for the encouragement. I barely know of the history of perft so I wrote down what Steven fed me in this thread. You would think anyone who had a chess program in the early 70s may have done perft(3). So it is good to know that R C. Smith is one of the authors. I mentioned Ken Thosmpson compute peft(4) based on a word of mouth.
Cheers

[Gerd Isenberg]

I have added interesting stuff to the Document for your reading pleasure I went philosophical on it in section 2.3, which may be a bit overboard. I have also added a review of the selection formula that i talked about in this thread. Hope you enjoy it as I do.

Thanks, great paper! I will incorporate some your research in cpw, which states Bob Hyatt introduced Perft in Cray Blitz. Along with Franklin D. Ceruti, Rolf C. Smith is co-author of the early program Schach which played ACM 71, 72, and 73.

Thanks Gerd for the encouragement. I barely know of the history of perft so I wrote down what Steven fed me in this thread. You would think anyone who had a chess program in the early 70s may have done perft(3). So it is good to know that R C. Smith is one of the authors. I mentioned Ken Thosmpson compute peft(4) based on a word of mouth.
Cheers

Ahh yes, I now remember "R. Smith's Chess Explorer" mentioned by Steven some time ago, already referred on the cpw Perft page, but "forgotten" to elaborate more on it.

[Daniel Shawul]

Well after 2 years I think i may have solved the problem with why I needed to use 2 sequence of random numbers. I am now running with a single sequence with all selection methods. The problem was the geometric distribution which had to be averaged to sort of change it in to a normal distribution. If on there is no smooth transition between the tree and monte-carlo part, one would feel the wrath of the variance coming from the distribution!! If the last ply uses uniform selection, the results from 20 or so moves are summed, everything will be back to normal (no pun) while using non-uniform selection everywhere else. I confirmed this with an artificial tree that just multiplies random numbers and returns as a result , it had the same problem even if the transition ply uses non-uniform allocation. Using any other distribution it will have no problem even without that. Decreaseing variance of the branching factors helps, so i now know where exactly that problem is coming. The conclusion is we can make selection with the same data in the tree, and the problem we had was just due to an unfortunate distribution with a very big variance i.e. log-normal. That is a satisfactory conclusion i arrived at , even though it took 2 years...

After this revelation , things becomes like a "sixth sense" phenomenon. Every weird behavior i observed in the past had suddenly a reason to it.

*second sequence just selects other moves at the shallow depth making it more uniform

*uniform and sub-tree selection had no problems because well all moves are selected equally on the last layer

*dynamic tree expansion was not much of a success, well because new nodes means new problems! The variance will be big again. I guess it is time to experiment with this with renewed hope.

*increasing width of the artificial tree helps solve this problem

*The problem was less severe when ply<=2 due to more or less uniform selection

etc..

Daniel

[sje]

For all the recent perft(n) calculations for n < 14, the 20 secondary perft(n - 1) and the 400 tertiary perft(n - 2) sums are available. My suggestion is to use these statistics for test data to help tune perft estimation strategies. It took some time to calculate all of these values, so we might as well put them to use.

[Daniel Shawul]

Oh yes that is something i forgot to do! IIRC you have up to perft(8) data, when you did perft(13) so that means i can use all of them to guide the perft estimation. Weights for fwd=5 are more than enough. In fact i don't think there is enough memory to store all perft(6) positions, so this is just perfect. This might take me some time, as i have now a pretty long list of todos even for perft. But i will definitely try it.

Daniel

[Ajedrecista]

Hello Peter:

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 ran a long MonteCarlo perft estimate (10000 seconds) on Tuesday using GNU Chess 5.50 w32. Here are the last results:

Code: Select all

[...]
m=2.015024e+021 sd=1.714903e+017 ci(99%)=[2.014583e+021,2.015466e+021] n=-1273525828 sdn=9.426418e+021 t=9845.39s
m=2.015022e+021 sd=1.713825e+017 ci(99%)=[2.014580e+021,2.015463e+021] n=-1271347476 sdn=9.423886e+021 t=9852.42s
m=2.015016e+021 sd=1.713506e+017 ci(99%)=[2.014575e+021,2.015458e+021] n=-1269169139 sdn=9.425527e+021 t=9859.48s
m=2.015012e+021 sd=1.712794e+017 ci(99%)=[2.014571e+021,2.015453e+021] n=-1266990705 sdn=9.425000e+021 t=9866.50s
m=2.015009e+021 sd=1.711782e+017 ci(99%)=[2.014568e+021,2.015450e+021] n=-1264812292 sdn=9.422817e+021 t=9873.53s
m=2.015014e+021 sd=1.711091e+017 ci(99%)=[2.014573e+021,2.015454e+021] n=-1262633887 sdn=9.422399e+021 t=9880.58s
m=2.015021e+021 sd=1.711262e+017 ci(99%)=[2.014580e+021,2.015461e+021] n=-1260455538 sdn=9.426729e+021 t=9887.63s
m=2.015015e+021 sd=1.710837e+017 ci(99%)=[2.014575e+021,2.015456e+021] n=-1258277180 sdn=9.427770e+021 t=9894.64s
m=2.015016e+021 sd=1.709641e+017 ci(99%)=[2.014576e+021,2.015457e+021] n=-1256098833 sdn=9.424554e+021 t=9901.64s
m=2.015013e+021 sd=1.708709e+017 ci(99%)=[2.014573e+021,2.015453e+021] n=-1253920309 sdn=9.422792e+021 t=9908.64s
m=2.015015e+021 sd=1.707563e+017 ci(99%)=[2.014575e+021,2.015455e+021] n=-1251741841 sdn=9.419847e+021 t=9915.63s
m=2.015015e+021 sd=1.706342e+017 ci(99%)=[2.014575e+021,2.015454e+021] n=-1249563514 sdn=9.416479e+021 t=9922.61s
m=2.015016e+021 sd=1.705156e+017 ci(99%)=[2.014576e+021,2.015455e+021] n=-1247385157 sdn=9.413297e+021 t=9929.63s
m=2.015013e+021 sd=1.704116e+017 ci(99%)=[2.014574e+021,2.015452e+021] n=-1245206749 sdn=9.410920e+021 t=9936.64s
m=2.015014e+021 sd=1.702903e+017 ci(99%)=[2.014575e+021,2.015452e+021] n=-1243028337 sdn=9.407578e+021 t=9943.64s
m=2.015013e+021 sd=1.701700e+017 ci(99%)=[2.014575e+021,2.015451e+021] n=-1240850039 sdn=9.404286e+021 t=9950.69s
m=2.015002e+021 sd=1.704348e+017 ci(99%)=[2.014562e+021,2.015441e+021] n=-1238671584 sdn=9.422278e+021 t=9957.73s
m=2.014997e+021 sd=1.703701e+017 ci(99%)=[2.014558e+021,2.015436e+021] n=-1236493131 sdn=9.422059e+021 t=9964.77s
m=2.014998e+021 sd=1.702522e+017 ci(99%)=[2.014560e+021,2.015437e+021] n=-1234314836 sdn=9.418891e+021 t=9971.77s
m=2.014999e+021 sd=1.701317e+017 ci(99%)=[2.014560e+021,2.015437e+021] n=-1232136363 sdn=9.415571e+021 t=9978.81s
m=2.014997e+021 sd=1.700158e+017 ci(99%)=[2.014559e+021,2.015435e+021] n=-1229957920 sdn=9.412503e+021 t=9985.83s
m=2.014994e+021 sd=1.699335e+017 ci(99%)=[2.014556e+021,2.015431e+021] n=-1227779569 sdn=9.411290e+021 t=9992.84s
m=2.014998e+021 sd=1.698785e+017 ci(99%)=[2.014561e+021,2.015436e+021] n=-1225601128 sdn=9.411587e+021 t=9999.84s

Interrupted!

The confidence interval for 99% confidence is somewhat similar to yours (just taking a look to your distribution and the bounds estimated by GNU Chess).

I observed that n (n are the number of visited nodes?) became negative at some point. Knowing that sdn = sd*sqrt(n), it took me few time to realize that n restarts from -2^(31) instead of print 2^(31). I guess that this 32-bit integer n has these bounds: -2^(31) < n < 2^(31) - 1; that is, [2^(31) - 1] - [-2^(31)] + 1 = 2^(32) possible integers. If I call n_0 the true number of nodes, when n reaches 2^(31) k times (k > 0), then n_0 = k*2^(32) + n. Sorry for this evident, well-known explanation. In this MonteCarlo Perft run, k = 1. I correct the numbers for a nicer read:

Code: Select all

[...]
m=2.015024e+021 sd=1.714903e+017 ci(99%)=[2.014583e+021,2.015466e+021] n=3021441468 sdn=9.426418e+021 t=9845.39s
m=2.015022e+021 sd=1.713825e+017 ci(99%)=[2.014580e+021,2.015463e+021] n=3023619820 sdn=9.423886e+021 t=9852.42s
m=2.015016e+021 sd=1.713506e+017 ci(99%)=[2.014575e+021,2.015458e+021] n=3025798157 sdn=9.425527e+021 t=9859.48s
m=2.015012e+021 sd=1.712794e+017 ci(99%)=[2.014571e+021,2.015453e+021] n=3027976591 sdn=9.425000e+021 t=9866.50s
m=2.015009e+021 sd=1.711782e+017 ci(99%)=[2.014568e+021,2.015450e+021] n=3030155004 sdn=9.422817e+021 t=9873.53s
m=2.015014e+021 sd=1.711091e+017 ci(99%)=[2.014573e+021,2.015454e+021] n=3032333409 sdn=9.422399e+021 t=9880.58s
m=2.015021e+021 sd=1.711262e+017 ci(99%)=[2.014580e+021,2.015461e+021] n=3034511758 sdn=9.426729e+021 t=9887.63s
m=2.015015e+021 sd=1.710837e+017 ci(99%)=[2.014575e+021,2.015456e+021] n=3036690116 sdn=9.427770e+021 t=9894.64s
m=2.015016e+021 sd=1.709641e+017 ci(99%)=[2.014576e+021,2.015457e+021] n=3038868463 sdn=9.424554e+021 t=9901.64s
m=2.015013e+021 sd=1.708709e+017 ci(99%)=[2.014573e+021,2.015453e+021] n=3041046987 sdn=9.422792e+021 t=9908.64s
m=2.015015e+021 sd=1.707563e+017 ci(99%)=[2.014575e+021,2.015455e+021] n=3043225455 sdn=9.419847e+021 t=9915.63s
m=2.015015e+021 sd=1.706342e+017 ci(99%)=[2.014575e+021,2.015454e+021] n=3045403782 sdn=9.416479e+021 t=9922.61s
m=2.015016e+021 sd=1.705156e+017 ci(99%)=[2.014576e+021,2.015455e+021] n=3047582139 sdn=9.413297e+021 t=9929.63s
m=2.015013e+021 sd=1.704116e+017 ci(99%)=[2.014574e+021,2.015452e+021] n=3049760547 sdn=9.410920e+021 t=9936.64s
m=2.015014e+021 sd=1.702903e+017 ci(99%)=[2.014575e+021,2.015452e+021] n=3051938959 sdn=9.407578e+021 t=9943.64s
m=2.015013e+021 sd=1.701700e+017 ci(99%)=[2.014575e+021,2.015451e+021] n=3054117257 sdn=9.404286e+021 t=9950.69s
m=2.015002e+021 sd=1.704348e+017 ci(99%)=[2.014562e+021,2.015441e+021] n=3056295712 sdn=9.422278e+021 t=9957.73s
m=2.014997e+021 sd=1.703701e+017 ci(99%)=[2.014558e+021,2.015436e+021] n=3058474165 sdn=9.422059e+021 t=9964.77s
m=2.014998e+021 sd=1.702522e+017 ci(99%)=[2.014560e+021,2.015437e+021] n=3060652460 sdn=9.418891e+021 t=9971.77s
m=2.014999e+021 sd=1.701317e+017 ci(99%)=[2.014560e+021,2.015437e+021] n=3062830933 sdn=9.415571e+021 t=9978.81s
m=2.014997e+021 sd=1.700158e+017 ci(99%)=[2.014559e+021,2.015435e+021] n=3065009376 sdn=9.412503e+021 t=9985.83s
m=2.014994e+021 sd=1.699335e+017 ci(99%)=[2.014556e+021,2.015431e+021] n=3067187727 sdn=9.411290e+021 t=9992.84s
m=2.014998e+021 sd=1.698785e+017 ci(99%)=[2.014561e+021,2.015436e+021] n=3069366168 sdn=9.411587e+021 t=9999.84s

Interrupted!

Ideally, I would want to run a MonteCarlo Perft for days or even weeks, but those 10000 seconds are the most I can do. Anyway, it is better than nothing!

Regards from Spain.

Ajedrecista.