Usingsje wrote:A test point for the Monte Carlo practitioners:
I don't have perft(13) yet, but I've got parts of it.
[D]r1bqkbnr/pppp1ppp/2n5/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R w KQkq - 2 3
For the above ply 4 position, perft(9) is 23,814,128,415,915.
How well do your approximation algorithms do with this?
a Monte Carlo based method as suggested by HGM and Uri,
with my random walk sampling idea http://talkchess.com/forum/viewtopic.ph ... 43&t=39678
with optimal weights as calculated by Michel http://talkchess.com/forum/viewtopic.ph ... 71&t=39678
with my weight estimation idea http://talkchess.com/forum/viewtopic.ph ... 97&t=39678
and a UCT-like tree growing approach as suggested by Daniel,
I got the following just after the tree had grown to its maximum allowed size of 4M nodes.
Code: Select all
23814128415915 (real value)
23814148433009 (estimated value)
2375181106 (estimated standard deviation)
The estimate is too good to be typical though, as the error is less than 1% of the standard deviation. Therefore I repeated the measurement and got this:
Code: Select all
23814128415915 (real value)
23813936012606 (estimated value)
2372711320 (estimated standard deviation)
I think there is still some more room for improvement, as my current method seems to be learning the optimal sampling weights quite slowly. I have an idea how to make it learn faster, but I'm not sure it will work yet.