Home * Search * MTD(f)
Ascending_and_Descending.jpg

MTD(f),
a search algorithm created by Aske Plaat and the short name for MTD(n, f), which stands for something like Memory-enhanced Test Driver with node n and value f. MTD is the name of a group of driver-algorithms that search minimax trees using null window alpha-beta with transposition table calls.

In order to work, MTD(f) needs a first guess as to where the minimax value will turn out to be. The better than first guess is, the more efficient the algorithm will be, on average, since the better it is, the less passes the repeat-until loop will have to do to converge on the minimax value. If you feed MTD(f) the minimax value to start with, it will only do two passes, the bare minimum: one to find an upper bound of value x, and one to find a lower bound of the same value [1].
M. C. Escher, Ascending and Descending, 1960 [2]

Pascal Pseudo Code

Original Pascal pseudo code by Aske Plaat:
function MTDF(root : node_type; f : integer; d : integer) : integer;
      g := f;
      upperbound := +INFINITY;
      lowerbound := -INFINITY;
      repeat
            if g == lowerbound then beta := g + 1 else beta := g;
            g := AlphaBetaWithMemory(root, beta - 1, beta, d);
            if g < beta then upperbound := g else lowerbound := g;
      until lowerbound >= upperbound;
      return g;
Typically, one would call MTD(f) in an iterative deepening framework, the first guess the value of the previous iteration:
function iterative_deepening(root : node_type) : integer;
 
      firstguess := 0;
      for d = 1 to MAX_SEARCH_DEPTH do
            firstguess := MTDF(root, firstguess, d);
            if times_up() then break;
      return firstguess;

C Pseudo Code

Slightly modified pseudo code in C:
int mtdf(int f, int depth) {
   int bound[2] = {-oo, +oo}; // lower, upper
   do {
      beta = f + (f == bound[0]);
      f = alphaBetaWithMemory(beta - 1, beta, depth);
      bound[f < beta] = f;
   } while (bound[0] < bound[1]);
   return f;
}

See Also


Publications


Forum Posts

1997 ...

2000

2001

2002

2003

2004

2005 ...

2010 ...


External Links


References

  1. ^ Quote by Aske Plaat from MTD(f) - A Minimax Algorithm faster than NegaScout
  2. ^ Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website

What links here?


Up one level