Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Daniel Shawul
Posts: 4073
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

### Re: Perft(15) estimate after averaging 800 MC samples.

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
Posts: 4073
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

### Re: Perft(15) estimate after averaging 800 MC samples.

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
Posts: 1517
Joined: Wed Jul 13, 2011 7:04 pm
Contact:

### Re: Perft(15) estimate after averaging 800 MC samples.

Hello Daniel:
Daniel Shawul wrote: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
Posts: 612
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

### Re: Perft(15) estimate after averaging 800 MC samples.

Daniel Shawul wrote: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.

Daniel Shawul
Posts: 4073
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

### Re: Perft(15) estimate after averaging 800 MC samples.

petero2 wrote:
Daniel Shawul wrote: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.
Well I noted the well known stratified sampling concept in my paper too which I, and possibly all of us, learned post-mortem (i.e. proportioning by standard deviation. see page 17). Michel derived it during that competition but for others it may be so obvious as it is even stated in wikipedia! As to history of monte-carlo perft estimation, I was sure it goes back a long way but I abruptly stopped at Labelle(2007). I just didn't bother to do literature review at the time. It may even go back further than that since his references seem to have many monte-carlo papers.
Among the different methods that came into light during the competition, the monte-carlo methods were clear winners. Clearly these methods have been used in the past for computing perft estimates. \citet{francois} used what he called "random pruning" method to compute estimates of perft(13) through perft(20). The details of his method are not available, but the basic idea seems to be of monte-carlo estimation. Further investigation as to the first use of monte-carlo methods for estimating perft has not been done, but we suspect it maybe quite old since it is a simple application of original monte-carlo method proposed in the 1940s \citep{roger}. However estimating perft by other means is certainly not a recent effort. \citet{anthony} mentions an estimate for perft(8) which is now proven to be off by 275\%.
So Knuth's paper basically extends this literature one step back which I stoped at Labelle. Anyway the addition of tree growth, and all those variance reduction techniques are still ours but you can't mess with this Knuth fella