MTD-f
Encyclopedia
MTD, 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.
, 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.
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
) in games such as chesshttp://portal.acm.org/citation.cfm?id=240998&coll=GUIDE&dl=GUIDE&CFID=50049687&CFTOKEN=16181537. 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.
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
search algorithm, an alternative to the alpha-beta pruning
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
algorithm.
Zero Window Searches
MTD(f) efficiently does only zero-window alpha-beta searches, with a "good" bound (variable beta). In NegascoutNegascout
NegaScout or Principal Variation Search is a negamax algorithm that can be faster than alpha-beta pruning. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree...
, 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
Transposition table
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times....
stores and retrieves the previously searched portions of the tree in memory to reduce the overhead of re-exploring parts of the search tree.
Pseudocode
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
Performance
Implementations of the MTD(f) algorithm have been proven to be more efficient (search fewer nodes) than other search algorithms (e.g. NegascoutNegascout
NegaScout or Principal Variation Search is a negamax algorithm that can be faster than alpha-beta pruning. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree...
) in games such as chesshttp://portal.acm.org/citation.cfm?id=240998&coll=GUIDE&dl=GUIDE&CFID=50049687&CFTOKEN=16181537. However, in practice, MTD(f) has some issues such as heavy dependence on the transposition table
Transposition table
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times....
, 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.