Symbolic: First results with whole-tree mate search
I wrote up the Lisp version of the whole-tree mate search algorithm as described in the 2007.04.25 status report and tried it on several problems from BWTC and WAC.
There are a number of bugs in the code and redundancies in the search, to be sure. But it does seem to work. It was able to solve WAC.163 with just a 660 node search, and BWTC.0031 fell after only 130 nodes:
[D] 2qrr1n1/3b1kp1/2pBpn1p/1p2PP2/p2P4/1BP5/P3Q1PP/4RRK1 w - - 0 1
sje wrote:Symbolic: First results with whole-tree mate search
There are a number of bugs in the code and redundancies in the search, to be sure. But it does seem to work. It was able to solve WAC.163 with just a 660 node search, and BWTC.0031 fell after only 130 nodes:
Interesting, my engine bright needs 692k and 132k nodes for these problems.
So, nodewise, your algorithm is 1000x more effective than bright's search, amazing!
What nps do you get?
sje wrote:Symbolic: First results with whole-tree mate search
There are a number of bugs in the code and redundancies in the search, to be sure. But it does seem to work. It was able to solve WAC.163 with just a 660 node search, and BWTC.0031 fell after only 130 nodes:
Interesting, my engine bright needs 692k and 132k nodes for these problems.
So, nodewise, your algorithm is 1000x more effective than bright's search, amazing!
What nps do you get?
I think that you cannot decide that his algorithm is 1000x more effective based on tactical problems.
There are search ideas that are productive for test suites but counter productive for positions when there is no tactics to solve.
pruning based on static evaluation when the remaining depth is small is productive for playing strength but counter productive for finding sacrifices.
Allard Siemelink wrote:Interesting, my engine bright needs 692k and 132k nodes for these problems.
So, nodewise, your algorithm is 1000x more effective than bright's search, amazing!
What nps do you get?
Node frequency ranges from the tens to hundreds per second.
Oh, and the WAC.163 (a mate in eleven) took 662 nodes, not 660.
More comments on the first results of Symbolic's mate search:
1. A big problem is that only the first move is coming back correctly, the PV return is having some trouble.
2. There is some redundancy in the routine that manufactures the next global threat. For example, it sometimes keeps trying threats along a line in which it's already gotten a forced checkmate from an earlier threat.
3. The productions that generate the metrics for mate attack/defend are woefully primitive. Newer productions will be much better overall, although slower and more complex. Getting BWTC.0031 in 130 nodes (and on the first try!) is not as good as Paradise's 109 nodes. On the other hand, Symbolic managed the search in under five seconds, a bit less than Paradise's twenty minutes. (ChessLisp on a 2006 MacPro Xeon vs MacLisp on a 1980 Digital PDP-10)
4. The threat generation scan is doing way more work than it would be doing if there were an incremental updating facility for the threat list. I'm talking O(N*N) vs O(N*log N) here.
5. There's still a huge amount of work remaining for the implementation of the planning generation and elaboration subsystem.
6. Time control is not yet implemented. At the moment, there's a hard coded limit of 1000 threat generations per problem.
7. In spite of the above glaring deficiencies, the mate search is surprisingly effective with locating the key move for a good number of tricky checkmating problems. For all of the problems tried, it was able to locate the key move and a proof in under a thousand nodes and usually in under a hundred nodes.
