Author: Robert Hyatt
Date: 11:34:01 01/09/98
Go up one level in this thread
On January 09, 1998 at 13:54:00, Bruce Moreland wrote: > >On January 09, 1998 at 12:20:39, Ernst A. Heinz wrote: > >>BTW, what about the "mate extension" that you referred to -- are you >>willing >>to share any details? >> >>I have shortly tried to implement a "mate finding extension" twice >>without >>good success ... :-( > >I think it is important to never ask a question when you might have to >give some information back, and this is the mistake I made in this case. > >It is incredible how little content we post in this newsgroup and in >r.g.c.c. > >I hate having the feeling that those who have a better way of doing it, >but don't post, might be laughing at my primitive techniques this time. >Of course, if I happen to post something good they will go "ooh" and >immediately start coding. > >The extension is: If you discover that you get mated if you do nothing >in this position, extend all your moves by a ply (in total, this doesn't >add to other extensions). > >The idea is that if I'm getting mated if I do nothing, I probably want >to resolve this node a little better than usual, since perhaps the moves >I can make that avoid mate are just pushing it over the horizon. >Especially in cases where you give up huge material at the root, and >your opponent can give bits of it back to delay things (as in this >case). > >An alternate implementation is to note the mate threat, search >everything without extending, but if you find something that fails high >or is a PV, search it again with the extension. These implementations >seem to be approximately equivalent. > >The result is that mine finds WAC 141 in 8 plies rather than who knows >how many. A few other WAC problems benefit from this: 182, 222, and >maybe more. > >The trick is detecting that you are getting mated if you do nothing. I >am already doing a null move search, which will fail low because the >opponent has a threat. The problem is to figure out how low it is >failing. I try to return scores that are outside the alpha-beta bounds >when I can, and sometimes I catch a -MATE here, and in those cases there >is obviously a mate threat. I am sure there are other ways, lots of >ideas to try. > >So the short answer is to try to detect mate threats with the null move >search, and extend when you find one, if you would otherwise fail high >or get a PV. > >My way is obviously not perfect since other programs get this problem >more quickly. > >bruce This extension was Bruce's idea. I've been using it for a good while, but haven't said anything about it (although it's in the source code if you look carefully). But since he's explained it, there is one more thing I do that works very well. One problem with this extension is that after you search a PV move, and get a score back, and then try a different move at the root, the null-move search might fail low and you see the "mated in N" score and use that to extend. But on the re-search, after the fail-high on the root, you might not try the null move search, since it can't fail high on a +inf bound. And if you don't try it, you don't extend, and if you don't extend, you don't find the good stuff, and you then fail low and move on. in my case, when I find this "threat" I set a bit in the corresponding hash table entry. Later, after doing a lookup and having the hash table say "got entry, but insufficient depth, but this entry indicates that a null-move wouldn't fail high so don't do it" I also return the saved threat flag, and *still* extend this position. This last refinement stopped my problem on wac141 of failing high on qf4, then failing low and giving up on it. Totally free, and perfectly safe. Because if you are mated after a null move search in a position, you will *always* be mated after playing a null, so extending is safe every time... Now if some others would share good technical ideas, this might be fun. Wait, what am I saying? Forget I wrote that... never happen of course... :)
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.