Perft(15) estimates thread
Moderators: hgm, Dann Corbit, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

 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 montecarlo 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 ... 74442.pdf

 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
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
 Location: Madrid, Spain.
 Contact:
Re: Perft(15) estimate after averaging 800 MC samples.
Hello Daniel:
Anyway, thanks for the reminder. Good luck with the update of your paper!
Regards from Spain.
Ajedrecista.
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.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
Anyway, thanks for the reminder. Good luck with the update of your paper!
Regards from Spain.
Ajedrecista.
Re: Perft(15) estimate after averaging 800 MC samples.
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.Daniel Shawul wrote:As a side note, Richard Delorme sent me a link to Knuth's paper that uses montecarlo 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 ... 74442.pdf
This means I didn't invent anything new in that algorithm, I just reinvented something old.

 Posts: 4073
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: Perft(15) estimate after averaging 800 MC samples.
Well I noted the well known stratified sampling concept in my paper too which I, and possibly all of us, learned postmortem (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 montecarlo 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 montecarlo papers.petero2 wrote: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.Daniel Shawul wrote:As a side note, Richard Delorme sent me a link to Knuth's paper that uses montecarlo 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 ... 74442.pdf
This means I didn't invent anything new in that algorithm, I just reinvented something old.
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 fellaAmong the different methods that came into light during the competition, the montecarlo 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 montecarlo estimation. Further investigation as to the first use of montecarlo methods for estimating perft has not been done, but we suspect it maybe quite old since it is a simple application of original montecarlo 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\%.