MTDf

Home * Search * MTD(f)

M. C. Escher, Ascending and Descending [1] [2] 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 [3].

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#

• Category:MTD(f)
• Aspiration Windows
• Iterative Deepening
• Minimax Wall
• NegaC*
• SSS* and Dual*
• Transposition Table

Publications#

1994 …#

• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994, 2014). SSS* = Alpha-Beta + TT. TR-CS-94-17, University of Alberta, arXiv:1404.1517
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994, 2014). A New Paradigm for Minimax Search. TR-CS 94-18, University of Alberta, arXiv:1404.1515
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1995, 2015). Best-First Fixed Depth Game Tree Search in Practice. IJCAI-95, arXiv:1505.01603
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996, 2017). A Minimax Algorithm Better Than Alpha-beta?: No and Yes. arXiv:1702.03401
• 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, 2014). MTD(f), A Minimax Algorithm Faster Than NegaScout. Internal Report, Erasmus University Rotterdam, arXiv:1404.1511

2000 …#

• Arie de Bruin, Wim Pijls (2003). Trends in game tree search. Erasmus University, Rotterdam
• 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 …#

• Eric Stock, David J. King (2010). A new enhancement to MTD(f). Games and Arts, Abertay University, ResearchGate [4]
• 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
• Jan-Jaap van Horssen (2018). Handling Search Inconsistencies in MTD(f). pdf
• Jan-Jaap van Horssen (2019). Move selection in MTD(f) . ICGA Journal, Vol. 41, 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
• mtdf by Daniel Homan, CCC, May 13, 1999
• 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
• MTD(f) experiments with Crafty by Eric Stock, CCC, December 18, 2009 » Crafty [5]

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
• Handling search inconsistencies in MTD(f) by Jan-Jaap van Horssen, World Draughts Forum, February 26, 2018
• What am I missing with respect to MTDf by Jonathan Rosenthal, CCC, June 21, 2018

2020 …#

• MTDF - what am I doing wrong? by Alex Baker, CCC, September 02, 2020

External Links#

• MTD(f) - A Minimax Algorithm faster than NegaScout by Aske Plaat
• MTD(f) Experiments by Jan-Jaap van Horssen
• MTD(f) from Wikipedia
• Lecture notes for February 2, 1999 Variants of Alpha-Beta Search by David Eppstein
• Jan Garbarek, Keith Jarrett, Palle Danielsson, Jon Christensen - Spiral Dance, 1974, YouTube Video

References#

1. ↑ M. C. Escher, Ascending and Descending, 1960, Picture gallery “Recognition and Success 1955 - 1972” from The Official M.C. Escher Website
2. ↑ Penrose stairs from Wikipedia
3. ↑ Quote by Aske Plaat from MTD(f) - A Minimax Algorithm faster than NegaScout
4. ↑ MTD(f) experiments with Crafty by Eric Stock, CCC, December 18, 2009
5. ↑ Eric Stock, David J. King (2010). A new enhancement to MTD(f). Games and Arts, Abertay University

Up one level