Author: Dann Corbit
Date: 12:36:15 04/14/04
Go up one level in this thread
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).
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.