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