Author: Robert Hyatt
Date: 09:39:01 07/13/03
Go up one level in this thread
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. > >> >>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.