Author: Omid David Tabibi
Date: 21:52:55 07/13/03
Go up one level in this thread
On July 13, 2003 at 23:55:26, Robert Hyatt wrote: >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. Sure, that was what I meant. Of course even the slightest forward pruning can change the results between fail hard and fail soft. >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.