Computer Chess Club Archives




Subject: Re: Question for the MTD(f) experts

Author: Bo Persson

Date: 11:09:04 04/14/04

Go up one level in this thread

On April 14, 2004 at 13:47:06, Dann Corbit wrote:

>On April 14, 2004 at 13:33:38, Robert Hyatt wrote:
>>On April 14, 2004 at 03:30:22, Dann Corbit wrote:
>>>I decided to toss an MTD(f) search into TSCP, and I've got something wrong, but
>>>I can't quite see what it is.
>>There is a lot more to do.
>>1.  you need to modify the hash table to store 2 bounds, not 1.
>That was not done yet.

But not too hard!

>>2.  the search must be fail-soft.  TSCP isn't.
>I had already done that.
>>3.  PV has to be yanked from the hash table and that makes it flakey at times as
>>has been discussed many times.  There is another way to get the PV, but it is a
>>special case solution only for mtd...
>Tord showed a very nice way to do that with a clever "hash only" update.
>>4.  the convergence has to be accelerated.  IE on a fail high searching v and
>>v+1 won't cut it.

I can supply that part, learned from CCC a couple of years ago of course.

            // Calculate next gamma and Step

            if (gamma < Beta)
               GlobalUpperBound = gamma;
               gamma = max(gamma - Step, GlobalLowerBound + 1);
               SteppedDown = true;
               GlobalLowerBound = gamma;
               gamma = min(gamma + Step, GlobalUpperBound - 1);
               SteppedUp = true;

            if (SteppedUp & SteppedDown)
               Step /= 2;
               if (Step < (GlobalUpperBound - GlobalLowerBound) / 2)
                  Step *= 2;

Here gamma is your f. The idea is to accellerate the stepping, until you have
over stepped the score twice, once in each direction. Then you have an
acceptable bound, and can start to zoom in, using smaller and smaller steps as
you get closer and closer.

The GlobalUpperBound and GlobalLowerBound should really be global. If you use
lazy evaluations those are the bounds to use there, not the local alpha/beta
which are always just 1 point apart.

>>IE this is not a "drop in and go" it is a "rewrite and test" thing to do. :)

No, I think it is slight rewrite and a re-tune.

Bo Persson

This page took 0.08 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.