MTD(f), an abbreviation of MTD(n,f) (Memory-enhanced Test Driver with node n and value f) is a minimax search algorithm, an alternative to the alpha-beta pruning algorithm.
Contents |
MTD(f) efficiently does only zero-window alpha-beta searches, with a "good" bound (variable beta). In Negascout, AlphaBeta is called with a wide search window, as in AlphaBeta(root, -INFINITY, +INFINITY, depth), so the return value lies between the value of alpha and beta in one call. In MTD(f), AlphaBeta fails high or 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) calls AlphaBeta a number of times, converging towards it and eventually finding the exact value. A transposition table stores and retrieves the previously searched portions of the tree in memory to reduce the overhead of re-exploring parts of the search tree.
function MTDF(root, f, d)
g := f
upperBound := +∞
lowerBound := -∞
while lowerBound < upperBound
if g = lowerBound then
β := g+1
else
β := g
g := AlphaBetaWithMemory(root, β-1, β, d)
if g < β then
upperBound := g
else
lowerBound := g
return g
Implementations of the MTD(f) algorithm have been proven to be more efficient (search fewer nodes) than other search algorithms (e.g. Negascout) in games such as chess[1]. However, in practice, MTD(f) has some issues such as heavy dependence on the transposition table, search instability, and many others. Therefore, most modern chess engines still implement Negascout, which is considered by many chess programmers to be the best search algorithm in practice.