Computer Chess Club Archives




Subject: Re: MTD: an observation and a question

Author: Robert Hyatt

Date: 22:28:52 09/12/02

Go up one level in this thread

On September 12, 2002 at 11:54:11, Dieter Buerssner wrote:

>On September 12, 2002 at 09:28:28, Robert Hyatt wrote:
>>The gotcha is to use fail-soft.  And this probably requires a few changes
>>to how you back up scores.  IE you might do something like this:
>>        v=Search(-beta, -alpha, etc);
>>        if (v > alpha) {
>>            if (v > beta) return beta;
>>            alpha=v;
>>        }
>>That return beta is not fail-soft.  it should be changed to
>>            if (v > beta) return v;
>This is not enough. You need a new variable, for example best (intitialized to
>some very bad score)
>         v=Search(-beta, -alpha, etc);
>         if (v > best) {
>           best = v;
>           /* And to the PV discussion: here the "semi-PV" must be updated */
>           if (v > alpha) {
>             if (v > beta) return v;
>             alpha=v;
>           }
>         }
>and out of the search loop:
>  return best;
>Your code snippet (Crafty, too) is essentially fail hard. In the parent node,
>after you returned best, you end up returning alpha in most cases (which is
>almost the same, as you would return beta in the fail high node).

Right.  This was one of _many_ changes I did when I tried mtd(f) a couple of
years back.  I left a bit of the "fail-soft" code in place, because it didn't
make any real difference, but I did take the piece you mentioned above out
(starting alpha off very low).

I ended up with a pretty decent implementation, but it was only efficient
in positions where the score didn't change a lot.  Which was a pretty big
percentage, generally.  However, when I had those big jumps, it reall did
badly, enough so that the "average" performance simply never quite caught
back up to normal PVS...

But I haven't "given up", just "put on the back burner" further testing...

This page took 0.31 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.