Author: Dan Newman
Date: 13:01:28 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 ? > I have this trouble with my program too. I think this is due to doing the fail-high re-search without benefit of an iteratively deepened search. Ordinarily you extend the PV one move at a time, the previous iteration having given you a scaffolding to build the next on. As long as the PV doesn't change, this goes pretty quickly. The trouble occurs when you've gotten to very deep searches and one of the early moves in the PV gets changed--the worst case being the root move. When this happens most of that ideal move ordering info from the hash table is no longer available, and we end up relying on poorer guesses as to best moves (internal iterative deepening move, winning captures, killers and so forth). With a deep search to magnify the effect, we can end up with orders of magnitude more nodes to visit. >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 :) > Well, with a 10-ply search the worst case would be billions of times worse than the best case. It only takes a small change in branching factor to get a few orders of magnitude change in nodes visited, if you are searching deep enough... -Dan. >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. > >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.