Difference between revisions of "Monte-Carlo Tree Search"

From Chessprogramming wiki
Jump to: navigation, search
(36 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
'''Monte Carlo Tree Search''', (Monte-Carlo Tree Search, MCTS)<br/>
 
'''Monte Carlo Tree Search''', (Monte-Carlo Tree Search, MCTS)<br/>
is a [[Best-First|Best-First search]] algorithm based on [https://en.wikipedia.org/wiki/Randomness random] playouts. In conjunction with [[UCT]] ('''U'''pper '''C'''onfidence bounds applied to '''T'''rees) Monte-Carlo Tree Search has yielded in a breakthrough in [[Go|Computer Go]] <ref>[[Rémi Coulom]] ('''2009'''). ''The Monte-Carlo Revolution in Go''. JFFoS'2008: Japanese-French Frontiers of Science Symposium, [http://remi.coulom.free.fr/JFFoS/JFFoS.pdf slides as pdf]</ref>, and is also successful in [[Amazons]] <ref>[[Julien Kloetzer]], [[Hiroyuki Iida]], [[Bruno Bouzy]] ('''2007'''). ''The Monte-Carlo approach in Amazons''. [[CGW 2007]]</ref> <ref>[[Richard J. Lorentz]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_2 Amazons Discover Monte-Carlo]''. [[CG 2008]]</ref>, [[Lines of Action]] <ref>[[Mark Winands]] and [[Yngvi Björnsson]] ('''2009'''). ''Evaluation Function Based Monte-Carlo LOA''. [http://www.ru.is/faculty/yngvi/pdf/WinandsB09.pdf pdf]</ref>, [[Havannah]] <ref>[[Richard J. Lorentz]] ('''2010'''). ''[http://www.springerlink.com/content/p4x16832317r1214/ Improving Monte-Carlo Tree Search in Havannah]''. [[CG 2010]]</ref>, [[Hex]] <ref>[[Broderick Arneson]], [[Ryan Hayward]], [[Philip Henderson]] ('''2010'''). ''Monte Carlo Tree Search in Hex''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://webdocs.cs.ualberta.ca/~hayward/papers/mcts-hex.pdf pdf]</ref>, [[Checkers]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=38554 UCT surprise for checkers !] by [[Daniel Shawul]], [[CCC]], March 25, 2011</ref> and other [[Games]] with some difficulties in position evaluation, but until December 2017, when a  [[Google]] [[DeepMind]] team reported on [[AlphaZero]] <ref>[[David Silver]], [[Thomas Hubert]], [[Julian Schrittwieser]], [[Ioannis Antonoglou]], [[Matthew Lai]], [[Arthur Guez]], [[Marc Lanctot]], [[Laurent Sifre]], [[Dharshan Kumaran]], [[Thore Graepel]], [[Timothy Lillicrap]], [[Karen Simonyan]], [[Demis Hassabis]] ('''2017'''). ''Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm''. [https://arxiv.org/abs/1712.01815 arXiv:1712.01815]</ref>, not for [[Chess]] <ref>[[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2010'''). ''[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1458 On Adversarial Search Spaces and Sampling-Based Planning]''. [http://www.aaai.org/Press/Proceedings/icaps10.php ICAPS 2010]</ref> <ref>[[Oleg Arenz]] ('''2012'''). ''[http://www.ke.tu-darmstadt.de/bibtex/publications/show/2321 Monte Carlo Chess]''.  B.Sc. thesis, [[Darmstadt University of Technology]], advisor [[Johannes Fürnkranz]], [http://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf pdf]</ref>.  
+
is a [[Best-First|Best-First search]] algorithm based on [https://en.wikipedia.org/wiki/Randomness random] playouts. In conjunction with [[UCT]] ('''U'''pper '''C'''onfidence bounds applied to '''T'''rees) Monte-Carlo Tree Search has yielded in a breakthrough in [[Go|Computer Go]] <ref>[[Rémi Coulom]] ('''2009'''). ''The Monte-Carlo Revolution in Go''. JFFoS'2008: Japanese-French Frontiers of Science Symposium, [http://remi.coulom.free.fr/JFFoS/JFFoS.pdf slides as pdf]</ref>, and is also successful in [[Amazons]] <ref>[[Julien Kloetzer]], [[Hiroyuki Iida]], [[Bruno Bouzy]] ('''2007'''). ''The Monte-Carlo approach in Amazons''. [[CGW 2007]]</ref> <ref>[[Richard J. Lorentz]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_2 Amazons Discover Monte-Carlo]''. [[CG 2008]]</ref>, [[Lines of Action]] <ref>[[Mark Winands]], [[Yngvi Björnsson]] ('''2009'''). ''Evaluation Function Based Monte-Carlo LOA''. [http://www.ru.is/faculty/yngvi/pdf/WinandsB09.pdf pdf]</ref>, [[Havannah]] <ref>[[Richard J. Lorentz]] ('''2010'''). ''[http://www.springerlink.com/content/p4x16832317r1214/ Improving Monte-Carlo Tree Search in Havannah]''. [[CG 2010]]</ref>, [[Hex]] <ref>[[Broderick Arneson]], [[Ryan Hayward]], [[Philip Henderson]] ('''2010'''). ''Monte Carlo Tree Search in Hex''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://webdocs.cs.ualberta.ca/~hayward/papers/mcts-hex.pdf pdf]</ref>, [[Checkers]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=38554 UCT surprise for checkers !] by [[Daniel Shawul]], [[CCC]], March 25, 2011</ref> and other [[Games]] with some difficulties in position evaluation, but until December 2017, when a  [[Google]] [[DeepMind]] team reported on [[AlphaZero]] <ref>[[David Silver]], [[Thomas Hubert]], [[Julian Schrittwieser]], [[Ioannis Antonoglou]], [[Matthew Lai]], [[Arthur Guez]], [[Marc Lanctot]], [[Laurent Sifre]], [[Dharshan Kumaran]], [[Thore Graepel]], [[Timothy Lillicrap]], [[Karen Simonyan]], [[Demis Hassabis]] ('''2017'''). ''Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm''. [https://arxiv.org/abs/1712.01815 arXiv:1712.01815]</ref>, not for [[Chess]] <ref>[[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2010'''). ''[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1458 On Adversarial Search Spaces and Sampling-Based Planning]''. [http://www.aaai.org/Press/Proceedings/icaps10.php ICAPS 2010]</ref> <ref>[[Oleg Arenz]] ('''2012'''). ''[http://www.ke.tu-darmstadt.de/bibtex/publications/show/2321 Monte Carlo Chess]''.  B.Sc. thesis, [[Darmstadt University of Technology]], advisor [[Johannes Fürnkranz]], [http://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf pdf]</ref>.  
  
 
MCTS is based on randomized explorations of the [[Search Space|search space]]. Using the results of previous explorations, the algorithm gradually grows a [[Search Tree|game tree]] in [[Memory|memory]], and successively becomes better at accurately estimating the values of the most promising moves <ref>[[Guillaume Chaslot]], [[Mark Winands]], [[Jaap van den Herik]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_6 Parallel Monte-Carlo Tree Search]''. [[CG 2008]], [https://dke.maastrichtuniversity.nl/m.winands/documents/multithreadedMCTS2.pdf pdf]</ref>.   
 
MCTS is based on randomized explorations of the [[Search Space|search space]]. Using the results of previous explorations, the algorithm gradually grows a [[Search Tree|game tree]] in [[Memory|memory]], and successively becomes better at accurately estimating the values of the most promising moves <ref>[[Guillaume Chaslot]], [[Mark Winands]], [[Jaap van den Herik]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_6 Parallel Monte-Carlo Tree Search]''. [[CG 2008]], [https://dke.maastrichtuniversity.nl/m.winands/documents/multithreadedMCTS2.pdf pdf]</ref>.   
Line 35: Line 35:
 
=Publications=  
 
=Publications=  
 
==1987==
 
==1987==
* [[Bruce Abramson]], [[Richard Korf]] ('''1987'''). ''A Model of Two-Player Evaluation Functions.'' [http://www.aaai.org/Conferences/AAAI/aaai87.php AAAI-87]. [http://www.aaai.org/Papers/AAAI/1987/AAAI87-016.pdf pdf]
+
* [[Bruce Abramson]], [[Richard Korf]] ('''1987'''). ''A Model of Two-Player Evaluation Functions.'' [[Conferences#AAAI-87|AAAI-87]], [http://www.aaai.org/Papers/AAAI/1987/AAAI87-016.pdf pdf]
 
==1990 ...==
 
==1990 ...==
* [[Bruce Abramson]] ('''1990'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=44404 Expected-Outcome: A General Model of Static Evaluation]''. IEEE Transactions on Pattern Analysis and Machine Intelligence 12(2): 182-193.
+
* [[Bruce Abramson]] ('''1990'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=44404 Expected-Outcome: A General Model of Static Evaluation]''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 12, No. 2
* [[Bruce Abramson]] ('''1990'''). ''An Analysis of Expected-Outcome.'' Journal of Experimental and Theoretical Artificial Intelligence 2: 55-73.
+
* [[Bruce Abramson]] ('''1990'''). ''An Analysis of Expected-Outcome.'' [https://en.wikipedia.org/wiki/Journal_of_Experimental_and_Theoretical_Artificial_Intelligence Journal of Experimental and Theoretical Artificial Intelligence], Vol. 2
* [[Bruce Abramson]] ('''1991'''). ''The Expected-Outcome Model of Two-Player Games.'' Part of the series, Research Notes in Artificial Intelligence (San Mateo: Morgan Kaufmann, 1991).
+
* [[Bruce Abramson]] ('''1991'''). ''The Expected-Outcome Model of Two-Player Games.'' Part of the series, Research Notes in Artificial Intelligence, Morgan Kaufmann
 
* [[Bernd Brügmann]] ('''1993'''). ''Monte Carlo Go''. [http://www.ideanest.com/vegos/MonteCarloGo.pdf pdf]
 
* [[Bernd Brügmann]] ('''1993'''). ''Monte Carlo Go''. [http://www.ideanest.com/vegos/MonteCarloGo.pdf pdf]
 
==2000 ...==
 
==2000 ...==
Line 63: Line 63:
 
* [[Shugo Nakamura]], [[Makoto Miwa]], [[Takashi Chikayama]] ('''2007'''). ''Improvement of UCT using evaluation function''. [http://www.computer-shogi.org/gpw/gpw12_e.html 12th Game Programming Workshop 2007]
 
* [[Shugo Nakamura]], [[Makoto Miwa]], [[Takashi Chikayama]] ('''2007'''). ''Improvement of UCT using evaluation function''. [http://www.computer-shogi.org/gpw/gpw12_e.html 12th Game Programming Workshop 2007]
 
* [[Keh-Hsun Chen|Ken Chen]], [[Peigang Zhang]] ('''2007'''). ''Monte-Carlo Go with Knowledge-Guided Simulations''. [[CGW 2007]]
 
* [[Keh-Hsun Chen|Ken Chen]], [[Peigang Zhang]] ('''2007'''). ''Monte-Carlo Go with Knowledge-Guided Simulations''. [[CGW 2007]]
* [[Tristan Cazenave]] ('''2007'''). ''Reflexive Monte-Carlo Search''. [[CGW 2007]], [http://www.lamsade.dauphine.fr/~cazenave/papers/reflexmc.pdf pdf]
+
* [[Tristan Cazenave]] ('''2007'''). ''Reflexive Monte-Carlo Search''. [[CGW 2007]], [http://www.lamsade.dauphine.fr/~cazenave/papers/reflexmc.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Join_Five Morpion solitaire from Wikipedia]</ref>
 
* [[François van Lishout]], [[Guillaume Chaslot]], [[Jos Uiterwijk]] ('''2007'''). ''[https://www.researchgate.net/publication/228378473_Monte-Carlo_tree_search_in_backgammon Monte-Carlo Tree Search in Backgammon]''. [[CGW 2007]]
 
* [[François van Lishout]], [[Guillaume Chaslot]], [[Jos Uiterwijk]] ('''2007'''). ''[https://www.researchgate.net/publication/228378473_Monte-Carlo_tree_search_in_backgammon Monte-Carlo Tree Search in Backgammon]''. [[CGW 2007]]
 
* [[Julien Kloetzer]], [[Hiroyuki Iida]], [[Bruno Bouzy]] ('''2007'''). ''The Monte-Carlo approach in Amazons''. [[CGW 2007]]
 
* [[Julien Kloetzer]], [[Hiroyuki Iida]], [[Bruno Bouzy]] ('''2007'''). ''The Monte-Carlo approach in Amazons''. [[CGW 2007]]
Line 75: Line 75:
 
* [[Guillaume Chaslot]], [[Louis Chatriot]], [[Christophe Fiter]], [[Sylvain Gelly]], [[Jean-Baptiste Hoock]], [[Julien Pérez]], [[Arpad Rimmel]], [[Olivier Teytaud]] ('''2008'''). ''Combining expert, offline, transient and online knowledge in Monte-Carlo exploration''. [http://www.lri.fr/%7Eteytaud/eg.pdf pdf]
 
* [[Guillaume Chaslot]], [[Louis Chatriot]], [[Christophe Fiter]], [[Sylvain Gelly]], [[Jean-Baptiste Hoock]], [[Julien Pérez]], [[Arpad Rimmel]], [[Olivier Teytaud]] ('''2008'''). ''Combining expert, offline, transient and online knowledge in Monte-Carlo exploration''. [http://www.lri.fr/%7Eteytaud/eg.pdf pdf]
 
* [[Guillaume Chaslot]], [[Mark Winands]], [[Jos Uiterwijk]], [[Jaap van den Herik]], [[Bruno Bouzy]] ('''2008'''). ''Progressive Strategies for Monte-Carlo Tree Search''. [http://www.worldscinet.com/nmnc/nmnc.shtml New Mathematics and Natural Computation], Vol. 4, No. 3, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3015&rep=rep1&type=pdf pdf] <ref>[[Jeff Rollason]] ('''2015'''). ''[http://www.aifactory.co.uk/newsletter/2015_02_mixing_immiscible.htm Mixing the Immiscible - MCTS and evaluation]''. [[AI Factory]], October 2015</ref>
 
* [[Guillaume Chaslot]], [[Mark Winands]], [[Jos Uiterwijk]], [[Jaap van den Herik]], [[Bruno Bouzy]] ('''2008'''). ''Progressive Strategies for Monte-Carlo Tree Search''. [http://www.worldscinet.com/nmnc/nmnc.shtml New Mathematics and Natural Computation], Vol. 4, No. 3, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3015&rep=rep1&type=pdf pdf] <ref>[[Jeff Rollason]] ('''2015'''). ''[http://www.aifactory.co.uk/newsletter/2015_02_mixing_immiscible.htm Mixing the Immiscible - MCTS and evaluation]''. [[AI Factory]], October 2015</ref>
* [[Guillaume Chaslot]], [[Sander Bakkes]], [[István Szita]] and [[Pieter Spronck]] ('''2008'''). ''Monte-Carlo Tree Search: A New Framework for Game AI''. [http://sander.landofsand.com/publications/AIIDE08_Chaslot.pdf pdf]
+
* [[Guillaume Chaslot]], [[Sander Bakkes]], [[István Szita]], [[Pieter Spronck]] ('''2008'''). ''Monte-Carlo Tree Search: A New Framework for Game AI''. [http://sander.landofsand.com/publications/AIIDE08_Chaslot.pdf pdf]
* [[Guillaume Chaslot]], [[Mark Winands]], [[István Szita]], and [[Jaap van den Herik]]. ('''2008'''). ''Cross-entropy for Monte-Carlo Tree Search''. [[ICGA Journal#31_3|ICGA Journal, Vol. 31, No. 3]], [http://www.personeel.unimaas.nl/m-winands/documents/crossmc.pdf pdf]
+
* [[Guillaume Chaslot]], [[Mark Winands]], [[István Szita]], [[Jaap van den Herik]]. ('''2008'''). ''Cross-entropy for Monte-Carlo Tree Search''. [[ICGA Journal#31_3|ICGA Journal, Vol. 31, No. 3]], [http://www.personeel.unimaas.nl/m-winands/documents/crossmc.pdf pdf]
 
* [[Maarten Schadd]], [[Mark Winands]], [[Jaap van den Herik]], [[Huib Aldewereld]] ('''2008'''). ''Addressing NP-Complete Puzzles with Monte-Carlo Methods''. In Volume 9: Proceedings of the AISB 2008 Symposium on Logic and the Simulation of Interaction and Reasoning, pages 55-61, Brighton, UK, 2008. The Society for the study of Artificial Intelligence and Simulation of Behaviour. [http://www.personeel.unimaas.nl/Maarten-Schadd/Papers/2008SameGameAISB.pdf pdf]
 
* [[Maarten Schadd]], [[Mark Winands]], [[Jaap van den Herik]], [[Huib Aldewereld]] ('''2008'''). ''Addressing NP-Complete Puzzles with Monte-Carlo Methods''. In Volume 9: Proceedings of the AISB 2008 Symposium on Logic and the Simulation of Interaction and Reasoning, pages 55-61, Brighton, UK, 2008. The Society for the study of Artificial Intelligence and Simulation of Behaviour. [http://www.personeel.unimaas.nl/Maarten-Schadd/Papers/2008SameGameAISB.pdf pdf]
 
* [[Maarten Schadd]], [[Mark Winands]], [[Jaap van den Herik]], [[Guillaume Chaslot]], [[Jos Uiterwijk]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_1 Single-Player Monte-Carlo Tree Search]''. [[CG 2008]], [http://www.personeel.unimaas.nl/Maarten-Schadd/Papers/2008SameGameCG.pdf pdf]
 
* [[Maarten Schadd]], [[Mark Winands]], [[Jaap van den Herik]], [[Guillaume Chaslot]], [[Jos Uiterwijk]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_1 Single-Player Monte-Carlo Tree Search]''. [[CG 2008]], [http://www.personeel.unimaas.nl/Maarten-Schadd/Papers/2008SameGameCG.pdf pdf]
Line 86: Line 86:
 
* [[Keh-Hsun Chen|Ken Chen]], [[Dawei Du]], [[Peigang Zhang]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_9 A Fast Indexing Method for Monte-Carlo Go]''. [[CG 2008]]
 
* [[Keh-Hsun Chen|Ken Chen]], [[Dawei Du]], [[Peigang Zhang]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_9 A Fast Indexing Method for Monte-Carlo Go]''. [[CG 2008]]
 
* [[Yizao Wang]], [[Jean-Yves Audibert]], [[Rémi Munos]] ('''2008'''). ''Algorithms for Infinitely Many-Armed Bandits''. Advances in Neural Information Processing Systems, [http://www.stat.lsa.umich.edu/%7Eyizwang/publications/wang08algorithms.pdf pdf], Supplemental material - [http://www.stat.lsa.umich.edu/%7Eyizwang/publications/wang08algorithmsSupp.pdf pdf]
 
* [[Yizao Wang]], [[Jean-Yves Audibert]], [[Rémi Munos]] ('''2008'''). ''Algorithms for Infinitely Many-Armed Bandits''. Advances in Neural Information Processing Systems, [http://www.stat.lsa.umich.edu/%7Eyizwang/publications/wang08algorithms.pdf pdf], Supplemental material - [http://www.stat.lsa.umich.edu/%7Eyizwang/publications/wang08algorithmsSupp.pdf pdf]
* [http://en.scientificcommons.org/james_h_brodeur James H. Brodeur], [http://en.scientificcommons.org/benjamin_e_childs Benjamin E. Childs] and [[Levente Kocsis]] ('''2008'''). ''Transpositions and Move Groups in Monte Carlo Tree Search.'' [http://eprints.pascal-network.org/archive/00004571/01/8057.pdf pdf]
+
* [http://en.scientificcommons.org/james_h_brodeur James H. Brodeur], [http://en.scientificcommons.org/benjamin_e_childs Benjamin E. Childs], [[Levente Kocsis]] ('''2008'''). ''Transpositions and Move Groups in Monte Carlo Tree Search.'' [http://eprints.pascal-network.org/archive/00004571/01/8057.pdf pdf]
* [[Hilmar Finnsson]] and [[Yngvi Björnsson]]. ('''2008'''). ''Simulation-Based Approach to General Game Playing.'' In The Twenty-Third AAAI Conference on Artificial Intelligence, [[AAAI]] Press, 2008. Accepted. [http://www.ru.is/faculty/yngvi/pdf/FinnssonB08a.pdf pdf], [http://www.aaai.org/Papers/AAAI/2008/AAAI08-041.pdf pdf] » [[General Game Playing]]
+
* [[Hilmar Finnsson]], [[Yngvi Björnsson]]. ('''2008'''). ''Simulation-Based Approach to General Game Playing.'' In The Twenty-Third AAAI Conference on Artificial Intelligence, [[AAAI]] Press, 2008. Accepted. [http://www.ru.is/faculty/yngvi/pdf/FinnssonB08a.pdf pdf], [http://www.aaai.org/Papers/AAAI/2008/AAAI08-041.pdf pdf] » [[General Game Playing]]
 
* [[Jean Méhat]], [[Tristan Cazenave]] ('''2008'''). ''Monte-Carlo Tree Search for General Game Playing''. [http://www.lamsade.dauphine.fr/~cazenave/papers/ggp2008.pdf pdf] » [[General Game Playing]]
 
* [[Jean Méhat]], [[Tristan Cazenave]] ('''2008'''). ''Monte-Carlo Tree Search for General Game Playing''. [http://www.lamsade.dauphine.fr/~cazenave/papers/ggp2008.pdf pdf] » [[General Game Playing]]
 
* [[Tristan Cazenave]], [[Nicolas Jouandeau]] ('''2008'''). ''A Parallel Monte-Carlo Tree Search Algorithm''. [http://www.lamsade.dauphine.fr/%7Ecazenave/papers/parallelMCTS.pdf pdf]
 
* [[Tristan Cazenave]], [[Nicolas Jouandeau]] ('''2008'''). ''A Parallel Monte-Carlo Tree Search Algorithm''. [http://www.lamsade.dauphine.fr/%7Ecazenave/papers/parallelMCTS.pdf pdf]
Line 97: Line 97:
 
* [[Guillaume Chaslot]], [[Christophe Fiter]], [[Jean-Baptiste Hoock]], [[Arpad Rimmel]], [[Olivier Teytaud]] ('''2009'''). ''Adding Expert Knowledge and Exploration in Monte-Carlo Tree Search''. [[Advances in Computer Games 12]], [http://www.personeel.unimaas.nl/g-chaslot/papers/acg09.pdf pdf], [http://www.lri.fr/%7Erimmel/publi/EK_explo.pdf pdf]
 
* [[Guillaume Chaslot]], [[Christophe Fiter]], [[Jean-Baptiste Hoock]], [[Arpad Rimmel]], [[Olivier Teytaud]] ('''2009'''). ''Adding Expert Knowledge and Exploration in Monte-Carlo Tree Search''. [[Advances in Computer Games 12]], [http://www.personeel.unimaas.nl/g-chaslot/papers/acg09.pdf pdf], [http://www.lri.fr/%7Erimmel/publi/EK_explo.pdf pdf]
 
* [[Guillaume Chaslot]], [[Jean-Baptiste Hoock]], [[Julien Pérez]], [[Arpad Rimmel]], [[Olivier Teytaud]], [[Mark Winands]] ('''2009'''). ''Meta Monte-Carlo Tree Search for Automatic Opening Book Generation''. [http://www.personeel.unimaas.nl/m-winands/documents/ouvertures9x9.pdf pdf]
 
* [[Guillaume Chaslot]], [[Jean-Baptiste Hoock]], [[Julien Pérez]], [[Arpad Rimmel]], [[Olivier Teytaud]], [[Mark Winands]] ('''2009'''). ''Meta Monte-Carlo Tree Search for Automatic Opening Book Generation''. [http://www.personeel.unimaas.nl/m-winands/documents/ouvertures9x9.pdf pdf]
* [[Markus Enzenberger]] and [[Martin Müller]] ('''2009'''). ''A lock-free multithreaded Monte-Carlo tree search algorithm'', [[Advances in Computer Games 12]], [http://webdocs.cs.ualberta.ca/%7Emmueller/ps/enzenberger-mueller-acg12.pdf pdf]
+
* [[Markus Enzenberger]], [[Martin Müller]] ('''2009'''). ''A lock-free multithreaded Monte-Carlo tree search algorithm'', [[Advances in Computer Games 12]], [http://webdocs.cs.ualberta.ca/%7Emmueller/ps/enzenberger-mueller-acg12.pdf pdf]
* [[Markus Enzenberger]] and [[Martin Müller]] ('''2009'''). ''[http://www.cs.ualberta.ca/research/theses-publications/technical-reports/2009/tr09-08 Fuego - An Open-source Framework for Board Games and Go Engine Based on Monte-Carlo Tree Search]'', [http://www.cs.ualberta.ca/system/files/tech_report/2009/TR09-08.pdf pdf]
 
 
* [[Rémi Coulom]] ('''2009'''). ''The Monte-Carlo Revolution in Go''. JFFoS'2008: Japanese-French Frontiers of Science Symposium, [http://remi.coulom.free.fr/JFFoS/JFFoS.pdf slides as pdf]
 
* [[Rémi Coulom]] ('''2009'''). ''The Monte-Carlo Revolution in Go''. JFFoS'2008: Japanese-French Frontiers of Science Symposium, [http://remi.coulom.free.fr/JFFoS/JFFoS.pdf slides as pdf]
* [[Mark Winands]] and [[Yngvi Björnsson]] ('''2009'''). ''Evaluation Function Based Monte-Carlo LOA''. [http://www.ru.is/faculty/yngvi/pdf/WinandsB09.pdf pdf] <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=886 Monte Carlo in LOA] by [[Mark Watkins]], [[Computer Chess Forums|Open Chess Forum]], December 30, 2010</ref>  
+
* [[Mark Winands]], [[Yngvi Björnsson]] ('''2009'''). ''Evaluation Function Based Monte-Carlo LOA''. [http://www.ru.is/faculty/yngvi/pdf/WinandsB09.pdf pdf] <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=886 Monte Carlo in LOA] by [[Mark Watkins]], [[Computer Chess Forums|Open Chess Forum]], December 30, 2010</ref>  
 
* [[Tristan Cazenave]] ('''2009'''). ''Nested Monte-Carlo Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai2009.html#Cazenave09 IJCAI 2009], [http://www.lamsade.dauphine.fr/~cazenave/papers/nested.pdf pdf]
 
* [[Tristan Cazenave]] ('''2009'''). ''Nested Monte-Carlo Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai2009.html#Cazenave09 IJCAI 2009], [http://www.lamsade.dauphine.fr/~cazenave/papers/nested.pdf pdf]
 
* [[Paolo Ciancarini]], [[Gian Piero Favini]] ('''2009'''). ''Monte Carlo Tree Search Techniques in the Game of Kriegspiel''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai2009.html IJCAI 2009], [http://ijcai.org/papers09/Papers/IJCAI09-086.pdf pdf] » [[KriegSpiel]]
 
* [[Paolo Ciancarini]], [[Gian Piero Favini]] ('''2009'''). ''Monte Carlo Tree Search Techniques in the Game of Kriegspiel''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai2009.html IJCAI 2009], [http://ijcai.org/papers09/Papers/IJCAI09-086.pdf pdf] » [[KriegSpiel]]
Line 114: Line 113:
 
==2010 ...==  
 
==2010 ...==  
 
* [[Julien Kloetzer]] ('''2010'''). ''[https://dspace.jaist.ac.jp/dspace/handle/10119/8867?locale=en Monte-Carlo Techniques: Applications to the Game of the Amazons]''. Ph.D. thesis, [[JAIST]]
 
* [[Julien Kloetzer]] ('''2010'''). ''[https://dspace.jaist.ac.jp/dspace/handle/10119/8867?locale=en Monte-Carlo Techniques: Applications to the Game of the Amazons]''. Ph.D. thesis, [[JAIST]]
* [[Yoshikuni Sato]], [[Daisuke Takahashi]] and [[Reijer Grimbergen]] ('''2010'''). ''A Shogi Program based on Monte-Carlo Tree Search''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]
+
* [[Yoshikuni Sato]], [[Daisuke Takahashi]], [[Reijer Grimbergen]] ('''2010'''). ''A Shogi Program based on Monte-Carlo Tree Search''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]
 
* [[Richard J. Lorentz]] ('''2010'''). ''[http://www.springerlink.com/content/p4x16832317r1214/ Improving Monte-Carlo Tree Search in Havannah]''. [[CG 2010]]
 
* [[Richard J. Lorentz]] ('''2010'''). ''[http://www.springerlink.com/content/p4x16832317r1214/ Improving Monte-Carlo Tree Search in Havannah]''. [[CG 2010]]
 
* [[Amine Bourki]], [[Guillaume Chaslot]], [[Matthieu Coulm]], [[Vincent Danjean]], [[Hassen Doghmen]], [[Thomas Hérault]], [[Jean-Baptiste Hoock]], [[Arpad Rimmel]], [[Fabien Teytaud]], [[Olivier Teytaud]], [[Paul Vayssière]], [[Ziqin Yu]] ('''2010'''). ''[http://hal.inria.fr/inria-00512854/en/ Scalability and Parallelization of Monte-Carlo Tree Search]''. [[CG 2010]], [http://hal.inria.fr/docs/00/51/28/54/PDF/newcluster.pdf pdf]
 
* [[Amine Bourki]], [[Guillaume Chaslot]], [[Matthieu Coulm]], [[Vincent Danjean]], [[Hassen Doghmen]], [[Thomas Hérault]], [[Jean-Baptiste Hoock]], [[Arpad Rimmel]], [[Fabien Teytaud]], [[Olivier Teytaud]], [[Paul Vayssière]], [[Ziqin Yu]] ('''2010'''). ''[http://hal.inria.fr/inria-00512854/en/ Scalability and Parallelization of Monte-Carlo Tree Search]''. [[CG 2010]], [http://hal.inria.fr/docs/00/51/28/54/PDF/newcluster.pdf pdf]
Line 128: Line 127:
 
* [[Jean Méhat]], [[Tristan Cazenave]] ('''2010'''). ''Combining UCT and Nested Monte-Carlo Search for Single-Player General Game Playing''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://www.lamsade.dauphine.fr/~cazenave/papers/ggp2009.pdf pdf 2009] » [[General Game Playing]]
 
* [[Jean Méhat]], [[Tristan Cazenave]] ('''2010'''). ''Combining UCT and Nested Monte-Carlo Search for Single-Player General Game Playing''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://www.lamsade.dauphine.fr/~cazenave/papers/ggp2009.pdf pdf 2009] » [[General Game Playing]]
 
* [[Broderick Arneson]], [[Ryan Hayward]], [[Philip Henderson]] ('''2010'''). ''Monte Carlo Tree Search in Hex''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://webdocs.cs.ualberta.ca/~hayward/papers/mcts-hex.pdf pdf]
 
* [[Broderick Arneson]], [[Ryan Hayward]], [[Philip Henderson]] ('''2010'''). ''Monte Carlo Tree Search in Hex''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://webdocs.cs.ualberta.ca/~hayward/papers/mcts-hex.pdf pdf]
 +
* [[Mark Winands]], [[Yngvi Björnsson]], [[Jahn-Takeshi Saito]] ('''2010'''). ''[https://ieeexplore.ieee.org/document/5523941 Monte Carlo Tree Search in Lines of Action]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://www.ru.is/~yngvi/pdf/WinandsB10a.pdf pdf]
 
* [[Hendrik Baier]], [[Peter D. Drake]] ('''2010'''). ''The power of forgetting: Improving the last-good-reply policy in Monte Carlo Go''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4
 
* [[Hendrik Baier]], [[Peter D. Drake]] ('''2010'''). ''The power of forgetting: Improving the last-good-reply policy in Monte Carlo Go''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4
 
* [[Ingo Althöfer]] ('''2010'''). ''Game Self-Play with Pure Monte-Carlo: The Basin Structure''. [http://www.althofer.de/monte-carlo-basins-althoefer.pdf pdf]
 
* [[Ingo Althöfer]] ('''2010'''). ''Game Self-Play with Pure Monte-Carlo: The Basin Structure''. [http://www.althofer.de/monte-carlo-basins-althoefer.pdf pdf]
Line 137: Line 137:
 
* [[Thomas J. Walsh]], [[Sergiu Goschin]], [[Michael L. Littman]] ('''2010'''). ''Integrating sample-based planning and model-based reinforcement learning.'' [[AAAI]], [https://pdfs.semanticscholar.org/bdc9/bfb6ecc6fb5afb684df03d7220c46ebdbf4e.pdf pdf] » [[UCT]], [[Reinforcement Learning]]
 
* [[Thomas J. Walsh]], [[Sergiu Goschin]], [[Michael L. Littman]] ('''2010'''). ''Integrating sample-based planning and model-based reinforcement learning.'' [[AAAI]], [https://pdfs.semanticscholar.org/bdc9/bfb6ecc6fb5afb684df03d7220c46ebdbf4e.pdf pdf] » [[UCT]], [[Reinforcement Learning]]
 
'''2011'''
 
'''2011'''
 +
* [[Markus Enzenberger]], [[Martin Müller]], [[Broderick Arneson]], [[Richard Segal]] ('''2011'''). ''Fuego - An Open-source Framework for Board Games and Go Engine Based on Monte-Carlo Tree Search''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [https://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf pdf]
 
* [[Christopher D. Rosin]] ('''2011'''). ''[https://link.springer.com/article/10.1007/s10472-011-9258-6 Multi-armed bandits with episode context]''. Annals of Mathematics and Artificial Intelligence, Vol. 61, No. 3, [http://gauss.ececs.uc.edu/Workshops/isaim2010/papers/rosin.pdf ISAIM 2010 pdf]
 
* [[Christopher D. Rosin]] ('''2011'''). ''[https://link.springer.com/article/10.1007/s10472-011-9258-6 Multi-armed bandits with episode context]''. Annals of Mathematics and Artificial Intelligence, Vol. 61, No. 3, [http://gauss.ececs.uc.edu/Workshops/isaim2010/papers/rosin.pdf ISAIM 2010 pdf]
 
* [[Shih-Chieh Huang]], [[Rémi Coulom]], [[Shun-Shii Lin]] ('''2011'''). ''Time Management for Monte-Carlo Tree Search Applied to the Game of Go''. TAAI 2010, [http://remi.coulom.free.fr/Publications/TimeManagement.pdf pdf]
 
* [[Shih-Chieh Huang]], [[Rémi Coulom]], [[Shun-Shii Lin]] ('''2011'''). ''Time Management for Monte-Carlo Tree Search Applied to the Game of Go''. TAAI 2010, [http://remi.coulom.free.fr/Publications/TimeManagement.pdf pdf]
Line 167: Line 168:
 
* [[Joel Veness]], [[Kee Siong Ng]], [[Marcus Hutter]], [[William Uther]] , [[David Silver]] ('''2011'''). ''A Monte-Carlo AIXI Approximation''. [https://en.wikipedia.org/wiki/Journal_of_Artificial_Intelligence_Research JAIR], Vol. 40, [http://www.aaai.org/Papers/JAIR/Vol40/JAIR-4004.pdf pdf]
 
* [[Joel Veness]], [[Kee Siong Ng]], [[Marcus Hutter]], [[William Uther]] , [[David Silver]] ('''2011'''). ''A Monte-Carlo AIXI Approximation''. [https://en.wikipedia.org/wiki/Journal_of_Artificial_Intelligence_Research JAIR], Vol. 40, [http://www.aaai.org/Papers/JAIR/Vol40/JAIR-4004.pdf pdf]
 
* [[Christopher D. Rosin]] ('''2011'''). '' Nested Rollout Policy Adaptation for Monte Carlo Tree Search''. [[Conferences#IJCAI2011|IJCAI 2011]], [http://www.chrisrosin.com/rosin-ijcai11.pdf pdf]
 
* [[Christopher D. Rosin]] ('''2011'''). '' Nested Rollout Policy Adaptation for Monte Carlo Tree Search''. [[Conferences#IJCAI2011|IJCAI 2011]], [http://www.chrisrosin.com/rosin-ijcai11.pdf pdf]
 +
* [[David Tolpin]], [[Solomon Eyal Shimony]] ('''2011'''). ''Doing Better Than UCT: Rational Monte Carlo Sampling in Trees''. [https://arxiv.org/abs/1108.3711 arXiv:1108.3711] » [[UCT]]
 
'''2012'''
 
'''2012'''
 
* [[Michael L. Littman]] ('''2012'''). ''Technical Perspective: A New Way to Search Game Trees''. [[ACM#Communications|Communications of the ACM]], Vol. 55, No. 3
 
* [[Michael L. Littman]] ('''2012'''). ''Technical Perspective: A New Way to Search Game Trees''. [[ACM#Communications|Communications of the ACM]], Vol. 55, No. 3
Line 172: Line 174:
 
* [[Oleg Arenz]] ('''2012'''). ''Monte Carlo Chess''.  B.Sc. thesis, [[Darmstadt University of Technology]], advisor [[Johannes Fürnkranz]], [http://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf pdf] » [[Stockfish]]
 
* [[Oleg Arenz]] ('''2012'''). ''Monte Carlo Chess''.  B.Sc. thesis, [[Darmstadt University of Technology]], advisor [[Johannes Fürnkranz]], [http://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf pdf] » [[Stockfish]]
 
* [[Jeff Rollason]] ('''2012'''). ''[http://www.aifactory.co.uk/newsletter/2012_01_tuning_spades.htm Tuning Spades]''. [[AI Factory]], Summer 2012 » [[UCT]]
 
* [[Jeff Rollason]] ('''2012'''). ''[http://www.aifactory.co.uk/newsletter/2012_01_tuning_spades.htm Tuning Spades]''. [[AI Factory]], Summer 2012 » [[UCT]]
 +
* [[David Tolpin]], [[Solomon Eyal Shimony]] ('''2012'''). ''MCTS Based on Simple Regret''. [[Conferences#AAAI-2012|AAAI-2012]], [https://arxiv.org/abs/1207.5536 arXiv:1207.5536]
 +
* [[David Tolpin]], [[Solomon Eyal Shimony]] ('''2012'''). ''VOI-aware MCTS''. [https://dblp.uni-trier.de/db/conf/ecai/ecai2012.html ECAI 2012], [https://arxiv.org/abs/1207.5589  arXiv:1207.5589] <ref>[https://en.wikipedia.org/wiki/Value_of_information Value of information (VOI) from Wikipedia]</ref>
 
* [[Tristan Cazenave]], [[Fabien Teytaud]] ('''2012'''). ''Beam Nested Rollout Policy Adaptation''. [[ECAI CGW 2012]]
 
* [[Tristan Cazenave]], [[Fabien Teytaud]] ('''2012'''). ''Beam Nested Rollout Policy Adaptation''. [[ECAI CGW 2012]]
 
* [[André Fabbri]], [[Frédéric Armetta]], [[Eric Duchêne]], [[Salima Hassas]] ('''2012'''). ''A new self-acquired knowledge process for Monte Carlo Tree Search''. [[ECAI CGW 2012]]
 
* [[André Fabbri]], [[Frédéric Armetta]], [[Eric Duchêne]], [[Salima Hassas]] ('''2012'''). ''A new self-acquired knowledge process for Monte Carlo Tree Search''. [[ECAI CGW 2012]]
 
* [[Marc Lanctot]], [[Abdallah Saffidine]], [[Joel Veness]], [[Christopher Archibald]] ('''2012'''). ''Sparse Sampling for Adversarial Games''. [[ECAI CGW 2012]]
 
* [[Marc Lanctot]], [[Abdallah Saffidine]], [[Joel Veness]], [[Christopher Archibald]] ('''2012'''). ''Sparse Sampling for Adversarial Games''. [[ECAI CGW 2012]]
 
* [[Niek Den Teuling]], [[Mark Winands]] ('''2012'''). ''Monte-Carlo Tree Search for the Simultaneous Move Game Tron''. [[ECAI CGW 2012]], [https://dke.maastrichtuniversity.nl/m.winands/documents/Tronpaper.pdf pdf]
 
* [[Niek Den Teuling]], [[Mark Winands]] ('''2012'''). ''Monte-Carlo Tree Search for the Simultaneous Move Game Tron''. [[ECAI CGW 2012]], [https://dke.maastrichtuniversity.nl/m.winands/documents/Tronpaper.pdf pdf]
 +
* [[Arthur Guez]], [[David Silver]], [[Peter Dayan]] ('''2012'''). ''Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search''. [https://arxiv.org/abs/1205.3109 arXiv:1205.3109]
 +
* [[Truong-Huy Dinh Nguyen]], [[Wee Sun Lee]], [[Tze-Yun Leong]] ('''2012'''). ''Bootstrapping Monte Carlo Tree Search with an Imperfect Heuristic''. [https://arxiv.org/abs/1206.5940 arXiv:1206.5940]
 
* [[Jan Kuipers (Nikhef)|Jan Kuipers]], [[Aske Plaat]], [[Jos Vermaseren]], [[Jaap van den Herik]] ('''2012'''). ''Improving multivariate Horner schemes with Monte Carlo tree search''. [http://arxiv.org/abs/1207.7079 CoRR abs/1207.7079]
 
* [[Jan Kuipers (Nikhef)|Jan Kuipers]], [[Aske Plaat]], [[Jos Vermaseren]], [[Jaap van den Herik]] ('''2012'''). ''Improving multivariate Horner schemes with Monte Carlo tree search''. [http://arxiv.org/abs/1207.7079 CoRR abs/1207.7079]
 
* [[Cameron Browne]], [[Edward Powley]], [[Daniel Whitehouse]], [[Simon Lucas]], [[Peter Cowling]], [[Philipp Rohlfshagen]], [[Stephen Tavener]], [[Diego Perez]], [[Spyridon Samothrakis]], [[Simon Colton]] ('''2012'''). ''[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6145622&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4804728%2F6169178%2F06145622.pdf%3Farnumber%3D6145622 A Survey of Monte Carlo Tree Search Methods]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 4, No. 1
 
* [[Cameron Browne]], [[Edward Powley]], [[Daniel Whitehouse]], [[Simon Lucas]], [[Peter Cowling]], [[Philipp Rohlfshagen]], [[Stephen Tavener]], [[Diego Perez]], [[Spyridon Samothrakis]], [[Simon Colton]] ('''2012'''). ''[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6145622&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4804728%2F6169178%2F06145622.pdf%3Farnumber%3D6145622 A Survey of Monte Carlo Tree Search Methods]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 4, No. 1
Line 182: Line 188:
 
* [[Hendrik Baier]], [[Mark Winands]] ('''2012'''). ''Beam Monte-Carlo Tree Search''. [[IEEE#CIG|IEEE CIG 2012]], [https://dke.maastrichtuniversity.nl/m.winands/documents/CIG2012_paper_32.pdf pdf]
 
* [[Hendrik Baier]], [[Mark Winands]] ('''2012'''). ''Beam Monte-Carlo Tree Search''. [[IEEE#CIG|IEEE CIG 2012]], [https://dke.maastrichtuniversity.nl/m.winands/documents/CIG2012_paper_32.pdf pdf]
 
* [[Thomas Philip Runarsson]], [[Marc Schoenauer]], [[Michèle Sebag]] ('''2012'''). ''Pilot, Rollout and Monte Carlo Tree Search Methods for Job Shop Scheduling''. [https://arxiv.org/abs/1210.0374 arXiv:1210.0374]
 
* [[Thomas Philip Runarsson]], [[Marc Schoenauer]], [[Michèle Sebag]] ('''2012'''). ''Pilot, Rollout and Monte Carlo Tree Search Methods for Job Shop Scheduling''. [https://arxiv.org/abs/1210.0374 arXiv:1210.0374]
* [[Adrien Couetoux]], [[Olivier Teytaud]], [[Hassen Doghmen]] ('''2012'''). ''Learning a Move-Generator for Upper Confidence Trees''. [http://ics2012.ndhu.edu.tw/ ICS 2012], [https://en.wikipedia.org/wiki/Hualien_City Hualien], [https://en.wikipedia.org/wiki/Taiwan Taiwan], December 2012
+
* [[Adrien Couetoux]], [[Olivier Teytaud]], [[Hassen Doghmen]] ('''2012'''). ''Learning a Move-Generator for Upper Confidence Trees''. [http://ics2012.ndhu.edu.tw/ ICS 2012], [https://en.wikipedia.org/wiki/Hualien_City Hualien]
 +
* [[Haruhiko Akiyama]], [[Kanako Komiya]], [[Yoshiyuki Kotani]] ('''2012'''). ''[https://www.sciencedirect.com/science/article/abs/pii/S0950705111002516 Nested Monte-Carlo Search with simulation reduction]''. [https://en.wikipedia.org/wiki/Knowledge-Based_Systems_(journal) Knowledge-Based Systems], Vol. 34 <ref>[https://en.wikipedia.org/wiki/Join_Five Morpion solitaire from Wikipedia]</ref> <ref>[http://www.morpionsolitaire.com/English/RecordsGrids5T.htm Morpion Solitaire - Record Grids (5T game)]</ref>
 
'''2013'''
 
'''2013'''
 
* [[Cheng-Wei Chou]], [[Ping-Chiang Chou]], [[Chang-Shing Lee]], [[David L. Saint-Pierre]], [[Olivier Teytaud]], [[Mei-Hui Wang]], [[Li-Wen Wu]], [[Shi-Jim Yen]] ('''2013'''). ''Strategic Choices: Small Budgets and Simple Regret''. [[TAAI|TAAI 2012]], [http://www.csie.ndhu.edu.tw/csieweb/en/node/685 Excellent Paper Award], [https://hal.inria.fr/hal-00753145v2/document pdf]
 
* [[Cheng-Wei Chou]], [[Ping-Chiang Chou]], [[Chang-Shing Lee]], [[David L. Saint-Pierre]], [[Olivier Teytaud]], [[Mei-Hui Wang]], [[Li-Wen Wu]], [[Shi-Jim Yen]] ('''2013'''). ''Strategic Choices: Small Budgets and Simple Regret''. [[TAAI|TAAI 2012]], [http://www.csie.ndhu.edu.tw/csieweb/en/node/685 Excellent Paper Award], [https://hal.inria.fr/hal-00753145v2/document pdf]
Line 205: Line 212:
 
* [[Timothy Furtak]], [[Michael Buro]] ('''2013'''). ''Recursive Monte Carlo search for imperfect information games''. [[IEEE#CIG|CIG 2013]], [https://skatgame.net/mburo/ps/recmc13.pdf pdf]
 
* [[Timothy Furtak]], [[Michael Buro]] ('''2013'''). ''Recursive Monte Carlo search for imperfect information games''. [[IEEE#CIG|CIG 2013]], [https://skatgame.net/mburo/ps/recmc13.pdf pdf]
 
* [[Ben Ruijl]], [[Jos Vermaseren]], [[Aske Plaat]], [[Jaap van den Herik]] ('''2013'''). ''Combining Simulated Annealing and Monte Carlo Tree Search for Expression Simplification''. [http://arxiv.org/abs/1312.0841 CoRR abs/1312.0841]
 
* [[Ben Ruijl]], [[Jos Vermaseren]], [[Aske Plaat]], [[Jaap van den Herik]] ('''2013'''). ''Combining Simulated Annealing and Monte Carlo Tree Search for Expression Simplification''. [http://arxiv.org/abs/1312.0841 CoRR abs/1312.0841]
* [[Arthur Guez]], [[David Silver]], [[Peter Dayan]] ('''2013'''). ''Scalable and Efficient Bayes-Adaptive Reinforcement Learning Based on Monte-Carlo Tree Search''. [https://en.wikipedia.org/wiki/Journal_of_Artificial_Intelligence_Research Journal of Artificial Intelligence Research], Vol. 48, [https://www.jair.org/media/4117/live-4117-7507-jair.pdf pdf]
+
* [[Arthur Guez]], [[David Silver]], [[Peter Dayan]] ('''2013'''). ''[https://www.jair.org/index.php/jair/article/view/10853 Scalable and Efficient Bayes-Adaptive Reinforcement Learning Based on Monte-Carlo Tree Search]''. [https://en.wikipedia.org/wiki/Journal_of_Artificial_Intelligence_Research Journal of Artificial Intelligence Research], Vol. 48
 
* [[Ari Weinstein]], [[Michael L. Littman]], [[Sergiu Goschin]] ('''2013'''). ''[http://proceedings.mlr.press/v24/weinstein12a.html Rollout-based Game-tree Search Outprunes Traditional Alpha-beta]''. [http://proceedings.mlr.press/ PMLR], Vol. 24 » [[UCT]]
 
* [[Ari Weinstein]], [[Michael L. Littman]], [[Sergiu Goschin]] ('''2013'''). ''[http://proceedings.mlr.press/v24/weinstein12a.html Rollout-based Game-tree Search Outprunes Traditional Alpha-beta]''. [http://proceedings.mlr.press/ PMLR], Vol. 24 » [[UCT]]
 +
* [[Kuo-Yuan Kao]], [[I-Chen Wu]], [[Shi-Jim Yen]], [[Yi-Chang Shan]] ('''2013'''). ''[https://ieeexplore.ieee.org/document/6468079 Incentive Learning in Monte Carlo Tree Search]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 5, No. 4
 
'''2014'''
 
'''2014'''
 
* [[Ben Ruijl]], [[Jos Vermaseren]], [[Aske Plaat]], [[Jaap van den Herik]] ('''2014'''). ''HEPGAME and the Simplification of Expressions''. [http://arxiv.org/abs/1405.6369 CoRR abs/1405.6369]
 
* [[Ben Ruijl]], [[Jos Vermaseren]], [[Aske Plaat]], [[Jaap van den Herik]] ('''2014'''). ''HEPGAME and the Simplification of Expressions''. [http://arxiv.org/abs/1405.6369 CoRR abs/1405.6369]
Line 234: Line 242:
 
* [[Jeff Rollason]] ('''2015'''). ''[http://www.aifactory.co.uk/newsletter/2015_02_mixing_immiscible.htm Mixing the Immiscible - MCTS and evaluation]''. [[AI Factory]], October 2015 <ref>[[Guillaume Chaslot]], [[Mark Winands]], [[Jos Uiterwijk]], [[Jaap van den Herik]], [[Bruno Bouzy]] ('''2008'''). ''Progressive Strategies for Monte-Carlo Tree Search''. [http://www.worldscinet.com/nmnc/nmnc.shtml New Mathematics and Natural Computation], Vol. 4, No. 3, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3015&rep=rep1&type=pdf pdf]</ref>
 
* [[Jeff Rollason]] ('''2015'''). ''[http://www.aifactory.co.uk/newsletter/2015_02_mixing_immiscible.htm Mixing the Immiscible - MCTS and evaluation]''. [[AI Factory]], October 2015 <ref>[[Guillaume Chaslot]], [[Mark Winands]], [[Jos Uiterwijk]], [[Jaap van den Herik]], [[Bruno Bouzy]] ('''2008'''). ''Progressive Strategies for Monte-Carlo Tree Search''. [http://www.worldscinet.com/nmnc/nmnc.shtml New Mathematics and Natural Computation], Vol. 4, No. 3, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3015&rep=rep1&type=pdf pdf]</ref>
 
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2015'''). ''Scaling Monte Carlo Tree Search on Intel Xeon Phi''. [http://arxiv.org/abs/1507.04383 CoRR abs/1507.04383] » [[Hex]], [[Parallel Search]], [[x86-64]]
 
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2015'''). ''Scaling Monte Carlo Tree Search on Intel Xeon Phi''. [http://arxiv.org/abs/1507.04383 CoRR abs/1507.04383] » [[Hex]], [[Parallel Search]], [[x86-64]]
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2015'''). ''Parallel Monte Carlo Tree Search from Multi-core to Many-core Processors''. [https://whova.com/portal/ieeet_201508/ TrustCom/BigDataSE/|ISPA 2015], [https://askeplaat.files.wordpress.com/2013/01/ispa2015.pdf pdf]
+
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2015'''). ''Parallel Monte Carlo Tree Search from Multi-core to Many-core Processors''. [https://whova.com/portal/ieeet_201508/ TrustCom/BigDataSE/ISPA 2015], [https://askeplaat.files.wordpress.com/2013/01/ispa2015.pdf pdf]
 
* [[Peter H. Jin]], [[Kurt Keutzer]] ('''2015'''). ''Convolutional Monte Carlo Rollouts in Go''. [http://arxiv.org/abs/1512.03375 arXiv:1512.03375]
 
* [[Peter H. Jin]], [[Kurt Keutzer]] ('''2015'''). ''Convolutional Monte Carlo Rollouts in Go''. [http://arxiv.org/abs/1512.03375 arXiv:1512.03375]
 
* [[Naoki Mizukami]], [[Yoshimasa Tsuruoka]] ('''2015'''). ''Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models''. [[IEEE#TOCIAIGAMES|IEEE CIG 2015]], [http://www.logos.ic.i.u-tokyo.ac.jp/~mizukami/paper/cig_2015.pdf pdf]
 
* [[Naoki Mizukami]], [[Yoshimasa Tsuruoka]] ('''2015'''). ''Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models''. [[IEEE#TOCIAIGAMES|IEEE CIG 2015]], [http://www.logos.ic.i.u-tokyo.ac.jp/~mizukami/paper/cig_2015.pdf pdf]
Line 249: Line 257:
 
* [[Katsuki Ohto]], [[Tetsuro Tanaka]] ('''2016'''). ''Application of Monte Carlo Tree Search to Curling AI''. [[Conferences#GPW21|21st Game Programming Workshop]]
 
* [[Katsuki Ohto]], [[Tetsuro Tanaka]] ('''2016'''). ''Application of Monte Carlo Tree Search to Curling AI''. [[Conferences#GPW21|21st Game Programming Workshop]]
 
* [[Maciej Świechowski]], [[Jacek Mańdziuk]] ('''2016'''). ''A Hybrid Approach to Parallelization of Monte Carlo Tree Search in General Game Playing''. [https://www.springer.com/de/book/9783319301648 Challenging Problems and Solutions in Intelligent Systems], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
 
* [[Maciej Świechowski]], [[Jacek Mańdziuk]] ('''2016'''). ''A Hybrid Approach to Parallelization of Monte Carlo Tree Search in General Game Playing''. [https://www.springer.com/de/book/9783319301648 Challenging Problems and Solutions in Intelligent Systems], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
 +
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2016'''). ''A New Method for Parallel Monte Carlo Tree Search''. [https://arxiv.org/abs/1605.04447 arXiv:1605.04447] » [[Parallel Search]]
 +
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2016'''). ''An Efficient Computation Pattern for Parallel MCTS''. [http://www.ictopen.nl/content/Previous+editions ICT.OPEN 2016], [http://liacs.leidenuniv.nl/~plaata1/papers/ictopen2016.pdf pdf]
 +
* [[David L. St-Pierre]], [[Jean-Baptiste Hoock]], [[Jialin Liu]], [[Fabien Teytaud]], [[Olivier Teytaud]] ('''2016'''). ''Automatically Reinforcing a Game AI''. [https://arxiv.org/abs/1607.08100 arXiv:1607.0810]
 +
* [[Tristan Cazenave]], [[Abdallah Saffidine]], [[Michael Schofield]], [[Michael Thielscher]] ('''2016'''). ''Nested Monte Carlo Search for Two-Player Games''. [[Conferences#AAAI-2016|AAAI 2016]], [https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12134/11652 pdf]
 
'''2017'''
 
'''2017'''
 
* [[Dap Hartmann]] ('''2017'''). ''Let's Catch the Train to Monte-Carlo''. [[ICGA Journal#39_1|ICGA Journal, Vol. 39, No. 1]], Review on [[Hendrik Baier#PhD|Hendrik Baier's Ph.D. thesis]]
 
* [[Dap Hartmann]] ('''2017'''). ''Let's Catch the Train to Monte-Carlo''. [[ICGA Journal#39_1|ICGA Journal, Vol. 39, No. 1]], Review on [[Hendrik Baier#PhD|Hendrik Baier's Ph.D. thesis]]
 +
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2017'''). ''Structured Parallel Programming for Monte Carlo Tree Search''. [https://arxiv.org/abs/1704.00325 arXiv:1704.00325]
 +
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]], [[Jos Vermaseren]] ('''2017'''). ''An Analysis of Virtual Loss in Parallel MCTS''. [https://dblp.uni-trier.de/db/conf/icaart/icaart2017-2.html ICAART 2017], Vol. 2, [http://liacs.leidenuniv.nl/~plaata1/papers/paper_ICAART17.pdf pdf]
 
* [[Katsuki Ohto]], [[Tetsuro Tanaka]] ('''2017'''). ''A Curling Agent Based on the Monte-Carlo Tree Search Considering the Similarity of the Best Action among Similar States''. [[Advances in Computer Games 15]]
 
* [[Katsuki Ohto]], [[Tetsuro Tanaka]] ('''2017'''). ''A Curling Agent Based on the Monte-Carlo Tree Search Considering the Similarity of the Best Action among Similar States''. [[Advances in Computer Games 15]]
 
* [[Naoki Mizukami]], [[Jun Suzuki]], [[Hirotaka Kameko]], [[Yoshimasa Tsuruoka]] ('''2017'''). ''Exploration Bonuses Based on Upper Confidence Bounds for Sparse Reward Games''. [[Advances in Computer Games 15]]
 
* [[Naoki Mizukami]], [[Jun Suzuki]], [[Hirotaka Kameko]], [[Yoshimasa Tsuruoka]] ('''2017'''). ''Exploration Bonuses Based on Upper Confidence Bounds for Sparse Reward Games''. [[Advances in Computer Games 15]]
Line 260: Line 274:
 
'''2018'''
 
'''2018'''
 
* [[Arthur Guez]], [[Théophane Weber]], [[Ioannis Antonoglou]], [[Karen Simonyan]], [[Oriol Vinyals]], [[Daan Wierstra]], [[Rémi Munos]], [[David Silver]] ('''2018'''). ''Learning to Search with MCTSnets''. [https://arxiv.org/abs/1802.04697 arXiv:1802.04697]
 
* [[Arthur Guez]], [[Théophane Weber]], [[Ioannis Antonoglou]], [[Karen Simonyan]], [[Oriol Vinyals]], [[Daan Wierstra]], [[Rémi Munos]], [[David Silver]] ('''2018'''). ''Learning to Search with MCTSnets''. [https://arxiv.org/abs/1802.04697 arXiv:1802.04697]
 +
* [[Hui Wang]], [[Michael Emmerich]], [[Aske Plaat]] ('''2018'''). ''Monte Carlo Q-learning for General Game Playing''. [https://arxiv.org/abs/1802.05944 arXiv:1802.05944] » [[Reinforcement Learning]], [[General Game Playing]]
 
* [[Mark Winands]] ('''2018'''). ''[http://www.aifactory.co.uk/newsletter/2017_02_magic_montecarlo.htm The Magic of Monte-Carlo Tree Search]''. [[AI Factory]], January 2018
 
* [[Mark Winands]] ('''2018'''). ''[http://www.aifactory.co.uk/newsletter/2017_02_magic_montecarlo.htm The Magic of Monte-Carlo Tree Search]''. [[AI Factory]], January 2018
 
* [[Jacek Mańdziuk]] ('''2018'''). ''MCTS/UCT in Solving Real-Life Problems''. [https://www.springer.com/us/book/9783319679457 Advances in Data Analysis with Computational Intelligence Methods], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
 
* [[Jacek Mańdziuk]] ('''2018'''). ''MCTS/UCT in Solving Real-Life Problems''. [https://www.springer.com/us/book/9783319679457 Advances in Data Analysis with Computational Intelligence Methods], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
Line 266: Line 281:
 
* [[Chao Gao]], [[Martin Müller]], [[Ryan Hayward]] ('''2018'''). ''Three-Head Neural Network Architecture for Monte Carlo Tree Search''. [[Conferences#IJCAI2018|IJCAI 2018]]
 
* [[Chao Gao]], [[Martin Müller]], [[Ryan Hayward]] ('''2018'''). ''Three-Head Neural Network Architecture for Monte Carlo Tree Search''. [[Conferences#IJCAI2018|IJCAI 2018]]
 
* [[Tobias Joppen]], [[Christian Wirth]], [[Johannes Fürnkranz]] ('''2018'''). ''Preference-Based Monte Carlo Tree Search''. [https://arxiv.org/abs/1807.06286 arXiv:1807.06286]
 
* [[Tobias Joppen]], [[Christian Wirth]], [[Johannes Fürnkranz]] ('''2018'''). ''Preference-Based Monte Carlo Tree Search''. [https://arxiv.org/abs/1807.06286 arXiv:1807.06286]
 +
* [[S. Ali Mirsoleimani]], [[Jaap van den Herik]], [[Aske Plaat]], [[Jos Vermaseren]] ('''2018'''). ''Pipeline Pattern for Parallel MCTS''. [https://dblp.uni-trier.de/db/conf/icaart/icaart2018-2.html ICAART 2018], [http://liacs.leidenuniv.nl/~plaata1/papers/paper_ICAART18_pos.pdf pdf]
 +
* [[S. Ali Mirsoleimani]], [[Jaap van den Herik]], [[Aske Plaat]], [[Jos Vermaseren]] ('''2018'''). ''A Lock-free Algorithm for Parallel MCTS''. [https://dblp.uni-trier.de/db/conf/icaart/icaart2018-2.html ICAART 2018], [http://liacs.leidenuniv.nl/~plaata1/papers/paper_ICAART18.pdf pdf]
 +
* [[Ching-Nung Lin]], [[Jr-Chang Chen]], [[Shi-Jim Yen]], [[Chan-San Chen]] ('''2018'''). ''Design of a Block Go program using deep learning and Monte Carlo tree search''. [[ICGA Journal#40_3|ICGA Journal, Vol. 40, No. 3]]
 +
* [[Kiminori Matsuzaki]], [[Naoki Kitamura]] ('''2018'''). ''Do evaluation functions really improve Monte-Carlo tree search?'' [[CG 2018]], [[ICGA Journal#40_3|ICGA Journal, Vol. 40, No. 3]]
 +
* [[Shun-Shii Lin]], [[Chih-Hung Chen]], [[Yu-Heng Chen]], [[Wei-Lin Wu]] ('''2018'''). ''Some improvements in Monte Carlo tree search algorithms for sudden death games''. [[CG 2018]], [[ICGA Journal#40_4|ICGA Journal, Vol. 40, No. 4]]
 +
* [[Nai-Yuan Chang]], [[Chih-Hung Chen]], [[Shun-Shii Lin]], [[Surag Nair]]  ('''2018'''). ''[https://dl.acm.org/citation.cfm?id=3278325 The Big Win Strategy on Multi-Value Network: An Improvement over AlphaZero Approach for 6x6 Othello]''. [https://dl.acm.org/citation.cfm?id=3278312 MLMI2018]
 +
* [[Yen-Chi Chen]], [[Chih-Hung Chen]], [[Shun-Shii Lin]] ('''2018'''). ''[https://dl.acm.org/citation.cfm?id=3293486 Exact-Win Strategy for Overcoming AlphaZero]''. [https://dl.acm.org/citation.cfm?id=3293475 CIIS 2018]  <ref>[https://github.com/LeelaChessZero/lc0/issues/799 "Exact-Win Strategy for Overcoming AlphaZero" · Issue #799 · LeelaChessZero/lc0 · GitHub]</ref>
 
'''2019'''
 
'''2019'''
 
* [[Tobias Joppen]], [[Johannes Fürnkranz]] ('''2019'''). ''[https://www.groundai.com/project/ordinal-monte-carlo-tree-search/ Ordinal Monte Carlo Tree Search]''. [[Darmstadt University of Technology|TU Darmstadt]], [https://arxiv.org/abs/1901.04274 arXiv:1901.04274]
 
* [[Tobias Joppen]], [[Johannes Fürnkranz]] ('''2019'''). ''[https://www.groundai.com/project/ordinal-monte-carlo-tree-search/ Ordinal Monte Carlo Tree Search]''. [[Darmstadt University of Technology|TU Darmstadt]], [https://arxiv.org/abs/1901.04274 arXiv:1901.04274]
 +
* [[Herilalaina Rakotoarison]], [[Marc Schoenauer]], [[Michèle Sebag]] ('''2019'''). ''Automated Machine Learning with Monte-Carlo Tree Search''. [https://arxiv.org/abs/1906.00170 arXiv:1906.00170]
  
 
=Forum Posts=  
 
=Forum Posts=  
 
==2010 ...==
 
==2010 ...==
* [https://groups.google.com/d/msg/computer-go-archive/JrrSovvgTV0/UbPOufyTApQJ [Computer-go] learning patterns for mc go] by [[Hendrik Baier]], [https://groups.google.com/forum/#!forum/computer-go-archive Computer Go Archive], April 26, 2010
+
* [https://groups.google.com/d/msg/computer-go-archive/JrrSovvgTV0/UbPOufyTApQJ <nowiki>[Computer-go]</nowiki> learning patterns for mc go] by [[Hendrik Baier]], [https://groups.google.com/forum/#!forum/computer-go-archive Computer Go Archive], April 26, 2010
 
* [http://www.talkchess.com/forum/viewtopic.php?t=38554 UCT surprise for checkers !] by [[Daniel Shawul]], [[CCC]], March 25, 2011
 
* [http://www.talkchess.com/forum/viewtopic.php?t=38554 UCT surprise for checkers !] by [[Daniel Shawul]], [[CCC]], March 25, 2011
 
* [http://www.talkchess.com/forum/viewtopic.php?t=41730 MCTS without random playout?] by [[Antonio Torrecillas]], [[CCC]], January 01, 2012 » [[B*]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=41730 MCTS without random playout?] by [[Antonio Torrecillas]], [[CCC]], January 01, 2012 » [[B*]]
Line 277: Line 300:
 
==2015 ...==
 
==2015 ...==
 
* [http://www.talkchess.com/forum/viewtopic.php?t=59118 monte carlo tree search question] by [[Marco Belli]], [[CCC]], January 31, 2016
 
* [http://www.talkchess.com/forum/viewtopic.php?t=59118 monte carlo tree search question] by [[Marco Belli]], [[CCC]], January 31, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61801 The scaling of Deep Learning MCTS Go engines] by [[Kai Laskos]], [[CCC]], October 23, 2016 » [[Deep Learning]], [[Go]], [[Monte-Carlo Tree Search|MCTS]]
+
* [http://www.talkchess.com/forum/viewtopic.php?t=61801 The scaling of Deep Learning MCTS Go engines] by [[Kai Laskos]], [[CCC]], October 23, 2016 » [[Deep Learning]], [[Go]]
 
'''2017'''
 
'''2017'''
* [https://groups.google.com/forum/#!topic/fishcooking/AE4EgWQ20dY A branch to test the Monte Carlo algorithm in Stockfish] by Stephane Nicolet, [[Computer Chess Forums|FishCooking]], December 06, 2017 » [[Stockfish]], [[AlphaZero]]
+
* [https://groups.google.com/forum/#!topic/fishcooking/AE4EgWQ20dY A branch to test the Monte Carlo algorithm in Stockfish] by [[Stephane Nicolet]], [[Computer Chess Forums|FishCooking]], December 06, 2017 » [[Stockfish]], [[AlphaZero]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65964 Nebiyu-MCTS vs TSCP 1-0] by [[Daniel Shawul]], [[CCC]], December 10, 2017 » [[Nebiyu]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65964 Nebiyu-MCTS vs TSCP 1-0] by [[Daniel Shawul]], [[CCC]], December 10, 2017 » [[Nebiyu]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66013 An AlphaZero inspired project] by [[Truls Edvard Stokke]], [[CCC]], December 14, 2017 » [[AlphaZero]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66013 An AlphaZero inspired project] by [[Truls Edvard Stokke]], [[CCC]], December 14, 2017 » [[AlphaZero]]
Line 289: Line 312:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66886 comparing minimax and averaging MCTS with alphabeta rollouts] by [[Daniel Shawul]], [[CCC]], March 20, 2018 » [[Scorpio]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66886 comparing minimax and averaging MCTS with alphabeta rollouts] by [[Daniel Shawul]], [[CCC]], March 20, 2018 » [[Scorpio]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=67235 MCTS beginner questions] by [[Martin Fierz]], [[CCC]], April 25, 2018
 
* [http://www.talkchess.com/forum/viewtopic.php?t=67235 MCTS beginner questions] by [[Martin Fierz]], [[CCC]], April 25, 2018
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=67302 MCTS with minmax backup operator?] by [[Martin Fierz]], [[CCC]], May 01, 2018
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=67441 Komodo 12 and MCTS] by [[Larry Kaufman]], [[CCC]], May 14, 2018 » [[Komodo]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=67441 Komodo 12 and MCTS] by [[Larry Kaufman]], [[CCC]], May 14, 2018 » [[Komodo]]
 
'''2019'''
 
'''2019'''
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69612 MCTS: How to deal with extreme imbalances] by [[Alexandru Mosoi]], [[CCC]], January 16, 2019 » [[Zurichess]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69612 MCTS: How to deal with extreme imbalances] by [[Alexandru Mosoi]], [[CCC]], January 16, 2019 » [[Zurichess]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69993 MCTS implementation question] by mobmat, [[CCC]], February 22, 2019 <ref>[https://github.com/dkappe/leela_lite GitHub - dkappe/leela_lite: A toolkit for experimenting with UCT and Leela Chess nets in Python] by [[Dietrich Kappe]]</ref>
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70069 Training the trainer: how is it done for Stockfish?] by [[Marc-Philippe Huget]], [[CCC]], March 01, 2019 » [[Stockfish]]
 +
: [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70069&start=10 Re: Training the trainer: how is it done for Stockfish?] by Graham Jones, [[CCC]], March 03, 2019 » [[Leela Chess Zero]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70596 Training using 1 playout instead of 800] by [[Daniel Shawul]], [[CCC]], April 26, 2019
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70578&start=14 Re: On-line engine blitz tourney April] by [[Rémi Coulom]], [[CCC]], April 27, 2019
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70605 Question to Remi about CrazyZero] by [[Harm Geert Muller]], [[CCC]], April 28, 2019 » [[CrazyZero]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70611 SL vs RL] by [[Chris Whittington]], [[CCC]], April 28, 2019
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71301 A question to MCTS + NN experts] by [[Maksim Korzh]], [[CCC]], July 17, 2019 » [[Deep Learning]]
 +
: [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71301&start=3 Re: A question to MCTS + NN experts] by [[Daniel Shawul]], [[CCC]], July 17, 2019
  
 
=External Links=  
 
=External Links=  
Line 304: Line 337:
 
* Monte Carlo Tree Search by [https://www.strath.ac.uk/staff/levinejohndr/ John Levine], [https://en.wikipedia.org/wiki/University_of_Strathclyde University of Strathclyde], March 05, 2017, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
* Monte Carlo Tree Search by [https://www.strath.ac.uk/staff/levinejohndr/ John Levine], [https://en.wikipedia.org/wiki/University_of_Strathclyde University of Strathclyde], March 05, 2017, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
: {{#evu:https://www.youtube.com/watch?v=UXW2yZndl7U|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=UXW2yZndl7U|alignment=left|valignment=top}}
 +
* [https://en.chessbase.com/post/monte-carlo-instead-of-alpha-beta Monte Carlo instead of Alpha-Beta?] by [[Stephan Oliver Platz]], [[ChessBase|ChessBase News]], January 30, 2019 » [[Komodo#MCTS|Komodo MCTS]]
 
==Monte Carlo Misc==
 
==Monte Carlo Misc==
 
* [http://www.chessbase.com/newsdetail.asp?newsid=5075 Rybka's Monte Carlo analysis] by [[Steve Lopez]], [[ChessBase|ChessBase News]], February 03, 2009 » [[Rybka]]
 
* [http://www.chessbase.com/newsdetail.asp?newsid=5075 Rybka's Monte Carlo analysis] by [[Steve Lopez]], [[ChessBase|ChessBase News]], February 03, 2009 » [[Rybka]]

Revision as of 10:35, 15 May 2020

Home * Search * Monte-Carlo Tree Search

Edvard Munch - At the Roulette Table in Monte Carlo [1]

Monte Carlo Tree Search, (Monte-Carlo Tree Search, MCTS)
is a Best-First search algorithm based on random playouts. In conjunction with UCT (Upper Confidence bounds applied to Trees) Monte-Carlo Tree Search has yielded in a breakthrough in Computer Go [2], and is also successful in Amazons [3] [4], Lines of Action [5], Havannah [6], Hex [7], Checkers [8] and other Games with some difficulties in position evaluation, but until December 2017, when a Google DeepMind team reported on AlphaZero [9], not for Chess [10] [11].

MCTS is based on randomized explorations of the search space. Using the results of previous explorations, the algorithm gradually grows a game tree in memory, and successively becomes better at accurately estimating the values of the most promising moves [12].

Four Phases

MCTS consists of four strategic phases, repeated as long as there is time left [13] :

  1. In the Selection phase the tree is traversed from the root node until it selects a leaf node that is not added to the tree yet
  2. The Expansion strategy adds the leaf node to the tree
  3. The Simulation strategy plays moves in self-play until the end of the game. The result is either 1, 0 ,-1
  4. The Backpropagation strategy propagates the results through the tree
MCTS (English).svg

Steps of Monte Carlo Tree Search [14]

Pure Monte-Carlo search

Pure Monte-Carlo search with parameter T means that for each feasible move T random games are generated. The move with the best average score is played. A game is called “Monte Carlo perfect” when this procedure converges to perfect play for each position, when T goes to infinity. However, with limited time per move, increasing T does not guarantee to find a better move [15].

UCT

UCT (Upper Confidence bounds applied to Trees) deals with the flaw of Monte-Carlo Tree Search, when a program may favor a losing move with only one or a few forced refutations, but due to the vast majority of other moves provides a better random playout score than other, better moves [16].

See also

Publications

1987

1990 ...

2000 ...

2005 ...

2006

2007

2008

2009

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017

2018

2019

Forum Posts

2010 ...

2015 ...

2017

2018

2019

Re: Training the trainer: how is it done for Stockfish? by Graham Jones, CCC, March 03, 2019 » Leela Chess Zero
Re: A question to MCTS + NN experts by Daniel Shawul, CCC, July 17, 2019

External Links

Monte Carlo Tree Search

GitHub - suragnair/alpha-zero-general: A clean and simple implementation of a self-play learning algorithm based on AlphaGo Zero (any game, any framework!)

Monte Carlo Misc

Monte Carlo algorithm
Monte Carlo method
Monte Carlo
Monte Carlo Casino
feat. Raúl Midón, Roy Hargrove and the Monte-Carlo Philharmonic Orchestra, November 29, 2008, Monte-Carlo Jazz Festival

References

  1. Edvard Munch, At the Roulette Table in Monte Carlo, 1893, Edvard Munch from Wikipedia
  2. Rémi Coulom (2009). The Monte-Carlo Revolution in Go. JFFoS'2008: Japanese-French Frontiers of Science Symposium, slides as pdf
  3. Julien Kloetzer, Hiroyuki Iida, Bruno Bouzy (2007). The Monte-Carlo approach in Amazons. CGW 2007
  4. Richard J. Lorentz (2008). Amazons Discover Monte-Carlo. CG 2008
  5. Mark Winands, Yngvi Björnsson (2009). Evaluation Function Based Monte-Carlo LOA. pdf
  6. Richard J. Lorentz (2010). Improving Monte-Carlo Tree Search in Havannah. CG 2010
  7. Broderick Arneson, Ryan Hayward, Philip Henderson (2010). Monte Carlo Tree Search in Hex. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 4, pdf
  8. UCT surprise for checkers ! by Daniel Shawul, CCC, March 25, 2011
  9. David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815
  10. Raghuram Ramanujan, Ashish Sabharwal, Bart Selman (2010). On Adversarial Search Spaces and Sampling-Based Planning. ICAPS 2010
  11. Oleg Arenz (2012). Monte Carlo Chess. B.Sc. thesis, Darmstadt University of Technology, advisor Johannes Fürnkranz, pdf
  12. Guillaume Chaslot, Mark Winands, Jaap van den Herik (2008). Parallel Monte-Carlo Tree Search. CG 2008, pdf
  13. Guillaume Chaslot, Mark Winands, Jaap van den Herik (2008). Parallel Monte-Carlo Tree Search. CG 2008, pdf
  14. Steps of Monte-Carlo Tree Search by Mciura, March 31, 2013, Wikimedia Commons, Monte Carlo tree search from Wikipedia
  15. Ingo Althöfer (2011). On Board-Filling Games with Random-Turn Order and Monte Carlo Perfectness. Advances in Computer Games 13
  16. Levente Kocsis, Csaba Szepesvári (2006). Bandit based Monte-Carlo Planning ECML-06, LNCS/LNAI 4212, pp. 282-293. introducing UCT, pdf
  17. Morpion solitaire from Wikipedia
  18. Jeff Rollason (2015). Mixing the Immiscible - MCTS and evaluation. AI Factory, October 2015
  19. Monte Carlo in LOA by Mark Watkins, Open Chess Forum, December 30, 2010
  20. The Settlers of Catan from Wikipedia
  21. Blokus Duo from Wikipedia
  22. Search traps in MCTS and chess by Daniel Shawul, CCC, December 25, 2017
  23. NoGo (ICGA Tournaments)
  24. Ms. Pac-Man from Wikipedia
  25. Value of information (VOI) from Wikipedia
  26. Scotland Yard (board game) from Wikipedia
  27. Morpion solitaire from Wikipedia
  28. Morpion Solitaire - Record Grids (5T game)
  29. Re: MC methods by Daniel Shawul, CCC, April 13, 2013
  30. Crossings from Wikipedia
  31. Epaminondas from Wikipedia
  32. 7 Wonders (board game) from WIkipedia
  33. Guillaume Chaslot, Mark Winands, Jos Uiterwijk, Jaap van den Herik, Bruno Bouzy (2008). Progressive Strategies for Monte-Carlo Tree Search. New Mathematics and Natural Computation, Vol. 4, No. 3, pdf
  34. Dap Hartmann (2017). Let's Catch the Train to Monte-Carlo. ICGA Journal, Vol. 39, No. 1
  35. Re: Minmax backup operator for MCTS by Brahim Hamadicharef, CCC, December 30, 2017
  36. Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » Leela Chess Zero
  37. GitHub - suragnair/alpha-zero-general: A clean and simple implementation of a self-play learning algorithm based on AlphaGo Zero (any game, any framework!)
  38. "Exact-Win Strategy for Overcoming AlphaZero" · Issue #799 · LeelaChessZero/lc0 · GitHub
  39. GitHub - dkappe/leela_lite: A toolkit for experimenting with UCT and Leela Chess nets in Python by Dietrich Kappe
  40. A Simple Alpha(Go) Zero Tutorial by Oliver Roese, CCC, December 30, 2017
  41. David Silver, Gerald Tesauro (2009). Monte-Carlo Simulation Balancing. ICML 2009, pdf

Up one level