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
