Definitions

mtd

MTD-f

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.

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.

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. Negascout) in games such as chess 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.

External links

Search another word or see mtdon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature