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 windowalpha-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]}

function MTDF(root : node_type; f :integer; d :integer):integer;
g := f;
upperbound :=+INFINITY;
lowerbound :=-INFINITY;repeatif g == lowerbound then beta := g +1else 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 =1to MAX_SEARCH_DEPTH do
firstguess := MTDF(root, firstguess, d);if times_up()thenbreak;
return firstguess;

Home * Search * MTD(f)MTD(f),a search algorithm created by Aske Plaat and the short name for MTD(n, f), which stands for something like

Memory-enhancedTestDriver with node n and valuef. 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 guessas 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]}.^{[2]}## Table of Contents

## Pascal Pseudo Code

Original Pascal pseudo code by Aske Plaat:Typically, one would call MTD(f) in an iterative deepening framework, the first guess the value of the previous iteration:

## C Pseudo Code

Slightly modified pseudo code in C:## See Also

## Publications

1994).A New Paradigm for Minimax Search. TR 94-181996).Best-First Fixed-Depth Minimax Algorithms. pdf1996).An Algorithm Faster than NegaScout and SSS* in Practice. pdf from CiteSeerX1997).MTD(f), A Minimax Algorithm Faster Than NegaScout. Internal Report, Erasmus University Rotterdam2004).Alpha-Beta Search Enhancements with a Real-Value Game-State Evaluation Function. ICGA Journal, Vol. 27, No. 1, pdf2005).Adaptive Strategies of MTD-f for Actual Games. CIG 2005, pdf## Forum Posts

## 1997 ...

## 2000

## 2001

## 2002

Re: MTD(f) Problems by Rudolf Huber, CCC, April 11, 2002

Re: Couple of chess programming questions - MDT and parallel by Scott Farrell, CCC, September 10, 2002 » Parallel Search

## 2003

Re: MTD, IID, fail-low, root-research by Rudolf Huber, CCC, August 14, 2003

Re: MTD(F) results by Rudolf Huber, CCC, December 17, 2003

## 2004

MTD(f) by Tord Romstad, CCC, January 14, 2004

## 2005 ...

## 2010 ...

## External Links

## References

## What links here?

Up one level