Author: Robert Hyatt
Date: 21:53:08 07/12/03
Go up one level in this thread
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. 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.