Author: Omid David Tabibi
Date: 22:19:17 07/12/03
Go up one level in this thread
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. 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. > >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.