Author: Heiner Marxen
Date: 18:46:47 08/08/01
Go up one level in this thread
On August 08, 2001 at 20:54:16, leonid wrote: >On August 08, 2001 at 09:23:33, Heiner Marxen wrote: > >>On August 08, 2001 at 08:56:52, leonid wrote: >> >>>On August 07, 2001 at 13:33:24, Heiner Marxen wrote: >>> >>>>On August 04, 2001 at 15:56:13, leonid wrote: >>>> >>>>>On August 04, 2001 at 15:13:24, Angrim wrote: >>>>> >>>>>>On August 04, 2001 at 09:01:36, leonid wrote: >>>>>> >>>>>>>Hi! >>>>>>> >>>>>>>Are you ready for solving some mate? Here is one: >>>>>>> >>>>>>>[D]q1qk1q1q/q1qrrq1q/1bQq1Qb1/1Q1QQ1Q1/BNn2nNB/1Q4Q1/3Q4/R2K3R w - - >>>>>>> >>>>>>>Please indicate your result. >>>>>>> >>>>>>>Thanks, >>>>>>>Leonid. >>>>>> >>>>>>proved that move f6xe7 wins, 12 turns >>>>>>PN2:4523172 evals, 98612 expands, 30.16 seconds >>>>> >>>>>This time we found mate by selective at the same depth but your probably is more >>>>>quick. >>>>> >>>>>12 moves selective in 105 sec. Celeron 600. No hash. >>>>> >>>>>By brute force I stopped searching before 8 moves. 7 moves took 18 min and 57 >>>>>sec. >>>> >>>>Hello Leonid, hello Angrim! >>>> >>>>Unfortunately, Chest is not much faster: "no mate in 8" after 38.1 minutes >>>>on a K7/600 with 350 MB hash. The effective branching factor is beetween >>>>8 and 10, so more depth would cost a lot of time. And depth 12 is not >>>>reachable for Chest, here. Sorry. >>>> >>>>Cheers, >>>>Heiner >>> >>>Hi, Heiner! >>> >>>Thanks for 8 moves! >>> >>>My branching factor was 9.37, 9.96 and 11.67 between 4 moves and 7, that I look >>>by brute force. Your branching is close to mine or better. >> >>Corresponding values for Chest: 11.69, 8.44 and 9.87. About equal. >> >>>My time was, starting with 4 moves: 1.043 sec, 9.78 sec, 97 sec, 18 min 57 >>>sec. >> >>Corresponding values for Chest: 0.29s, 3.39s, 28.61s, 282.51s (4 min 42 sec) >> >>Interestingly, the mate in 4 is already faster for Chest, while more depth >>does not change much, in this case. > >Since the mate in 4 is much shorter for you, it signify that your "2 moves mate" >worked more efficiently. It is exactly what is in your and my program "special >plies" writing can give as initial speed. Yes, I agree. In the plies above the mate in 4 (i.e. nearer to the root) your search and mine appear to be quite equivalent, at least in this position. We have seen other positions from you, where Chest manages to get a much smaller EBF, but here that obviously did not work out. >I am still very curious to know how those few "special plys" are written in >other programs. It look like that, logically, everybody must have "specially >written few plys", never mind what that person wrote, mate solver or chess >program. It could be that I understood something in a wrong way but when I spoke >with one chess program writer (Tom Kerrigan), he insisted that all plys in his >chess program, and in every other, have identical writing. Basically this is correct (IMO). >Before I spoke with you (when I found that you have also specific plys writing) >my guess was that other professional chess program have slow mate search because >Tom was right. But is this really so? Yes, I think that is the main reason. Of course it depends on the way those other programs do that "mate search". Do not forget, that some programs are excellent and fast mate searchers (not proving the shortest mate, but finding some mate), e.g. CM has shown many excellent results here. >Have you some idea how other chess >programs wrote their plys? Maybe you read some other programs code. My reading, >in dispite of all my best wishes, is still close to nothing. Basically, all their plies are the same (it is just one recursive search function), until the depth is exhausted completely. At that point the recursion stops, and the "static evaluation function" kicks in. Ah, wait, normally they first start a "quienscence search", which is not necessaryly limited by depth, but follows only a limited sort of move: mostly capturing moves, may be also some checks and promotions. So the last ply is special, where the search stops. Well, that is no surprise. It is simply necessary. There are some standard techniques which are used in the last few plies, only, and by that are somewhat similar to what our mate solvers do in their last plies, although the details are very different. These techniques are called "futility pruning" and "limited razoring" in the book from Ernst Heinz. They try to estimate bounds for the search result of the small remaining search tree, and eventually use these bounds for a cutoff. A simple analogy for a mate searcher may be: If the king to mate is in the middle of the board and all 8 neighbor squares are free and not attacked... you need not search a mate move, there will be none. Two plies earlier, when we search for a mate in 2, you may do the same (i.e. not search further), but now it will not be correct always. There are very rare positions where still a mate in 2 is possible. Still, in order to be fast one could decide to tolerate the tiny inaccuracy. Other than these "forward pruning" techniques I am not aware of special methods applied by chess programs in the last plies. Hope this helps a bit. Cheers, Heiner
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.