Author: Omid David Tabibi
Date: 09:47:25 07/13/03
Go up one level in this thread
On July 13, 2003 at 12:39:01, Robert Hyatt wrote: >On July 13, 2003 at 01:19:17, Omid David Tabibi wrote: > >>On July 13, 2003 at 00:53:08, Robert Hyatt wrote: >> >>>On July 12, 2003 at 23:47:23, Omid David Tabibi wrote: >>> >>>>On July 12, 2003 at 22:31:52, Robert Hyatt wrote: >>>> >>>>>On July 12, 2003 at 18:10:39, Omid David Tabibi wrote: >>>>> >>>>>>On July 12, 2003 at 15:06:55, Dieter Buerssner wrote: >>>>>> >>>>>>>On July 12, 2003 at 14:43:52, Heiner Marxen wrote: >>>>>>> >>>>>>>>On July 12, 2003 at 14:13:25, Omid David Tabibi wrote: >>>>>>>> >>>>>>>>>Hi, >>>>>>>>> >>>>>>>>>After a few days of rewriting large parts of my program's code, to my surprise I >>>>>>>>>found out that: >>>>>>>>> >>>>>>>>>if (value >= beta) >>>>>>>>> return beta; >>>>>>>> >>>>>>>>The classic version. >>>>>>>> >>>>>>>>>and >>>>>>>>> >>>>>>>>>if (value >= beta) >>>>>>>>> return value; >>>>>>>> >>>>>>>>This variant is called "fail soft". >>>>>>> >>>>>>>When also additionally, you don't return alpha in fail low situations, but a >>>>>>>best value. I actually wonder, if you have a classic fail hard search, and just >>>>>>>change one line in search like above, can it change anything? The parent node >>>>>>>could return alpha (not less). So did the child. Where can this value > beta >>>>>>>come from? >>>>>>> >>>>>>>>The caller must be prepared to receive a value outside the alpha/beta window. >>>>>>>> >>>>>>>>>don't yield the very same result. >>>>>>>> >>>>>>>>The second version (fail soft) has the potential to generate better results, >>>>>>>>sometimes. When these are reused via the TT, the rest may change. >>>>>>> >>>>>>>Yes. It might also influence move-ordering, for example when using some "mate >>>>>>>killer heuristics". Additionally, for PVS combined with null move an aritifact >>>>>>>can arise. With another bound in the research (which will be needed here), you >>>>>>>might not fail high null move anymore (the original null move fail high was sort >>>>>>>of bogus), and the whole normal search could show, that it would not result in a >>>>>>>value as high as the value returned by the null move. Similar for other pruning >>>>>>>techniques, and perhaps even extensions (when dependent on bounds). >>>>>>> >>>>>>>>>I've been trying to find the bug for the past 24 hours, without any success so >>>>>>>>>far. Has anyone experienced this problem in the past?! Any ideas as to the >>>>>>>>>possible source of the problem? >>>>>>>>> >>>>>>>>>Thanks. >>>>>>>> >>>>>>>>What is the problem? >>>>>>> >>>>>>>Good question. Many such things are just unavoidable for efficient search. >>>>>>> >>>>>> >>>>>>But when transposition table, PVS, apsiration window, and null-move are all >>>>>>turned off (for the purpose of debugging) then fail-soft and fail-hard should >>>>>>result in the same tree (same node count), shouldn't they? >>>>>> >>>>> >>>>>Nope. You are altering the search bounds. >>>> >>>>Why? When instead of alpha I send value <= alpha, the father of this node >>>>receives it as value >= beta, and results in a cutoff. Had I sent alpha, the >>>>father would have received it as beta, with the same result. The same holds true >>>>if I send value >= beta instead of beta: the father will receive it as value <= >>>>alpha which is the same as sending beta which will be received as alpha. So, I >>>>don't see where any search bounds are changed. >>>> >>> >>><= alpha is not necessarily >= beta at a previous node, for one thing. It >>>_might_ be true or it might not be, depending on whether you have already >>>searched the PV move or not. >> >>If we are not doing PVS, then we are searching all the moves the same. For >>example: >> >>assume the initial bound is (alpha, beta) >>you call the child with (-beta, -alpha) >> >>three things could happen based on returned value (in both fail soft and fail >>hard): >>value <= alpha : ignore the move >>value > alpha && value < beta : alpha = value >>value >= beta : cutoff >> >>assume this move returned x (x > alpha && x < beta) and now our window is (alpha >>+ x, beta) >>we call the next child with (-beta, -alpha - x) >> >>and again regardless of whether we are using fail hard or fail soft, one of the >>same three things will happen based on the returned score. > >THat's ok. But you _still_ can return a bound that is outside the original >alpha/beta window you started with. And if you let that happen, then you >affect pruning decisions that depend on alpha/beta values themselves. > >IE even a normal hash look-up can raise alpha or lower beta. And _that_ can >change the score if it affects pruning (forward pruning) such as is done to >throw out bad captures, or null-move pruning. > >> >>So, no matter what the current alpha and beta are, when we call the child with >>(-beta, -alpha), his value <= alpha will be our value >= beta, and his value >= >>beta will be our value <= alpha. > >I don't understand why you think those are the same. If my current beta >value is X, and I pass that to the next ply as -X, it can easily affect my >X value when the value is backed up. And changing _either_ of my alpha/beta >values, in any way, can affect pruning that uses alpha/beta values. Note I >am _not_ talking about the alpha/beta cutoff process itself. I am talking >about things that use alpha/beta to shrink the tree. Forward pruning like >null-move, or tossing out improbable captures in the q-search, etc. > Read again what I said a few posts above: "But when transposition table, PVS, apsiration window, and null-move are all turned off (for the purpose of debugging) then fail-soft and fail-hard should result in the same tree (same node count)." All what you said is correct, but assuming that we are doing _pure_ "textbook" alphabeta search, then fail high and fail soft will result in the same very search bounds, and thus the same node count. > > >> >>> >>>Also, if you do a _real_ fail-soft, then you _definitely_ shift the bounds, >>>which is the case I was really talking about. And any change in the bounds >>>can wreck any sort of pruning based on alpha/beta bounds, such as the capture >>>elimination I do in my q-search. >>> >>> >>> >>>> >>>>>That can affect the PV although >>>>>the score probably should not change. However, if you use alpha/beta to >>>>>do other things, such as pruning q-search moves (as but one example) then you >>>>>can change the score too. >>>>> >>>>> >>>>> >>>>> >>>>>> >>>>>> >>>>>>>Regards, >>>>>>>Dieter
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.