Author: Robert Hyatt
Date: 05:04:09 03/03/00
Go up one level in this thread
On March 03, 2000 at 05:30:12, Andreas Stabel wrote: >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 ? Before I answer, take a deep breath and think about it. :) What answer would you expect a 1 ply search to produce _now_? Maybe the same thing it produced before? That is the problem. We would get back to depth=X again, and fail high on a different move again. The first N searches should produce the same thing they did the last time... which is a headache of course. > >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 :) > If you mean simpler = slower, yes. :) But you have move ordering info even if you think you don't. Because you get scores. And they all become suddenly useless after a fail high. >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.