Author: Andreas Stabel
Date: 02:16:04 03/03/00
Go up one level in this thread
On March 02, 2000 at 16:01:28, Dan Newman wrote: >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 Thank you very much for an informative answer. I am making my own chess program (who doesn't ?), but my hash and move ordering is not yet complex enough to encounter theese problems. Seems like I have a lot of fun ahead :) 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.