Home * Search * MTD(f)

		MTD(f), a search algorithm created by Aske Plaat and the short name for MTD(n, f), which stands for something like Memory-enhanced Test Driver with node n and value f. MTD is the name of a group of driver-algorithms that search minimax trees using null window alpha-beta with transposition table calls. In order to work, MTD(f) needs a first guess as to where the minimax value will turn out to be. The better than first guess is, the more efficient the algorithm will be, on average, since the better it is, the less passes the repeat-until loop will have to do to converge on the minimax value. If you feed MTD(f) the minimax value to start with, it will only do two passes, the bare minimum: one to find an upper bound of value x, and one to find a lower bound of the same value [1].
M. C. Escher, Ascending and Descending, 1960 [2]

Pascal Pseudo Code

Original Pascal pseudo code by Aske Plaat:

function MTDF(root : node_type; f : integer; d : integer) : integer;
      g := f;
      upperbound := +INFINITY;
      lowerbound := -INFINITY;
      repeat
            if g == lowerbound then beta := g + 1 else beta := g;
            g := AlphaBetaWithMemory(root, beta - 1, beta, d);
            if g < beta then upperbound := g else lowerbound := g;
      until lowerbound >= upperbound;
      return g;

Typically, one would call MTD(f) in an iterative deepening framework, the first guess the value of the previous iteration:

function iterative_deepening(root : node_type) : integer;
 
      firstguess := 0;
      for d = 1 to MAX_SEARCH_DEPTH do
            firstguess := MTDF(root, firstguess, d);
            if times_up() then break;
      return firstguess;

C Pseudo Code

Slightly modified pseudo code in C:

int mtdf(int f, int depth) {
   int bound[2] = {-oo, +oo}; // lower, upper
   do {
      beta = f + (f == bound[0]);
      f = alphaBetaWithMemory(beta - 1, beta, depth);
      bound[f < beta] = f;
   } while (bound[0] < bound[1]);
   return f;
}

See Also

• Aspiration Windows
• Iterative Deepening
• Minimax Wall
• NegaC*
• SSS* and Dual*
• Transposition Table

Publications

1994 ...

• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994). A New Paradigm for Minimax Search. TR 94-18
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). Best-First Fixed-Depth Minimax Algorithms. pdf
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). An Algorithm Faster than NegaScout and SSS* in Practice. pdf from CiteSeerX
• Aske Plaat (1997). MTD(f), A Minimax Algorithm Faster Than NegaScout. Internal Report, Erasmus University Rotterdam

2000 ...

• Jacek Mańdziuk, Daniel Osman (2004). Alpha-Beta Search Enhancements with a Real-Value Game-State Evaluation Function. ICGA Journal, Vol. 27, No. 1, pdf
• Kazutomo Shibahara, Nobuo Inui, Yoshiyuki Kotani (2005). Adaptive Strategies of MTD-f for Actual Games. CIG 2005, pdf

2010 ...

• Jr-Chang Chen, I-Chen Wu, Wen-Jie Tseng, Bo-Han Lin, Chia-Hui Chang (2015). Job-Level Alpha-Beta Search. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, No. 1

Forum Posts

1997 ...

• Tree search issues! by Magnus Heldestad, rgcc, May 26, 1997 » Enhanced Transposition Cutoff
  Re: Tree search issues! by Robert Hyatt, rgcc, May 26, 1997
  Re: Tree search issues! by Aske Plaat, rgcc, May 27, 1997

1998

• New(?) search idea by Andrew Walker, CCC, January 21, 1998
  Re: New(?) search idea by Don Dailey, CCC, January 22, 1998
  MTD(f) (was Re: New(?) search idea.) by Stuart Cracraft, CCC, January 22, 1998
  Re: New(?) search idea by Robert Hyatt, CCC, January 22, 1998 » Minimax Wall

1999

• Re: CilkChess by Don Dailey, CCC, February 14, 1999 » CilkChess
• Building the Principal Variation in MTD(f) searches by Andrew Williams, CCC, July 18, 1999 » Principal variation
• MTD is a big win by Don Dailey, CCC, July 19, 1999
• MTD(f) by Nicolas Carrasco, CCC, September 28, 1999

2000 ...

• Getting a PV using MTD(f) by Tijs van Dam, CCC, February 08, 2000 » Principal variation
• MTD(f) and PV by David Rasmussen, rgcc, March 09, 2000 » Principal variation

2001

• MTD(f) and the PV by Adrian Jackson, rgcc, March 16, 2001 » Principal variation
• Beating MTD(n,f) by Gian-Carlo Pascutto, CCC, June 05, 2001
• MTD(f) and killer heuristics by Marcus Heidkamp, CCC, July 12, 2001 » Killer Heuristic
• Performance of MTD(f) versus eval granularity? by Werner Mühlpfordt, CCC, November 01, 2001

2002

• MTD(f) Problems by Oren Avraham, CCC, April 10, 2002
  Re: MTD(f) Problems by Rudolf Huber, CCC, April 11, 2002
• About False Fail Highs, professionals, and MTD searches by Gian-Carlo Pascutto, CCC, April 12, 2002 » Fail-High
• Couple of chess programming questions by Eli Liang, CCC, September 10, 2002 » ProbCut, Evaluation, Bitboards, 0x88, Fractional Plies, Transposition Table
  Re: Couple of chess programming questions - MDT and parallel by Scott Farrell, CCC, September 10, 2002 » Parallel Search
• calculating the PV using MTD by Fabien Letouzey, CCC, September 11, 2002 » Principal variation
• MTD: an observation and a question by Martin Fierz, CCC, September 11, 2002

2003

• MTD(f), Quiscient Search, and hashing Quiscient nodes by Joel, CCC, January 19, 2003
• MTD(f) and storing the PV by Tord Romstad, CCC, July 29, 2003
• MTD, IID, fail-low, root-research by Juergen Wolf, CCC, August 14, 2003 » Internal Iterative Deepening, Fail-Low, Root
  Re: MTD, IID, fail-low, root-research by Rudolf Huber, CCC, August 14, 2003
• MTD(f) and hash table size by Tord Romstad, CCC, August 16, 2003
• MTD(F) results by Anthony Cozzie, CCC, December 16, 2003
  Re: MTD(F) results by Rudolf Huber, CCC, December 17, 2003

2004

• QSearch() as PVS() ? by Matthias Gemuh, CCC, January 14, 2004
  MTD(f) by Tord Romstad, CCC, January 14, 2004
• Search behavior in a case of root fail high/low by Sergei S. Markoff, CCC, March 10, 2004 » Fail-High, Fail-Low, Root
• mtd(f) and null move by Peter Alloysius, CCC March 11, 2004
• Question for the MTD(f) experts by Dann Corbit, CCC, April 14, 2004
• An MTD(f) question about NULL MOVE searching by Dann Corbit, CCC, July 16, 2004
• MTD(f) by Stuart Cracraft, CCC, July 26, 2004
• MTD Drivers by Tor Lattimore, CCC, August 10, 2004

2005 ...

• MTD(f) by Tor Alexander Lattimore, CCC, June 15, 2005
• Rybka uses PVS and not MTD(f). Its no Fruit-Clone by Chrilly Donninger, CCC December 12, 2005
• MTD(f) versus Alpha-Beta by Harm Geert Muller, Winboard Forum, December 13, 2005
• MTD(f) by Engin Üstün, CCC, December 17, 2005
• MTD(f) and Wikipedia by Joachim Rang, CCC, January 19, 2006
• MTD(f) experiences by Don Dailey, CCC, May 25, 2008

2010 ...

• An Idea Of speeding up MTD-f by Pio Korinth, CCC, August 22, 2014
• MTD-f: Extracting PV ? by Henk van den Belt, CCC, June 24, 2016
• mtd(f) by stefano.c, FishCooking, August 7, 2016 » Stockfish

External Links

• MTD(f) - A Minimax Algorithm faster than NegaScout by Aske Plaat
• MTD(f) from Wikipedia
• Jan Garbarek, Keith Jarrett, Palle Danielsson, Jon Christensen - Spiral Dance, 1974, YouTube Video
  

References

1. ^ Quote by Aske Plaat from MTD(f) - A Minimax Algorithm faster than NegaScout
2. ^ Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website

What links here?

Up one level