Computer Chess Club Archives




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

Author: Dann Corbit

Date: 10:58:58 04/14/04

Go up one level in this thread

On April 14, 2004 at 13:51:17, Bo Persson wrote:

>On April 14, 2004 at 04:57:01, Dann Corbit wrote:
>>Picking out the hash value and moving the lookup to the end gives a bit better
>>/* MTD(f) is an alternative search to pvs */
>>int             mtdf(int f, int depth)
>>    int             beta;
>>    int             smallest = -INFINITY;
>>    int             greatest = INFINITY;
>>    TranspositionEntry *entry;
>>    do {
>>        if (f == smallest)
>>            beta = f + 1;
>>        else
>>            beta = f;           /* beta is starting with a first best guess */
>>        f = AlphaBeta(beta - 1, beta, depth);
>You have a problem right here, if you don't use fail-soft. The returned value
>will always be either beta or beta-1.
>>        if (f < beta)
>>            greatest = f;
>>        else {
>>            int             j;
>>            smallest = f;       /* performs a cut-off */
>Say you got beta-1 from AlphaBeta. Then you set greatest = beta-1, and try again
>with a window one single point lower. How long does it take to reach down to the
>the real upper bound?

It depends on how good your initial guess was.  I have a database with hundreds
of millions of analyzed positions, so I figured MTD(f) was a very natural
approach, since I will often have a very good estimate.

I was playing around and trying to understand the algorithm better.

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