Author: Heiner Marxen
Date: 19:43:04 12/30/01
Go up one level in this thread
On December 30, 2001 at 20:51:48, leonid wrote: >Hi! Hi again! >>> Do you really >>>have attacking and defending side going into different move sorting (alignment)? > >>Yes. > >Now I see that your mate solver have more differenciation that mine have. > >>>In my program (never mind what side was initially asked to look for mate) all >>>"move sorting" for two colors (for two move sortings) goes in identical way. >>>Reason for identical search (at least in my mind) is in the fact that defending >>>side also will look for many possible mates during entire search. Each time when >>>"defensive side" will respond with mate, offensive side will stop searching. >>>This will speed entire hunt for mate. >> >>Aha! I see! That is what I call the "anti" heuristic, although in Chest it >>is very limited (to immediate mate moves). > >What is "immediate mate move"? If the defender is to move, and the current depth is at least 3 (mate-in-2 or more left after defender move), and the defender has more than just his bare king, then, before even generating the legal defender moves, Chest calls the special mate-move-generator, trying to find a "mate the attacker in 1". The moves found by that move generator are just candidates, and must be executed to verify them, but there are not many false candidates. I did mention this heuristic some time ago, already, since especially for your "beasts" it sometimes yields exceptionally high success rates. Currently I don't try deeper mates in the opposite direction, but since the defender move sorting does prefer (somewhat) to limit the freedom of the attacker's king, the chance to find a mate-in-1 is not so bad. >>>Here once again I must take care. Will give rustic and simple explanation. Best >>>move in mate solver is the move that lead to mate. Previously found best move is >>>used for putting the most successful at the head of chain. Each best move for >>>its ply. Here also one important moment. If previous best move was "passive >>>move" it will not jump to the head of move chain over "active moves". It will go >>>only at the head of passive moves. >> >>That really sounds like a (special sort of) killer heuristic. > >Will try to remember this strange expression. To me it appears to be standard term in the computer chess community. >>>>How exactly are these moves "used"? >>>>What exactly triggers the saving of another move (replacement)? >>> >>>Only when next move that lead to mate for this ply ply was found. Only then >>>previous best move will be replaced. >> >>So a defensive move only is remembered as "best active" move, if it does >>mate the attacking side? Sounds a bit restrictive. >>While it may help in many of your crowded many-queen positions, >>in more quiet positions (say typical chess problems) this will be extremely >>rare, I think. > >Maybe your not symmetrical way could have some sense in my program. I should >verify this when I will be with my solver the next time. Statistics will say how >much it work. Good idea! Thanks! > >>>Ha, ha, ha!!!! It look like myself going to some parts of my program that I not >>>touched for years. Very often it is very obscure to me what I wrote there. This >>>is why I leave a lot of description. >> >>... which only helps if that description contains more detail than just >>"it works best this way" :-) > >I don't leave description that something work better that before. In each part >of my program that I wrote (when I really was with it) each part was changed by >hundreds of time. To say that this way is better that other one hundreds will >only bring confusion in description. > >>>>My co-author Holger Pause developped the complex part of this move sorting >>>>by try and error, until he was satisfied with the results for a certain >>>>benchmark. That way some of the things in it are hard to explain, beyond >>>>"it works well that way". > >And how Holger wrote its move sorting? Did he started by doing move generator >first? Don't be afraid to be very descriptive. It is just too interesting to >know how other big projects started. First, we developped together some complete version of Chest, including move generator, hash table etc. Sorting of defender moves was done by the simple "basic" logic I already explained, and which still is used for depth=2 analysis. Then we (Holger and I) had some intensive discussions, how to improve the situation. The defenders most important job has to be to cut down the tree size. On that we did agree. But how to achieve this in a better way? The simple heuristic we already had appeared to be not appropriate for really deep analysis, say depth=6 remaining. Tree sizes would vary very drastically depending on the choice of the defender move. And to avoid such large trees we felt that some more effort should be spent. We agreed on a benchmark position: "Das unsterbliche Schachproblem" by C.Bayer, a mate-in-9: [D]3Q4/5q1k/4ppp1/2Kp1N1B/RR6/3P1r2/4nP1b/3b4 w - - Holger was interested to do research and experiments on this, and tried to work on the tree size estimation idea. He spent 2 weeks of his vacations on this, and came back with an extended version of Chest, which now solved that mate-in-9 much, much faster. Actually, it was the first time that we did solve that position (took 32.5 hours on a HP9000-835 in 1991). So I took his code, cleaned it up somewhat, added some comments, and asked him about all those peculiar details in there, which I did not understand. Most often he could not explain much more than "I tried several things, and this worked best... don't know why". There is still some "magic" in that defender sorting function. I have tried many small improvements there during the years since then, but most of my attempts had to be discarded, again, since the effect did slow down the overall computation. Well, such is life :-) >>>All my move sortings was done only after statistical data. Nothing was left to >>>my personal preferences. Even my mistake about "best passive" and "best active" >>>in my mate solver, probably, come from the fact that I tried them in mate solver >>>but came later to something else. >> >>Respect! >>That is the best way to do it: first measure, then decide. Scientific. >>Sometimes I do not do a complete measuring (too lazy), and even if I do, >>I often do not document the results of my experiments in a way that can >>be understood years later. :-( > >I still have mate positions created in around 1995 with all time for my program >and other programs that I was able to buy. Recently I looked into my old >positions and found some that took around 5 hours to solve position only 5 moves >deep. > >>Well, it is not rocket science, it is just for fun :-) > >Probably your program is already rocket science. I do remember buying one chess >program that was written by ex NASA programmer. His chess had very often rupture >in very simple mate positions. > >>A happy new year to all of you! > >All the best for you and your Chest!!!! > >Leonid. Cheers! Heiner
This page took 0.04 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.