Author: Robert Hyatt
Date: 18:03:05 12/15/03
Go up one level in this thread
On December 15, 2003 at 19:11:00, Jeremiah Penery wrote: >On December 14, 2003 at 23:14:00, Robert Hyatt wrote: > >>On December 14, 2003 at 20:52:15, Jeremiah Penery wrote: >> >>>On December 14, 2003 at 17:32:12, Robert Hyatt wrote: >>> >>>>On December 14, 2003 at 02:54:32, Jeremiah Penery wrote: >>>> >>>>>On December 13, 2003 at 13:07:00, Robert Hyatt wrote: >>>>> >>>>>>I have seen worse. What happens is that the aspiration window initially cuts >>>>>>off all mate scores. But once it fails low, it can't just find any old mate >>>>>>and cut off analyzing that line. Now it has to follow _all_ mates and that >>>>>>kills performance. This also happens in endgames where you can potentially >>>>>>promote a pawn, but it always gets lost, so you can search to great depth. >>>>>>And eventually you find that you can promote it there, but now all those lines >>>>>>you got cutoffs on before (where the pawn promoted, but it wasn't forced) now >>>>>>explode and while the depth 25 search took 10 seconds, the depth 26 search might >>>>>>not take 10 days... >>>>>> >>>>>>It's a known problem with no known solution. >>>>>> >>>>>>Even not using aspiration search won't solve it. >>>>> >>>>>You can not lower the window to -INF, but rather on the initial fail low move it >>>>>down -1, then next do -3, and so on. Or just do it for fail-high and that >>>>>should affect fail-low also (since a fail-low on one side is a fail-high for the >>>>>other). >>>> >>>> >>>>Yes you can. We documented that in "using time wisely" and "using time wisely, >>>>revisited" which were published in the JICCA. But it only solves it for >>>>some cases, not the pawn promotion case. Because you _must_ drop it low enough >>>>to let the promotion stand, and that is low enough to let _all_ promotions >>>>stand, which blows the search right out of reality. >>> >>>Dropping it low enough to let promotions stand does not have to be the same as >>>dropping it low enough to let it find mates everywhere. You can still get a >>>huge improvement over dropping immediately to -INF. >> >> >>You are missing my point. If the "target score" is simply promoting a pawn, > >I don't think I'm missing your point. First, you talked about mate scores, not >promotions, so I responded about mate scores. > Yes, but if the _final_ position is a mate, then you are going to have to raise beta to +infinity. If you got away with pruning non-forced mates earlier, suddenly they don't prune and the tree will explode. The case you are talking of is the case where you are winning some material, but there are also lots of forced mates. Going directly to +infinity is worse there. But I believe this is a rare case also. It is much more common to search for N plies with no forced mate or pawn promotion, then when you finally get to the ply where you can force it, the tree explodes far beyond any reasonable ability to actually search it. There it doesn't matter what you do, once you get beta "right" the floodgates open. The plus for going up or down slowly is that you hope you raise the window over the actual score, without raising it over all the non-forced stuff... That does happen, but not terribly often. >>but it takes great depth to find this, then the shallow searches will get by >>with a narrow aspiration window and they will fly, as the non-forced promotions >>produce cutoffs and get discarded. But once you get to the correct depth and >>prove that a promotion is possible, then the window must be large enough to >>let that promotion produce a true score, and now _every_ promotion has to be >>searched, they don't cause cutoffs. And the tree explodes. > >Tree explosion is one of Crafty's biggest problems. Programs that are stronger >than Crafty have tree explosions much more rarely than Crafty does. They must >have found some way to control tree explosions. > >I've seen cases where Crafty finds at depth 2-3 that move A gets score >-MATE_IN_2, so it naturally chooses a different move, B. When move B fails low >(not to mate score), and Crafty returns to move A the search explodes and never >terminates (as long as I let it search - many minutes). > >That kind of thing doesn't happen very often. Much more likely is the case that >Crafty simply fails low/high on something and spends much more time searching >one move than it did for all previous moves at all previous depths combined.
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.