Author: Robert Hyatt
Date: 20:55:26 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)." Again, I am not sure I agree _IF_ you include the concept of forward pruning based on alpha/beta bounds. If you don't include that, then I agree. Null-move is not the _only_ form of alpha/beta bound forward pruning. IE what some call the "delta algorithm" as used in Crafty's q-search. If it is possible for two different searches to hit the same node with different alpha/beta bounds (and fail-soft can certainly do this) then the score/best move can change due to differences in the q-search tree. You only mentioned disabling null-move, but there are other approaches that use alpha/beta bounds to do things. > >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. "textbook alpha/beta" really doesn't address the specifics of the q-search, for example. And making decisions on what is futile to search and what is not might be influenced by the bounds. Or it might not. It depends on whether you do that or not... > > > >> >> >>> >>>> >>>>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.