Computer Chess Club Archives


Search

Terms

Messages

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

Author: Andrew Williams

Date: 13:23:02 04/14/04

Go up one level in this thread


On April 14, 2004 at 15:36:15, Dann Corbit wrote:

>On April 14, 2004 at 15:24:53, Andrew Williams wrote:
>
>>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.
>
>Have you tried it with an aspiration window around the last search score?
>
>I think the big problem with MTD(bi) is that you will do a terrible job if you
>always search -32767 to +32767.  You are guaranteed to do 16 searches every time
>and so it is going to be a loser if your standard MTD(f) averages less than
>that.  But suppose that you use an 8 bit window of 256 centipawns?  Then you
>will need only 8 searches (unless the window fails).

I *think* so, but I didn't keep track of what I was doing back then, and PM
certainly doesn't do that now. MTD is (relatively) unexplored territory, so it's
always worth having a go.

Andrew






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