MTD-f
From Wikipedia, the free encyclopedia
MTD(f), an abbreviation of MTD(n,f) (Memory-enhanced Test Driver with node n and value f) is a minimax search algorithm better than the basic alpha-beta pruning algorithm.
Contents |
[edit] Zero Window Searches
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.
[edit] 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
[edit] 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]. Most chess engine authors still use Negascout.
