MTD-f
Encyclopedia : M : MT : MTD : MTD-f
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[link]. 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.External links
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.