Author: Andreas Stabel
Date: 02:30:12 03/03/00
Go up one level in this thread
On March 02, 2000 at 18:20:47, Robert Hyatt 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 ? > >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 Thanks for the enlightening - I stand corrected (nothing like numbers to really stop your mouth). But I don't give up that easily, so here is another thought on the matter. If searching to ply N took time X and after failing high it may take 100X or more because the hash table has no useful move ordering info and so on, why not just start from ply 1 again. Would you not expect the new search to take a least not more than a small multiple of X ? Perhaps you should consider to do like me. No move ordering info in the hash table, (almost no move ordering at all) - life gets much simpler that way :) 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.