Perft(15) estimates thread

[Daniel Shawul]

@Steven, Do you have a some kind of article on your work that I can cite?

Not really. I started doing movepath enumeration (my name for perft) more than thirty years ago as a part of program verification. My early work and later additions by myself and others appear at http://oeis.org/A048987 (which also lists a truly ancient email address of mine).

Thanks. I will directly cite that specific page instead of giving a general link to integer-sequences.

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

[Ajedrecista]

Hello:

I have done some numbers today, adapting my strange method for estimate Perft(15) now. I will not bother you with all the numbers this time, but I obtain this number:

Code: Select all

[My Perft(15) estimate] = 2,015,977,411,404,673,313,379

I know that it can be ridiculous giving all the numbers up to units and also do not have standard deviations or things like these... well, my method is dubious at least. I hope I did not get wrong when doing the math with the simple help of Windows calculator!

I see that François Labelle's estimate for Perft(15) is 2.015e+21 more less. Our differences are really tiny! Not bad at all.

Regards from Spain.

Ajedrecista.

[smrf]

Based on my old calculating scheme - but still ignoring the latest Perft(14) result - here is my estimate:

Perft(15) ≈ 2.01533e21

[smrf]

[Michel]

Hi,

Even though it is a nice mathematical gadget which perhaps has other applications, I got disillusioned with the optimal proportioning method for perft since, as far as I recall, no clear benefit has been demonstrated from it. Perhaps proportioning works asymptotically but the naive method of doing a full width search up to some depth N and then doing a naive Monte Carlo with uniform probabilities at the leaves (Peter Osterlund's original approach) is so efficient that it seems hard to overcome. Instead of putting CPU resources into gathering statistics one can just increase N, which was more effective in my testing.

This being said, if you believe in optimal proportioning, you definitely want p_i to depend on (an estimate of) the parameter x_i.

Imaging that X_i has zero variance (thus X_i=x_i). Then X_1+...+X_n is an estimator for x_1+...+x_n with zero variance. One the other hand doing uniform selection would give you an estimator for x_1+...+x_n with non-zero variance due to differences among the x_i.

Letting the p_i depend on the x_i cures this problem (in this case p_i=x_i/(x_1+...+x_n) and X_i should be counted as X_i/p_i=x_1+...+x_n).

Of course this is a completely degenerate example. It is just to make the point.

Also recall that my formula was confirmed by HGM.

[Daniel Shawul]

Hi Michel
Thanks for taking the time to reply and i hope you hang around this thread when you have time. I am trying to single out all the issues that were causing confusion at the time and there definitely are many. It seems to me we were looking at things from different perspectives and there may not have been any difference with our approaches eventually. I want to go through stuff really really slowly to make sure nothing is missed this time.

Ok let me just say that I haven't summarized HG's and Peter's monte carlo methods _yet_. What I have looked at so far is in tree selection policy. Please look at this Document starting from section 2.4 if you haven't already done so. First int section 2.4.1 I give your proof of 'proportioning by standard devition' is the best which i now completely _agree_ with. Then in 2.4.2 I give my best performing formula that i derived from maximal variance reduction. In 2.4.3 I convert your formula to a 'selection' algorithm and test it against mine with mine using matlab code. They both give the same sequences so they are basically the same eventhough we didn't understand it at the time. Please let me know if you see a flow in my reasoning there.

Now what i am not sure of is your other formula that has the mean in it. I am sure you,HG and Peter all agre with it but I need time to grasp things from your perspectives. Simple I was looking at things from different perspectives and I need time to analyze it to avoid confusions. There are differences of perft with othe monte-carlo search methods that could easily lead one astray so I want to take maximal caution. I will look at your reply here and study all those posts two years ago and make a summary so that you can check if make a mistake understanding things from your perspective. I just don't want this thread to end up like that one.

Cheers

[Daniel Shawul]

Ok here is what I got from your comments. You basically have two different formulas one to be used as in the tree (tree policy) and the other in the monte-carlo part (default policy)

Tree policy:
---------------------
p_i = mu * sd_i
This is the same as my approach that selects the the largest reduction in variance. Here we always have the mean estimates of each move so we always do X_1+X_2+...+X_n with no weights to get the perft estimate. That is what the case for me and also others who use depth-first perft estimation without storing the tree. The weights p_i are used to proportion the visits for maximal variance reduction, and not to multiply (1/p_i)*X_i as is done in the monte-carlo part below.
---------------------
Default policy
-----------------------
p_i = mu * sqrt(mean_i^2 + sd_i^2)
This is to be used in the monte-carlo part where we estimate the perft of the root node by (1/p_i)*X_i. So according to the 'degenerate' example you gave , even if the estimate X_i has 0 variance, the sum will show some variance. This is solely because we don't store estimates for the other moves as well. If this was in the tree the estimate will also have zero variance since we will use X_1+X_2+...+X_n to estimate it.
-----------------------

Unless you have objections to my interpretations, this solves the confusion i think, and i will write it down.

Daniel

[sje]

@Steven, Do you have a some kind of article on your work that I can cite?

Not really. I started doing movepath enumeration (my name for perft) more than thirty years ago as a part of program verification. My early work and later additions by myself and others appear at http://oeis.org/A048987 (which also lists a truly ancient email address of mine).

Thanks. I will directly cite that specific page instead of giving a general link to integer-sequences.

I seem to recall that long ago (1970s) Ken Thompson did perft(3) and perft(4), possibly as a part of Belle's hardware verification. I think I was the first to do perft(5) through perft(9), all of which were calculated without any transposition assistance. In the second half of 2002 I did perft(10) also without transposition assistance, but by that time I believe someone else had gotten there first.

And don't forget perft(3) done back in 1978 with a Cobol program: http://news.google.com/newspapers?nid=8 ... 80,1080528

[Daniel Shawul]

@Steven, Do you have a some kind of article on your work that I can cite?

Not really. I started doing movepath enumeration (my name for perft) more than thirty years ago as a part of program verification. My early work and later additions by myself and others appear at http://oeis.org/A048987 (which also lists a truly ancient email address of mine).

Thanks. I will directly cite that specific page instead of giving a general link to integer-sequences.

I seem to recall that long ago (1970s) Ken Thompson did perft(3) and perft(4), possibly as a part of Belle's hardware verification. I think I was the first to do perft(5) through perft(9), all of which were calculated without any transposition assistance. In the second half of 2002 I did perft(10) also without transposition assistance, but by that time I believe someone else had gotten there first.

And don't forget perft(3) done back in 1978 with a Cobol program: http://news.google.com/newspapers?nid=8 ... 80,1080528

Ok thanks for the hisorical background. Somehow I can imagine perft(3) could have been computed by hand with pen and paper before computer era. But I understand the excitement in the magazine article about the Cobol program. Indeed it makes sense that Ken must have computed perft(3) for his program since it was the best at its time. It would be great if i can find some written material like the Cobol program to give him full credit.

Sorry I forgot to mention about your computation of peft(5)-perft(9). There is an article by the other guy who computed perft(10) that also mentions you 'posted' those numbers in CCC. I guess he meant to say you computed them first which was why I asked you if you had a an article.

Thanks again.