WAC.163: 662 node search tree

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: WAC.163: 662 node search tree

Post by sje » Wed May 02, 2007 12:39 am

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):

Code: Select all

2007.05.01 20:19:27.349 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Kd2 Rd3+ Kc2 Rh2+ Kb1 Rd1#)
2007.05.01 20:19:27.694 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Kd2 Rd3+ Kc2 Rh2+ Kc1 Rd1#)
2007.05.01 20:19:30.037 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Ra3+ Kd2 e3+ Kc2 Bf5#)
2007.05.01 20:19:33.608 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf1#)
2007.05.01 20:19:34.961 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Re3+ Kc1 Re1#)
2007.05.01 20:19:36.961 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rd3+ Kc1 Rd1#)
2007.05.01 20:19:42.225 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rxg3+ Kd2 Rh2+ Kc1 Rg1#)
2007.05.01 20:19:42.511 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rxg3+ Kd2 Rh2+ Ke1 Rg1#)
2007.05.01 20:19:46.985 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf4+ Kc1 Rf1#)
2007.05.01 20:19:47.613 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf4+ Ke1 Re2+ Kd1 Rf1#)
2007.05.01 20:19:50.426 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf5+ Kc1 Rf1#)
2007.05.01 20:19:51.082 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf5+ Ke1 Re2+ Kd1 Rf1#)
2007.05.01 20:19:53.643 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf6+ Kc1 Rf1#)
2007.05.01 20:19:54.336 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf6+ Ke1 Re2+ Kd1 Rf1#)
2007.05.01 20:20:01.354 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf7+ Kc1 Rf1#)
2007.05.01 20:20:02.128 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf7+ Ke1 Re2+ Kd1 Rf1#)
2007.05.01 20:20:06.188 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf8+ Kc1 Rf1#)
2007.05.01 20:20:06.998 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Nf5 Rxf5+ Qf3 Rxf3+ Ke1 h1=R+ Ke2 Rh2+ Kd1 Rf8+ Ke1 Re2+ Kd1 Rf1#)
2007.05.01 20:20:21.214 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qe2+ Kc1 Rf1+ Qd1 Qxd1#)
2007.05.01 20:20:21.698 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qe2+ Kc1 Rf1+ Qd1 Rxd1#)
2007.05.01 20:20:40.942 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qf2+ Kc1 Qe1+ Qd1 Qxd1#)
2007.05.01 20:20:41.501 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qf2+ Kc1 Qe1+ Kc2 Rf2#)
2007.05.01 20:20:46.620 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qe2+ Kc3 Rf3+ Kb4 Qb5+ Ka3 Qa5#)
2007.05.01 20:20:50.786 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qe2+ Kc3 Rf3+ Kb4 Qb5+ Ka3 Rxb3+ axb3 Qa5#)
2007.05.01 20:20:54.637 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qe2+ Kc3 Rf3+ Kb4 Qb5+ Ka3 Qa6+ Kb4 Qb5+ Ka3 Qa5#)
2007.05.01 20:20:55.835 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kh1 Bf3+ Ng2 Bxg2#)
2007.05.01 20:21:03.834 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qe2+ Kc3 Rf3+ Kb4 Qb5+ Ka3 Qa6+ Kb4 Qb5+ Ka3 Rxb3+ axb3 Qa5#)
2007.05.01 20:21:14.804 MA: (Qxf2+ Rxf2 Rxf2+ Kg1 h2+ Kxf2 Rf6+ Ke1 h1=Q+ Nf1 Qxf1+ Kd2 Qe2+ Kc3 Rf3+ Kb4 Qb5+ Ka3 Qa6+ Kb4 Qb5+ Ka3 Qa6+ Kb4 Qb5+ Ka3 Qa5#)
2007.05.01 20:21:16.122 MA: (Qxf2+ Kh1 Bf3+ Ng2 hxg2#)
2007.05.01 20:21:16.779 MA: (Qxf2+ Ng2 Qxg2#)

User avatar
Steve Maughan
Posts: 1061
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: WAC.163: 662 node search tree

Post by Steve Maughan » Wed May 02, 2007 12:44 am

sje wrote:Third, the program thinks the key move (or at least one key move) is 1... Qxf2+.
OK - so it doesn't actually find a forced mate in 11 since Qxf2 looses, it just finds any old mate.

Regards,

Steve

Slater

Re: WAC.163: 662 node search tree

Post by Slater » Wed May 02, 2007 12:46 am

sje wrote:Wrap all of this together and you've got the basics behind Symbolic's mate search.
Oh...well when you put it like that it's simple. :lol:

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: WAC.163: 662 node search tree

Post by Pradu » Wed May 02, 2007 1:18 am

sje wrote:
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 1:22 am, edited 1 time in total.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: WAC.163: 662 node search tree

Post by sje » Wed May 02, 2007 1:19 am

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.

Tony

Re: WAC.163: 662 node search tree

Post by Tony » Wed May 02, 2007 6:27 am

sje wrote:
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 ?

Cheers,

Tony

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: WAC.163: 662 node search tree

Post by sje » Wed May 02, 2007 10:36 am

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.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: WAC.163: 662 node search tree

Post by sje » Thu May 03, 2007 9:00 pm

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.

Post Reply