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 [http://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.

External links

* [http://home.tiscali.nl/askeplaat/mtdf.html Description of MTD(f) algorithm]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • MTD — may refer to:*An unemployed workers movement of Argentina (Spanish Movimiento de Trabajadores Desocupados ) mdash; see Piquetero ; *A mass transit district, such as the Champaign Urbana Mass Transit District or the Metropolitan Transit District;… …   Wikipedia

  • MTD — puede referirse a: Movistar TV Digital. McDonnell Douglas F 15 STOL/MTD, avión de prueba e investigación. Movimiento de trabajadores desocupados o piqueteros, fenómeno originario de Argentina. Metadona, fármaco opioide sintético. Todas las… …   Wikipedia Español

  • MTD — steht für: Medizinischer Transportdienst MTD (Unternehmen), ein Hersteller von motorisierten Gartengeräten Month to date, auch Mtd, ein Zeitraum ab dem Beginn des laufenden Monats bis zum aktuellen Datum Michael Tobias Design, einen Hersteller… …   Deutsch Wikipedia

  • mtd — mtd; MTD; …   English syllables

  • MTD — Abreviatura de presentación mentotransversa derecha. Diccionario Mosby Medicina, Enfermería y Ciencias de la Salud, Ediciones Hancourt, S.A. 1999 …   Diccionario médico

  • MTD — [Abk. für maximale Tagesdosis]: ↑ Maximaldosis …   Universal-Lexikon

  • MTD — MTD: Abk. für ↑maximale Tagesdosis …   Das Wörterbuch medizinischer Fachausdrücke

  • MTD — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

  • MTD — maximum tolerated dose; mean total dose; metastatic trophoblastic disease; Midwife Teacher s Diploma; minimal topological difference; Monroe tidal drainage; maximum tolerated dose; multidrug therapy; multiple tic disorder; Mycobacterium… …   Medical dictionary

  • MTD — The highest dose of a drug or treatment that does not cause unacceptable side effects. The MTD is determined in clinical trials by testing increasing doses on different groups of people until the highest dose with acceptable side effects is found …   English dictionary of cancer terms


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.