Author: Robert Hyatt
Date: 15:20:47 03/02/00
Go up one level in this thread
On March 02, 2000 at 10:21:40, Andreas Stabel wrote: >On March 02, 2000 at 10:02:52, Robert Hyatt wrote: > >>On March 02, 2000 at 06:47:25, Andreas Stabel wrote: >> >>>On March 01, 2000 at 22:54:01, Robert Hyatt wrote: >>> >>>>On March 01, 2000 at 17:19:38, Dann Corbit wrote: >>>> >>>>>On March 01, 2000 at 17:05:13, Dave Gomboc wrote: >>>>> >>>>>>On March 01, 2000 at 13:53:57, Dann Corbit wrote: >>>>>> >>>>>>>On March 01, 2000 at 10:28:56, Dave Gomboc wrote: >>>>>>>[snip] >>>>>>> >>>>>>>>Well, my computer resolved the fail high in twenty seconds or so. Odd. >>>>>>> >>>>>>>You have a multiple CPU machine (I think Bernhard does as well). I believe that >>>>>>>sometimes you will get different move orderings because of this and solve early >>>>>>>(or late). >>>>>> >>>>>>Yes. >>>>>> >>>>>>Occasionally Crafty does go on a "forever think", even on 1 cpu. I don't recall >>>>>>versions from say a year ago doing this. I'm sure Bob would do something about >>>>>>it if he knew of a good solution for it. Something somewhere must be blowing up >>>>>>somehow (as if that description helps. ;-) >>>>> >>>>>On the other hand, I am not sure it needs fixing. Look at the recent CCC >>>>>tournament where Crafty pounded the ether-bits out of all the competition, >>>>>including the best commercial programs in the world on top-notch hardware. >>>>> >>>>>The check extension explosions almost never cause crafty to make the wrong move >>>>>(that I have seen). If the timer fired and said "it's time to move now" it >>>>>seems like usually, it would make the right choice. It's just a bit puzzled >>>>>about exactly how good the choice is. >>>>> >>>>>Since "the proof of the pudding is in the eating" I'm not so sure it is a good >>>>>idea to 'fix' anything. >>>> >>>> >>>>These "hangs" are rarely extension problems. They are more commonly alpha/beta >>>>window problems. IE it is easy to search a position where most moves lead to >>>>mate, but the mates are not forced, so that the best score is just +.02... >>>> >>>>all the mates get pruned instantly. But on a fail high, where beta is relaxed >>>>to +inf, these mates can't be pruned, and now you have to search thru the forest >>>>of checks, mates, and shorter mates, to find the shortest mate. Often that >>>>can't be resolved inside the time limit. But who cares? >>> >>>I use crafty a lot for analyzing and my experience is that this is a very >>>comon situation. Perhaps it wouldn't matter so much if it only happened on >>>fail highs, but in an equal amount of cases it happens on a fail low where >>>it may be fatal for crafty not to find a better move. >>> >>>In the cases where I've had the patience to wait for a resolution of the fail >>>high or low, the amount of time sometimes turn out the be incredibly large. >>>If the total time consumed by crafty before the fail high or low is X, it is >>>common to have to wait 100X or even 1000X for crafty to resolve the fail. >>> >>>I wonder if it is possible to set some of the parameters of crafty to lighten >>>this problem, espesially when analyzing a position fot a long time. >>> >>>Best regards >>>Andreas Stabel >> >>The problem with fail-lows is that move ordering is blown. The hash table >>was set based on the best move being best. But at the current depth, we >>suddenly find that this is wrong. And _all_ the stored hash moves suddenly >>become wrong and useless, because at the new depth, we have discovered that >>all our previous analysis had overlooked a critical move due to lack of >>depth. >> >>If a normal position takes too long, you can back off the extensions if you >>want to (ext command). >> >>For fail low/fail high positions, there is not much that can be done that I >>can see. I am not seeing this as a "common" happening, however, in watching >>Crafty play on ICC. It does happen occasionally, but not even once per game >>that I am seeing. > >The reason why it is "common" for me is perhaps because I usually don't analyze >whole games, but rather special positions where I know or suspect that there >are tactical possibilities. When crafty sees this it usually fails low or high. > >I can understand the argument about the hash values up to a point, but if to >make all the existing hash values only took X minutes, why should it take >100X or more to make them again ? This is the point of 'iterated deepening'. Use shallow searches to seed the hash table with good moves to try in the deeper searches. And all of a sudden, everything you 'learned' becomes worthless, sort of like diving off into a 12 ply search from the beginning, with no PV or anything to guide you. It would take a _long_ time when compared to searching from depth=1 to depth=12 sequentially, saving everything along the way. > >You say that the move ordering is blown, but the increased time it takes to >research the position seems to indicate that the move ordering suddenly >became the worst possible :) Not really close. Just compare these two numbers: x=2*sqrt(38^N) y=38^N for any N (search depth) you want. 100x is chickenfeed compared to what truly worst-first move ordering would do. It would increase the size of the tree by a factor of millions or billions, not a hundred. > >Do you perhaps search deeper after failing high or low, or increase extensions >... or perhaps more likely there is something fundamental that I don't >understand. No. For a given iteration the search depth is fixed. But when alpha or beta gets relaxed, things that were getting pruned quickly may now have to be searched completely. And that might be a huge tree. > >I know that in certain positions, the new best variation forces crafty to >analyze an exponential increase in positions which could just be cut off >earlier, but is this so common ? > >Regards >Andreas Stabel
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.