MTD(f), an abbreviation of MTD(n,f) (which is itself an abbreviation of Memory-enhance Test Driver with node n and value f) is a minimax search algorithm that improves on the basic alpha-beta pruning algorithm.
Zero Window Searches
MTD(f) gets its efficiency from doing only zero-window alpha-beta searches, and using a "good" bound (variable beta) to do those zero-window searches. Conventionally AlphaBeta is called with a wide search window, as in AlphaBeta(root, -INFINITY, +INFINITY, depth), making sure that the return value lies between the value of alpha and beta. In MTD(f) a window of zero size is used, so that on each call AlphaBeta will either fail high or fail low, returning a lower bound or an upper bound on the minimax value, respectively. Zero window calls cause more cutoffs, but return less information - only a bound on the minimax value. To find the minimax value, MTD(f) has to call AlphaBeta a number of times, eventually converging towards it. The overhead of re-exploring parts of the search tree in repeated calls to AlphaBeta disappears if a transposition table is used to store and retrieve the nodes it sees in memory.
Pseudocode
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;
Performance
Implementations of the MTD(f) algorithm had been proven to be better than other search algorithms (e.g. Negascout) in games such as chess[1]. However MTD(f) has practical issues in chess engines, such as the reliance on the transposition table, which makes it a less desirable choice. Today most chess engine authors still prefer Negascout.