Steve Maughan wrote:This may be a stupid question but where is the mate in 11 in the search? The key move is Qg2+ and the tree seems to focus on Qxf2. I cannot see the mating line in the tree.
First, there could be a fault in my implementation. It was the first try.
Second, the search is lacking in the area of PV reporting.
Third, the program thinks the key move (or at least one key move) is 1... Qxf2+.
Fourth, here's the list of successful mate threats as taken directly from a recent log (uh, I hope you have a wide screen monitor):
Dann Corbit wrote:I mean, 662 nodes for a depth 11 mate is borderline ridiculous!
Some might say that spending tens to hundreds of milliseconds at a node is just as ridiculous.
From what I know of Paradise, it was never tried on WAC.163, but I'm fairly sure that it could have solved the problem with under 500 nodes and maybe only 250 or less. And I think that a strong human with the assistance of paper and pencil (or the electronic equivalent) could do the same. Remember that nearly all of the problems in WAC and BWTC came from human games in the first place.
Consider the human correspondence chess player. With several days to a week or so for each move, there's plenty of time for leisurely analysis. One way of doing the analysis is to get a big piece of paper and start to draw a search tree with the nodes labeled with active attack and defend issues. The human extends the tree one node at a time with a different algorithm based on which side is on the move. The player adds a node for his/her choice based on which of all the lines seems the most promising. For the opponent's choice, the node added is the one that best refutes the current threat at any level of the threat. In both cases there's a slight bias for shorter threats and faster/early refutations.
Now add a simple computer program that replaces the paper and pencil and keeps track of the tree. Add to the program a set of functions (productions) that measures the relative nastiness and speed of a threat along with a sorting routine that picks the best one. Then add a set of defensive productions that measure at all levels of a threat the relative power of possible refutations and a companion sorting routine. Wrap all of this together and you've got the basics behind Symbolic's mate search.
If I'm understanding correctly, it seems you work on this by a rate-of-change of score approach instead of actual scores and give the lines with higher rate of change for either side greater depth. Quite an interesting extension mechanism but the most interesting part is the implementation of how your program figures out how high the rate-of-change of score is. I believe this can be applied to extension and pruning decisions of traditional alphabeta trees. Rate of change information could be propogated back up to the root and also the use of hashtable entries as nodes may help comparing rate of change across the alpha-beta tree.
Last edited by Pradu on Wed May 02, 2007 3:22 am, edited 1 time in total.
Well, it's getting the right move in many problems, but of course there could still be bugs. I'm reviewing the code and will likely add some self test routines.
Pradu wrote:Search algorithm looks very alpha-betaish eg attacker/defender. The implementation of attack and defense metrics will be rather interesting though.
Well, there aren't any position scores, so there's no alpha and beta. And there isn't any real symmetry, as threats are generated via global selection while refutations are generated along a single variation. Each side has a different search, and both are best first and not depth first.
The attack and defense do take turns as they would in a traditional A/B searcher. But there's no particular "current position" or "current expectation window."
--------
I took another look at the first cut source and plenty of omissions have come to light, including the lack of draw recognition other than stalemates. All draws are correctly marked when a node is generated and inserted into the tree, but the metrics productions don't use this data at the present. The same can be said for a lot of other attributes, so there's lots of room for improvement here.
Somewhat annoyingly, the PV returned by the mate search is almost always not the theoretically best PV but rather a PV with suboptimal moves. It turns out that both sides tend to try the worst moves last, and this is what comes back as a result. It doesn't matter too much for actual play as the attacker's first move in the final result is always correct in the sense that it leads to some forced mate, if not the fastest one.
Sounds a bit like the BStar variation I'm playing with.
Does your search resemble that ? Finding a best line by trying optimistic moves and once found, give the opponent the chance to refute it with his optimistic moves ?
Tony wrote:
Sounds a bit like the BStar variation I'm playing with.
Does your search resemble that ? Finding a best line by trying optimistic moves and once found, give the opponent the chance to refute it with his optimistic moves ?
I'm familiar with B* and Symbolic's mate search is quite different; there are no windows and no node evaluations (except for certain mate / lose / draw). There is the concept of alternating threat / refute, but there's no prove-best / disprove-rest top level control.
I found a couple of bugs so far and I expect there are a few more. I'm been inserting some diagnostic routines to help as manual scans of five hundred node trees is tedious and error prone. Interestingly, all versions of the mate search so far correctly select the key move in all problems with direct mates of length five or less. The search trees in these cases are encouragingly human like.
One problem identified so far is when a defensive move refutes one threat but fails to refute a separate and much longer threat. So there needs to be a way to count a defensive move more than once and I think I've found it by generating and propagating force / non forced move status. This should have the helpful side effect of informing both the threat and refutation generators to avoid production activities at unproductive nodes.
