Author: Omid David Tabibi
Date: 09:58:21 07/13/03
Go up one level in this thread
On July 13, 2003 at 12:47:25, Omid David Tabibi wrote: >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 "hard" not "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.