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, f, d)
g := f
upperBound := +∞
lowerBound := -∞
repeat
if g = lowerBound then
β := g+1
else
β := g
g := AlphaBetaWithMemory(root, β-1, β, d)
if g < β 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.