Computer Chess Club Archives


Search

Terms

Messages

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

Author: Andrew Williams

Date: 12:24:53 04/14/04

Go up one level in this thread


On April 14, 2004 at 14:13:04, Dann Corbit wrote:

>On April 14, 2004 at 14:09:04, Bo Persson wrote:
>
>>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;
>>            }
>>            else
>>            {
>>               GlobalLowerBound = gamma;
>>               gamma = min(gamma + Step, GlobalUpperBound - 1);
>>               SteppedUp = true;
>>            }
>>
>>            if (SteppedUp & SteppedDown)
>>               Step /= 2;
>>            else
>>               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.
>
>I have lots of ideas along these lines.
>
>I thought of using an MTD(f) like driver, but in MTD(bi) format, so that I will
>binary search.
>
When I first started with MTD (aeons ago now), i tried MTD(bi) and it just
didn't work. It looks like it should, but doesn't. I then switched to using
MTD(bi) after something similar to what Bo posted above. That didn't work
either. YMMV of course.

>I thought of doing a parabolic fit of the last few guesses and extrapolating the
>next guess.
>
>I thought of doing an aspiration window around the last bound and MTD(bi) search
>of that.
>
>Some others besides.  But I want to understand the algorithm through and through
>before I venture into that land.
>
>I got reinterested in MTD(f) because Uri mentioned that he would like to be able
>to experiment with it in his search.
>
>In case he wants me to give him a hand, I had better understand it well myself.

It's good fun playing with MTD, but make sure your hash-table works properly
first!

Andrew



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.