Difference between revisions of "MTD(f)"

From Chessprogramming wiki
Jump to: navigation, search
 
(14 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * MTD(f)'''
 
'''[[Main Page|Home]] * [[Search]] * MTD(f)'''
  
[[FILE:EschersAscending_and_Descending.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/recogn-bmp/LW435.jpg| [[Arts#Escher|M. C. Escher]], Ascending and Descending, 1960 <ref>[[Arts#Escher|M. C. Escher]], Ascending and Descending, 1960, [http://www.mcescher.com/Gallery/gallery-recogn.htm Picture gallery "Recognition and Success 1955 - 1972" ] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]  
+
[[FILE:EschersAscending_and_Descending.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/recogn-bmp/LW435.jpg| [[:Category:M. C. Escher|M. C. Escher]], Ascending and Descending <ref>[[:Category:M. C. Escher|M. C. Escher]], Ascending and Descending, 1960, [http://www.mcescher.com/Gallery/gallery-recogn.htm Picture gallery "Recognition and Success 1955 - 1972" ] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> <ref>[https://en.wikipedia.org/wiki/Penrose_stairs Penrose stairs from Wikipedia]</ref> ]]  
  
 
'''MTD(f)''',<br/>
 
'''MTD(f)''',<br/>
Line 47: Line 47:
 
</pre>
 
</pre>
  
=See Also=  
+
=See Also=
 +
* [[:Category:MTD(f)]]
 
* [[Aspiration Windows]]
 
* [[Aspiration Windows]]
 
* [[Iterative Deepening]]
 
* [[Iterative Deepening]]
Line 57: Line 58:
 
=Publications=  
 
=Publications=  
 
==1994 ...==
 
==1994 ...==
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994'''). ''[http://arxiv.org/abs/1404.1515?context=cs.AI A New Paradigm for Minimax Search]''. TR 94-18
+
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994, 2014'''). ''SSS* = Alpha-Beta + TT''. TR-CS-94-17, [[University of Alberta]], [https://arxiv.org/abs/1404.1517 arXiv:1404.1517]
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1996'''). ''Best-First Fixed-Depth Minimax Algorithms''[http://www.ldc.usb.ve/%7Ebonet/courses/ci5437/papers/mtd.pdf pdf]
+
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1994, 2014'''). ''A New Paradigm for Minimax Search''. TR-CS 94-18, [[University of Alberta]], [https://arxiv.org/abs/1404.1515 arXiv:1404.1515]
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1996'''). ''An Algorithm Faster than NegaScout and SSS* in Practice''. [http://citeseerx.ist.psu.edu/showciting;jsessionid=04E25D5F074D8B5BABB68D2AC5BA5D39?cid=3161130 pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.8641 CiteSeerX]
+
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1995, 2015'''). ''Best-First Fixed Depth Game Tree Search in Practice.'' [[Conferences#IJCAI1995|IJCAI-95]], [https://arxiv.org/abs/1505.01603 arXiv:1505.01603]
* [[Aske Plaat]] ('''1997'''). ''[http://arxiv.org/abs/1404.1511?context=cs.AI MTD(f), A Minimax Algorithm Faster Than NegaScout]''. Internal Report, [https://en.wikipedia.org/wiki/Erasmus_University_Rotterdam Erasmus University Rotterdam]
+
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1996'''). ''Best-First Fixed-Depth Minimax Algorithms.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) 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''. [https://arxiv.org/abs/1702.03401 arXiv:1702.03401]
 +
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1996'''). ''An Algorithm Faster than NegaScout and SSS* in Practice''. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.77.9111&rep=rep1&type=pdf pdf] from [https://en.wikipedia.org/wiki/CiteSeerX CiteSeerX]
 +
* [[Aske Plaat]] ('''1997, 2014'''). ''MTD(f), A Minimax Algorithm Faster Than NegaScout''. Internal Report, [https://en.wikipedia.org/wiki/Erasmus_University_Rotterdam Erasmus University Rotterdam], [https://arxiv.org/abs/1404.1511?context=cs.AI arXiv:1404.1511]
 
==2000 ...==
 
==2000 ...==
 +
* [[Arie de Bruin]], [[Wim Pijls]] ('''2003'''). ''[https://repub.eur.nl/pub/459 Trends in game tree search]''. [https://en.wikipedia.org/wiki/Erasmus_University_Rotterdam Erasmus University, Rotterdam]
 
* [[Jacek Mańdziuk]], [[Daniel Osman]] ('''2004'''). ''Alpha-Beta Search Enhancements with a Real-Value Game-State Evaluation Function''. [[ICGA Journal#27_1|ICGA Journal, Vol. 27, No. 1]], [http://www.mini.pw.edu.pl/~mandziuk/PRACE/ICGA.pdf pdf]
 
* [[Jacek Mańdziuk]], [[Daniel Osman]] ('''2004'''). ''Alpha-Beta Search Enhancements with a Real-Value Game-State Evaluation Function''. [[ICGA Journal#27_1|ICGA Journal, Vol. 27, No. 1]], [http://www.mini.pw.edu.pl/~mandziuk/PRACE/ICGA.pdf pdf]
 
* [[Kazutomo Shibahara]], [[Nobuo Inui]], [[Yoshiyuki Kotani]] ('''2005'''). ''Adaptive Strategies of MTD-f for Actual Games''. [http://www.informatik.uni-trier.de/~ley/db/conf/cig/cig2005.html#ShibaharaIK05 CIG 2005], [http://cswww.essex.ac.uk/cig/2005/papers/p1018.pdf pdf]
 
* [[Kazutomo Shibahara]], [[Nobuo Inui]], [[Yoshiyuki Kotani]] ('''2005'''). ''Adaptive Strategies of MTD-f for Actual Games''. [http://www.informatik.uni-trier.de/~ley/db/conf/cig/cig2005.html#ShibaharaIK05 CIG 2005], [http://cswww.essex.ac.uk/cig/2005/papers/p1018.pdf pdf]
 
==2010 ...==
 
==2010 ...==
 +
* [[Eric Stock]], [[David J. King]] ('''2010'''). ''[https://rke.abertay.ac.uk/en/publications/a-new-enhancement-to-mtdf A new enhancement to MTD(f)]''. Games and Arts, [https://en.wikipedia.org/wiki/Abertay_University Abertay University], [https://www.researchgate.net/publication/304307495_A_New_Enhancement_to_MTDf ResearchGate] <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=31130 MTD(f) experiments with Crafty] by [[Eric Stock]], [[CCC]], December 18, 2009</ref>
 
* [[Jr-Chang Chen]], [[I-Chen Wu]], [[Wen-Jie Tseng]], [[Bo-Han Lin]], [[Chia-Hui Chang]] ('''2015'''). ''[https://ir.nctu.edu.tw/handle/11536/124541 Job-Level Alpha-Beta Search]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 7, No. 1
 
* [[Jr-Chang Chen]], [[I-Chen Wu]], [[Wen-Jie Tseng]], [[Bo-Han Lin]], [[Chia-Hui Chang]] ('''2015'''). ''[https://ir.nctu.edu.tw/handle/11536/124541 Job-Level Alpha-Beta Search]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 7, No. 1
 +
* [[Jan-Jaap van Horssen]] ('''2018'''). ''Handling Search Inconsistencies in MTD(f)''. [https://jhorssen.home.xs4all.nl/Maximus/research/Handling%20Search%20Inconsistencies%20in%20MTDf.pdf pdf]
 +
* [[Jan-Jaap van Horssen]] ('''2019'''). ''Move selection in MTD(f) ''. [[ICGA Journal#41_1|ICGA Journal, Vol. 41, No. 1]]
  
 
=Forum Posts=  
 
=Forum Posts=  
Line 79: Line 87:
 
'''1999'''
 
'''1999'''
 
* [https://www.stmintz.com/ccc/index.php?id=43395 Re: CilkChess] by [[Don Dailey]], [[CCC]], February 14, 1999 » [[CilkChess]]
 
* [https://www.stmintz.com/ccc/index.php?id=43395 Re: CilkChess] by [[Don Dailey]], [[CCC]], February 14, 1999 » [[CilkChess]]
 +
* [https://www.stmintz.com/ccc/index.php?id=51608 mtdf] by [[Daniel Homan]], [[CCC]], May 13, 1999
 
* [https://www.stmintz.com/ccc/index.php?id=60833 Building the Principal Variation in MTD(f) searches] by [[Andrew Williams]], [[CCC]], July 18, 1999 » [[Principal Variation]]
 
* [https://www.stmintz.com/ccc/index.php?id=60833 Building the Principal Variation in MTD(f) searches] by [[Andrew Williams]], [[CCC]], July 18, 1999 » [[Principal Variation]]
 
* [https://www.stmintz.com/ccc/index.php?id=61058 MTD is a big win] by [[Don Dailey]], [[CCC]], July 19, 1999
 
* [https://www.stmintz.com/ccc/index.php?id=61058 MTD is a big win] by [[Don Dailey]], [[CCC]], July 19, 1999
Line 122: Line 131:
 
* [https://www.stmintz.com/ccc/index.php?id=480865 MTD(f) and Wikipedia] by [[Joachim Rang]], [[CCC]], January 19, 2006
 
* [https://www.stmintz.com/ccc/index.php?id=480865 MTD(f) and Wikipedia] by [[Joachim Rang]], [[CCC]], January 19, 2006
 
* [http://www.talkchess.com/forum/viewtopic.php?t=21360 MTD(f) experiences] by [[Don Dailey]], [[CCC]], May 25, 2008
 
* [http://www.talkchess.com/forum/viewtopic.php?t=21360 MTD(f) experiences] by [[Don Dailey]], [[CCC]], May 25, 2008
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=31130 MTD(f) experiments with Crafty] by [[Eric Stock]], [[CCC]], December 18, 2009 » [[Crafty]] <ref>[[Eric Stock]], [[David J. King]] ('''2010'''). ''[https://rke.abertay.ac.uk/en/publications/a-new-enhancement-to-mtdf A new enhancement to MTD(f)]''. Games and Arts, [https://en.wikipedia.org/wiki/Abertay_University Abertay University]</ref>
 
==2010 ...==
 
==2010 ...==
 
* [http://www.talkchess.com/forum/viewtopic.php?t=53388 An Idea Of speeding up MTD-f] by [[Pio Korinth]], [[CCC]], August 22, 2014
 
* [http://www.talkchess.com/forum/viewtopic.php?t=53388 An Idea Of speeding up MTD-f] by [[Pio Korinth]], [[CCC]], August 22, 2014
 
* [http://www.talkchess.com/forum/viewtopic.php?t=60583 MTD-f: Extracting PV ?] by [[Henk van den Belt]], [[CCC]], June 24, 2016
 
* [http://www.talkchess.com/forum/viewtopic.php?t=60583 MTD-f: Extracting PV ?] by [[Henk van den Belt]], [[CCC]], June 24, 2016
 
* [https://groups.google.com/forum/#!topic/fishcooking/ivM7n3DFQX8 mtd(f)] by stefano.c, [[Computer Chess Forums|FishCooking]], August 7, 2016 » [[Stockfish]]
 
* [https://groups.google.com/forum/#!topic/fishcooking/ivM7n3DFQX8 mtd(f)] by stefano.c, [[Computer Chess Forums|FishCooking]], August 7, 2016 » [[Stockfish]]
 +
* [http://laatste.info/bb3/viewtopic.php?f=53&t=7903 Handling search inconsistencies in MTD(f)] by [[Jan-Jaap van Horssen]], [http://laatste.info/bb3/viewforum.php?f=53 World Draughts Forum], February 26, 2018
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=67783 What am I missing with respect to MTDf] by [[Jonathan Rosenthal]], [[CCC]], June 21, 2018
 +
==2020 ...==
 +
* [http://talkchess.com/forum3/viewtopic.php?f=7&t=74971 MTDF - what am I doing wrong?] by Alex Baker, [[CCC]], September 02, 2020
  
 
=External Links=  
 
=External Links=  
 
* [http://people.csail.mit.edu/plaat/mtdf.html MTD(f) - A Minimax Algorithm faster than NegaScout] by [[Aske Plaat]]
 
* [http://people.csail.mit.edu/plaat/mtdf.html MTD(f) - A Minimax Algorithm faster than NegaScout] by [[Aske Plaat]]
 +
* [https://jhorssen.home.xs4all.nl/Maximus/research/mtdf/index.htm MTD(f) Experiments] by [[Jan-Jaap van Horssen]]
 
* [https://en.wikipedia.org/wiki/MTD-f MTD(f) from Wikipedia]
 
* [https://en.wikipedia.org/wiki/MTD-f MTD(f) from Wikipedia]
* [[Videos#JanGarbarek|Jan Garbarek]], [[Videos#KeithJarrett|Keith Jarrett]], [https://en.wikipedia.org/wiki/Palle_Danielsson Palle Danielsson], [[Videos#JonChristensen|Jon Christensen]] - [https://en.wikipedia.org/wiki/Belonging_%28album%29 Spiral Dance], 1974, [https://en.wikipedia.org/wiki/YouTube YouTube] Video  
+
* [https://www.ics.uci.edu/~eppstein/180a/990202b.html Lecture notes for February 2, 1999  Variants of Alpha-Beta Search] by [[David Eppstein]]
 +
* [[:Category:Jan Garbarek|Jan Garbarek]], [[:Category:Keith Jarrett|Keith Jarrett]], [https://en.wikipedia.org/wiki/Palle_Danielsson Palle Danielsson], [[:Category:Jon Christensen|Jon Christensen]] - [https://en.wikipedia.org/wiki/Belonging_%28album%29 Spiral Dance], 1974, [https://en.wikipedia.org/wiki/YouTube YouTube] Video  
 
: {{#evu:https://www.youtube.com/watch?v=oZuPd9dVApo|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=oZuPd9dVApo|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Search|Up one level]]'''
 
'''[[Search|Up one level]]'''
 
[[Category:M. C. Escher]]
 
[[Category:M. C. Escher]]
 +
[[Category:Jon Christensen]]
 +
[[Category:Jan Garbarek]]
 +
[[Category:Keith Jarrett]]

Latest revision as of 23:13, 31 January 2022

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].

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

Publications

1994 ...

2000 ...

2010 ...

Forum Posts

1997 ...

Re: Tree search issues! by Robert Hyatt, rgcc, May 26, 1997
Re: Tree search issues! by Aske Plaat, rgcc, May 27, 1997

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

2000 ...

2001

2002

Re: MTD(f) Problems by Rudolf Huber, CCC, April 11, 2002
Re: Couple of chess programming questions - MDT and parallel by Scott Farrell, CCC, September 10, 2002 » Parallel Search

2003

Re: MTD, IID, fail-low, root-research by Rudolf Huber, CCC, August 14, 2003
Re: MTD(F) results by Rudolf Huber, CCC, December 17, 2003

2004

MTD(f) by Tord Romstad, CCC, January 14, 2004

2005 ...

2010 ...

2020 ...

External Links

References

Up one level