Home * Search * Monte-Carlo Tree Search

		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 [1], and is also successful in Amazons [2] [3], Lines of Action [4], Havannah [5], Hex [6], Checkers [7] and other Games with some difficulties in position evaluation, but until December 2017, when a Google DeepMind team reported on AlphaZero [8], not for Chess [9] [10]. 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 [11].
Edvard Munch - At the Roulette Table in Monte Carlo [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

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

• Deep Learning
• MCαβ
• MC and UCT poster by Jakob Erdmann
• Rollout Paradigm
• Sampling-Based Planning
• Simulated Annealing
• UCT

Publications

1987

• Bruce Abramson, Richard Korf (1987). A Model of Two-Player Evaluation Functions. AAAI-87. pdf

1990 ...

• Bruce Abramson (1990). Expected-Outcome: A General Model of Static Evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence 12(2): 182-193.
• Bruce Abramson (1990). An Analysis of Expected-Outcome. Journal of Experimental and Theoretical Artificial Intelligence 2: 55-73.
• 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).
• Bernd Brügmann (1993). Monte Carlo Go. pdf

2000 ...

• Bruno Bouzy, Bernard Helmstetter (2003). Monte Carlo Go Developments. Advances in Computer Games 10, pdf
• Bruno Bouzy (2004). Associating Shallow and Selective Global Tree Search with Monte Carlo for 9 × 9 Go. CG 2004
• Tristan Cazenave (2004). Monte Carlo Real Time Strategy. pdf

2005 ...

• Tristan Cazenave, Bernard Helmstetter (2005). Combining tactical search and Monte-Carlo in the game of Go. IEEE CIG 2005, pdf, pdf
• Bruno Bouzy (2005). Move-Pruning Techniques for Monte-Carlo Go. Advances in Computer Games 11
• Bruno Bouzy (2005). Associating domain-dependent knowledge and Monte Carlo approaches within a go program. Information Sciences, Heuristic Search and Computer Game Playing IV

2006

• Levente Kocsis, Csaba Szepesvári (2006). Bandit based Monte-Carlo Planning ECML-06, LNCS/LNAI 4212, pp. 282-293. introducing UCT, pdf
• Sylvain Gelly, Yizao Wang (2006). Exploration exploitation in Go: UCT for Monte-Carlo Go. pdf
• Sylvain Gelly, Yizao Wang, Rémi Munos, Olivier Teytaud (2006). Modification of UCT with Patterns in Monte-Carlo Go. INRIA
• Levente Kocsis, Csaba Szepesvári, Jan Willemson (2006). Improved Monte-Carlo Search. pdf
• Jahn-Takeshi Saito, Guillaume Chaslot, Jos Uiterwijk, Jaap van den Herik (2006). Monte-Carlo Proof-Number Search for Computer Go. CG 2006
• Rémi Coulom (2006). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. CG 2006
• Bruno Bouzy (2006). History and Territory Heuristics for Monte-Carlo Go. New Mathematics and Natural Computation
• Haruhiro Yoshimoto, Kazuki Yoshizoe, Tomoyuki Kaneko, Akihiro Kishimoto, Kenjiro Taura (2006). Monte Carlo Go Has a Way to Go. AAAI 2006, pdf

2007

• Rémi Coulom (2007). Monte-Carlo Tree Search in Crazy Stone. slides as pdf
• Yizao Wang, Sylvain Gelly (2007). Modifications of UCT and Sequence-Like Simulations for Monte-Carlo Go. IEEE Symposium on Computational Intelligence and Games, Honolulu, USA, 2007, pdf
• Shugo Nakamura, Makoto Miwa, Takashi Chikayama (2007). Improvement of UCT using evaluation function. 12th Game Programming Workshop 2007
• Ken Chen, Peigang Zhang (2007). Monte-Carlo Go with Knowledge-Guided Simulations. CGW 2007
• Tristan Cazenave (2007). Reflexive Monte-Carlo Search. CGW 2007, pdf
• François van Lishout, Guillaume Chaslot, Jos Uiterwijk (2007). Monte-Carlo Tree Search in Backgammon. CGW 2007
• Julien Kloetzer, Hiroyuki Iida, Bruno Bouzy (2007). The Monte-Carlo approach in Amazons. CGW 2007
• Tristan Cazenave, Nicolas Jouandeau (2007). On the Parallelization of UCT. CGW 2007, pdf
• Jahn-Takeshi Saito, Mark Winands, Jos Uiterwijk, Jaap van den Herik (2007). Grouping Nodes for Monte-Carlo Tree Search. CGW 2007
• Tristan Cazenave (2007). Evolving Monte-Carlo Tree Search Algorithms. pdf
• Pim Nijssen (2007). Playing Othello Using Monte Carlo. Bachelor's Thesis, Maastricht University, pdf

2008

• Ken Chen, Peigang Zhang (2008). Monte-Carlo Go with Knowledge-Guided Simulations. ICGA Journal, Vol. 31, No. 2
• Sylvain Gelly, Jean-Baptiste Hoock, Arpad Rimmel, Olivier Teytaud, Yann Kalemkarian (2008). The Parallelization of Monte-Carlo Planning - Parallelization of MC-Planning. ICINCO-ICSO 2008: 244-249, pdf, slides as 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. pdf
• 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 ^[17]
• Guillaume Chaslot, Sander Bakkes, István Szita and Pieter Spronck (2008). Monte-Carlo Tree Search: A New Framework for Game AI. pdf
• Guillaume Chaslot, Mark Winands, István Szita, and Jaap van den Herik. (2008). Cross-entropy for Monte-Carlo Tree Search. ICGA Journal, Vol. 31, No. 3, 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. pdf
• Maarten Schadd, Mark Winands, Jaap van den Herik, Guillaume Chaslot, Jos Uiterwijk (2008). Single-Player Monte-Carlo Tree Search. CG 2008, pdf
• Richard J. Lorentz (2008). Amazons Discover Monte-Carlo. CG 2008
• Mark Winands, Yngvi Björnsson, Jahn-Takeshi Saito (2008). Monte-Carlo Tree Search Solver. CG 2008, pdf
• Nathan Sturtevant (2008). An Analysis of UCT in Multi-player Games. CG 2008
• Guillaume Chaslot, Mark Winands, Jaap van den Herik (2008). Parallel Monte-Carlo Tree Search. CG 2008, pdf
• Tristan Cazenave, Nicolas Jouandeau (2008). A Parallel Monte-Carlo Tree Search Algorithm. CG 2008, pdf
• Ken Chen, Dawei Du, Peigang Zhang (2008). 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, pdf, Supplemental material - pdf
• James H. Brodeur, Benjamin E. Childs and Levente Kocsis (2008). Transpositions and Move Groups in Monte Carlo Tree Search. 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. pdf, pdf » General Game Playing
• Jean Méhat, Tristan Cazenave (2008). Monte-Carlo Tree Search for General Game Playing. pdf » General Game Playing
• Tristan Cazenave, Nicolas Jouandeau (2008). A Parallel Monte-Carlo Tree Search Algorithm. pdf
• Ingo Althöfer (2008). On the Laziness of Monte-Carlo Game Tree Search in Non-tight Situations. Technical Report, pdf
• Kazutomo Shibahara, Yoshiyuki Kotani (2008). Combining Final Score with Winning Percentage using Sigmoid Function in Monte-Carlo Algorithm. 13th Game Programming Workshop, pdf
• Shogo Takeuchi, Tomoyuki Kaneko, Kazunori Yamaguchi (2008). Evaluation of Monte Carlo tree search and the application to Go. CIG 2008

2009

• Jean-Yves Audibert, Rémi Munos, Csaba Szepesvári (2009). Exploration-exploitation trade-off using variance estimates in multi-armed bandits. Theoretical Computer Science, 410:1876-1902, 2009, 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, 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. pdf
• Markus Enzenberger and Martin Müller (2009). A lock-free multithreaded Monte-Carlo tree search algorithm, Advances in Computer Games 12, pdf
• Markus Enzenberger and Martin Müller (2009). Fuego - An Open-source Framework for Board Games and Go Engine Based on Monte-Carlo Tree Search, pdf
• Rémi Coulom (2009). The Monte-Carlo Revolution in Go. JFFoS'2008: Japanese-French Frontiers of Science Symposium, slides as pdf
• Mark Winands and Yngvi Björnsson (2009). Evaluation Function Based Monte-Carlo LOA. pdf ^[18]
• Tristan Cazenave (2009). Nested Monte-Carlo Search. IJCAI 2009, pdf
• Paolo Ciancarini, Gian Piero Favini (2009). Monte Carlo Tree Search Techniques in the Game of Kriegspiel. IJCAI 2009, pdf » KriegSpiel
• Tristan Cazenave (2009). Monte-Carlo Kakuro. Advances in Computer Games 12, pdf
• István Szita, Guillaume Chaslot, Pieter Spronck (2009). Monte-Carlo Tree Search in Settlers of Catan. Advances in Computer Games 12, pdf ^[19]
• Tristan Cazenave, Nicolas Jouandeau (2009). Parallel Nested Monte-Carlo Search. NIDISC 2009, pdf
• Tomas Kozelek (2009). Methods of MCTS and the game Arimaa. Master's thesis, pdf » Arimaa
• Kenta Sasaki, Yoshiyuki Kotani (2009). Monte-Carlo Tree Search in the Game of Blokus-Duo. 14th Game Programming Workshop ^[20]
• David Silver, Gerald Tesauro (2009). Monte-Carlo Simulation Balancing. ICML 2009, pdf
• Ken Chen, Dawei Du, Peigang Zhang (2009). Monte-Carlo Tree Search and Computer Go. Advances in Information and Intelligent Systems 2009
• David Silver (2009). Reinforcement Learning and Simulation-Based Search. Ph.D. thesis, University of Alberta, pdf
• Seth Pellegrino, Andrew Hubbard, Jason Galbraith, Peter D. Drake, Yung-Pin Chen (2009). Localizing Search in Monte-Carlo Go using Statistical Covariance. ICGA Journal, Vol. 32, No. 3

2010 ...

• Julien Kloetzer (2010). 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, Vol. 33, No. 2
• Richard J. Lorentz (2010). 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). Scalability and Parallelization of Monte-Carlo Tree Search. CG 2010, pdf
• Julien Kloetzer (2010). Monte-Carlo Opening Books for Amazons. CG 2010
• Arpad Rimmel, Fabien Teytaud, Olivier Teytaud (2010). Biasing Monte-Carlo Simulations through RAVE Values. CG 2010, pdf
• Jean-Yves Audibert (2010). PAC-Bayesian aggregation and multi-armed bandits. Habilitation thesis, Université Paris Est, pdf, slides as pdf
• Shih-Chieh Huang, Rémi Coulom, Shun-Shii Lin (2010). Monte-Carlo Simulation Balancing in Practice. CG 2010, pdf
• Tristan Cazenave, Abdallah Saffidine (2010). Score Bounded Monte-Carlo Tree Search. CG 2010, pdf
• Pim Nijssen, Mark Winands (2010). Enhancements for Multi-Player Monte-Carlo Tree Search. CG 2010, pdf
• Raghuram Ramanujan, Ashish Sabharwal, Bart Selman (2010). On Adversarial Search Spaces and Sampling-Based Planning. ICAPS 2010 ^[21]
• Shih-Chieh Huang, Rémi Coulom, Shun-Shii Lin (2010). Monte-Carlo Simulation Balancing applied to 9x9 Go. ICGA Journal, Vol. 33, No. 4
• Tristan Cazenave, Abdallah Saffidine (2010). Monte-Carlo Hex. pdf
• Jean Méhat, Tristan Cazenave (2010). Combining UCT and Nested Monte-Carlo Search for Single-Player General Game Playing. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 4, pdf 2009 » General Game Playing
• 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
• Hendrik Baier, Peter D. Drake (2010). The power of forgetting: Improving the last-good-reply policy in Monte Carlo Go. 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. pdf
• Fabien Teytaud, Olivier Teytaud (2010). On the Huge Benefit of Decisive Moves in Monte-Carlo Tree Search Algorithms. pdf
• Guillaume Chaslot (2010). Monte-Carlo Tree Search. Ph.D. Thesis, Maastricht University, pdf
• Jahn-Takeshi Saito (2010). Solving Difficult Game Positions. Ph.D. Thesis, Maastricht University, pdf
• Romaric Gaudel, Michèle Sebag (2010). Feature Selection as a one-player game. ICML 2010, pdf
• Hendrik Baier (2010). Adaptive Playout Policies for Monte-Carlo Go. Master's thesis, University of Osnabrück, pdf
• Thomas J. Walsh, Sergiu Goschin, Michael L. Littman (2010). Integrating sample-based planning and model-based reinforcement learning. AAAI, pdf » UCT, Reinforcement Learning

2011

• 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, pdf
• Arpad Rimmel, Fabien Teytaud, Tristan Cazenave (2011). Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows. Evostar 2011, pdf
• Cameron Browne (2011). The Dangers of Random Playouts. ICGA Journal, Vol. 34, No. 1
• Jean Méhat, Tristan Cazenave (2011). A Parallel General Game Player. KI Journal, Vol. 25, No. 1, pdf
• Shih-Chieh Huang (2011). New Heuristics for Monte Carlo Tree Search Applied to the Game of Go. Ph.D. thesis, pdf
• Petr Baudiš (2011). Information Sharing in MCTS. Master thesis, Faculty of Mathematics and Physics, Charles University in Prague, pdf
• Petr Baudiš (2011). Balancing MCTS by Dynamically Adjusting the Komi Value. ICGA Journal, Vol. 34, No. 3
• Richard J. Lorentz (2011). Experiments with Monte-Carlo Tree Search in the Game of Havannah. ICGA Journal, Vol. 34, No. 3
• Kazuki Yoshizoe, Akihiro Kishimoto, Tomoyuki Kaneko, Haruhiro Yoshimoto, Yutaka Ishikawa (2011). Scalable Distributed Monte Carlo Tree Search. SoCS2011, pdf
• Cheng-Wei Chou, Olivier Teytaud, Shi-Jim Yen (2011). Revisiting Monte-Carlo Tree Search on a Normal Form Game: NoGo. EvoApplications 2011 ^[22]
• Shi-Jim Yen, Jung-Kuei Yang (2011). Two-Stage Monte Carlo Tree Search for Connect6. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 3
• Nozomu Ikehata, Takeshi Ito (2011). Monte-Carlo Tree Search In Ms. Pac-Man. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 3 ^[23]
• Junichi Hashimoto, Akihiro Kishimoto, Kazuki Yoshizoe, Kokolo Ikeda (2011). Accelerated UCT and Its Application to Two-Player Games. Advances in Computer Games 13
• Jan Stankiewicz, Mark Winands, Jos Uiterwijk (2011). Monte-Carlo Tree Search Enhancements for Havannah. Advances in Computer Games 13
• Gabriel Van Eyck, Martin Müller (2011). Revisiting Move Groups in Monte-Carlo Tree Search. Advances in Computer Games 13
• Hendrik Baier, Mark Winands (2011). Active Opening Book Application for Monte-Carlo Tree Search in 19x19 Go. BNAIC 2011, pdf
• Hendrik Baier, Mark Winands (2011). Time Management for Monte-Carlo Tree Search in Go. Advances in Computer Games 13
• Richard J. Lorentz (2011). An MCTS Program to Play EinStein Würfelt Nicht! Advances in Computer Games 13
• Cheng-Wei Chou, Ping-Chiang Chou, Hassen Doghmen, Chang-Shing Lee, Tsan-Cheng Su, Fabien Teytaud, Olivier Teytaud, Hui-Ming Wang, Mei-Hui Wang, Li-Wen Wu, Shi-Jim Yen (2011). Towards a Solution of 7x7 Go with Meta-MCTS. Advances in Computer Games 13
• Bruno Bouzy, Marc Métivier, Damien Pellier (2011). MCTS Experiments on the Voronoi Game. Advances in Computer Games 13
• Pim Nijssen, Mark Winands (2011). Playout Search for Monte-Carlo Tree Search in Multi-Player Games. Advances in Computer Games 13
• Jiao Wang, Shiyuan Li, Jitong Chen, Xin Wei, Huizhan Lv, Xinhe Xu (2011). 4*4-Pattern and Bayesian Learning in Monte-Carlo Go. Advances in Computer Games 13
• Jeff Rollason (2011). Mixing MCTS with Conventional Static Evaluation: Experiments and shortcuts en-route to full UCT. AI Factory, Winter 2011 » UCT, Evaluation
• Sylvain Gelly, David Silver (2011). Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence, Vol. 175, No. 11
• Lars Schaefers, Marco Platzner, Ulf Lorenz (2011). UCT-Treesplit - Parallel MCTS on Distributed Memory. MCTS Workshop, Freiburg, Germany, pdf
• Tobias Graf, Ulf Lorenz, Marco Platzner, Lars Schaefers (2011). Parallel Monte-Carlo Tree Search for HPC Systems. Euro-Par 2011, pdf
• Joel Veness, Marc Lanctot, Michael Bowling (2011). Variance Reduction in Monte-Carlo Tree Search. NIPS, pdf

2012

• Michael L. Littman (2012). Technical Perspective: A New Way to Search Game Trees. Communications of the ACM, Vol. 55, No. 3
• Sylvain Gelly, Marc Schoenauer, Michèle Sebag, Olivier Teytaud, Levente Kocsis, David Silver, Csaba Szepesvári (2012). The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions. Communications of the ACM, Vol. 55, No. 3, pdf preprint
• Oleg Arenz (2012). Monte Carlo Chess. B.Sc. thesis, Darmstadt University of Technology, advisor Johannes Fürnkranz, pdf » Stockfish
• Jeff Rollason (2012). Tuning Spades. AI Factory, Summer 2012 » UCT
• 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
• 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, pdf
• Jan Kuipers, Aske Plaat, Jos Vermaseren, Jaap van den Herik (2012). Improving multivariate Horner schemes with Monte Carlo tree search. 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). A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 4, No. 1
• Pim Nijssen, Mark Winands (2012). Monte-Carlo Tree Search for the Hide-and-Seek Game Scotland Yard. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 4, No. 4 ^[24]
• Hendrik Baier, Mark Winands (2012). Nested Monte-Carlo Tree Search for Online Planning in Large MDPs. ECAI 2012, pdf
• Hendrik Baier, Mark Winands (2012). Beam Monte-Carlo Tree Search. CIG 2012, pdf
• Adrien Couetoux, Olivier Teytaud, Hassen Doghmen (2012). Learning a Move-Generator for Upper Confidence Trees. ICS 2012, Hualien, Taiwan, December 2012

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 2012, Excellent Paper Award, pdf
• Daniel S. Abdi (2013). Monte carlo methods for estimating game tree size. pdf ^[25] » Perft
• Marc Lanctot (2013). Monte Carlo Sampling and Regret Minimization for Equilibrium Computation and Decision-Making in Large Extensive Form Games. Ph.D. thesis, University of Alberta, advisor Michael Bowling
• Aviezri Fraenkel (2013). Reflection. ICGA Journal, Vol. 36, No. 1 » Stanislaw Ulam
• Jeff Rollason (2013). Reducing the burden of knowledge: Simulation-based methods in imperfect information games. AI Factory, Summer 2013
• Abdallah Saffidine (2013). Solving Games and All That. Ph.D. thesis, 2.5 Monte Carlo Tree Search
• Shih-Chieh Huang, Martin Müller (2013). Investigating the Limits of Monte Carlo Tree Search Methods in Computer Go. CG 2013
• Shih-Chieh Huang, Broderick Arneson, Ryan Hayward, Martin Müller, Jakub Pawlewicz (2013). MoHex 2.0: a pattern-based MCTS Hex player. CG 2013, pdf
• Tobias Graf, Lars Schaefers, Marco Platzner (2013). On Semeai Detection in Monte-Carlo Go. CG 2013, pdf
• Richard J. Lorentz, Therese Horey (2013). Programming Breakthrough. CG 2013 » Breakthrough (Game)
• Ingo Althöfer, Wesley Turner (2013). Anomalies of Pure Monte Carlo Search in Monte Carlo Perfect Games. CG 2013
• Simon Viennot, Kokolo Ikeda (2013). Efficiency of Static Knowledge Bias in Monte-Carlo Tree Search. CG 2013
• Sumudo Fernando, Martin Müller (2013). Analyzing Simulations in Monte-Carlo Tree Search for the Game of Go. CG 2013
• Ingo Althöfer (2013). The wild Years are gone: Monte Carlo in Smoother Waters. Conference Report CG 2013, ICGA Journal, Vol. 36, No. 3
• Marc Lanctot, Abdallah Saffidine, Joel Veness, Christopher Archibald, Mark Winands (2013). Monte Carlo *-Minimax Search. IJCAI 2013
• Pim Nijssen (2013). Monte-Carlo Tree Search for Multi-Player Games. Ph.D. thesis, Maastricht University, pdf
• Jeff Rollason (2013). Searching the Unknown with MCTS. AI Factory, Winter 2013
• David Silver, Richard Sutton, Martin Mueller (2013). Temporal-Difference Search in Computer Go. ICAPS-13, pdf
• Hendrik Baier, Mark Winands (2013). Monte-Carlo Tree Search and minimax hybrids. CIG 2013, pdf
• Timothy Furtak, Michael Buro (2013). Recursive Monte Carlo search for imperfect information games. CIG 2013, pdf
• Ben Ruijl, Jos Vermaseren, Aske Plaat, Jaap van den Herik (2013). Combining Simulated Annealing and Monte Carlo Tree Search for Expression Simplification. CoRR abs/1312.0841
• Arthur Guez, David Silver, Peter Dayan (2013). Scalable and Efficient Bayes-Adaptive Reinforcement Learning Based on Monte-Carlo Tree Search. Journal of Artificial Intelligence Research, Vol. 48, pdf
• Ari Weinstein, Michael L. Littman, Sergiu Goschin (2013). Rollout-based Game-tree Search Outprunes Traditional Alpha-beta. PMLR, Vol. 24 » UCT

2014

• Ben Ruijl, Jos Vermaseren, Aske Plaat, Jaap van den Herik (2014). HEPGAME and the Simplification of Expressions. CoRR abs/1405.6369
• S. Ali Mirsoleimani, Aske Plaat, Jaap van den Herik, Jos Vermaseren (2014). Performance analysis of a 240 thread tournament level MCTS Go program on the Intel Xeon Phi. CoRR abs/1409.4297 » Go, Parallel Search, x86-64
• Ben Ruijl, Jos Vermaseren, Aske Plaat, Jaap van den Herik (2014). Why Local Search Excels in Expression Simplification. CoRR abs/1409.5223
• Lars Schaefers (2014). Parallel Monte-Carlo Tree Search for HPC Systems and its Application to Computer Go. Ph.D. thesis, University of Paderborn, advisors Marco Platzner, Ulf Lorenz, pdf, pdf
• Rémi Munos (2014). From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning. Foundations and Trends in Machine Learning, Vol. 7, No 1, hal-00747575v5, slides as pdf
• David W. King (2014). Complexity, Heuristic, and Search Analysis for the Games of Crossings and Epaminondas. Masters thesis, Air Force Institute of Technology, pdf ^[26]
• David W. King, Gilbert L. Peterson (2014). Epaminondas: Exploring Combat Tactics. ICGA Journal, Vol. 37, No. 3 ^[27]
• Ting-Fu Liao, I-Chen Wu, Guan-Wun Chen, Chung-Chin Shih, Po-Ya Kang, Bing-Tsung Chiang, Ting-Chu Ho, Ti-Rong Wu (2014). A Study of Software Framework for Parallel Monte Carlo Tree Search. GPW-2014
• Hendrik Baier, Mark Winands (2014). Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions. ECAI CGW 2014
• Nicolas Jouandeau, Tristan Cazenave (2014). Small and Large MCTS Playouts applied to Chinese Dark Chess Stochastic Game. ECAI CGW 2014
• Tom Pepels, Tristan Cazenave, Mark Winands, Marc Lanctot (2014). Minimizing Simple and Cumulative Regret in Monte-Carlo Tree Search. ECAI CGW 2014
• Denis Robilliard, Cyril Fonlupt, Fabien Teytaud (2014). Monte-Carlo Tree Search for the Game of “7 Wonders”. ECAI CGW 2014 ^[28]
• Johannes Heinrich, David Silver (2014). Self-Play Monte-Carlo Tree Search in Computer Poker. AAAI-14 Workshop

2015 ...

• Richard J. Lorentz (2015). Early Playout Termination in MCTS. Advances in Computer Games 14
• Tristan Cazenave (2015). Playout Policy Adaptation for Games. Advances in Computer Games 14
• Tobias Graf, Marco Platzner (2015). Adaptive Playouts in Monte Carlo Tree Search with Policy Gradient Reinforcement Learning. Advances in Computer Games 14
• Chu-Hsuan Hsueh, I-Chen Wu, Wen-Jie Tseng, Shi-Jim Yen, Jr-Chang Chen (2015). Strength Improvement and Analysis for an MCTS-Based Chinese Dark Chess Program. Advances in Computer Games 14
• Yusaku Mandai, Tomoyuki Kaneko (2015). LinUCB Applied to Monte Carlo Tree Search. Advances in Computer Games 14
• Yun-Ching Liu, Yoshimasa Tsuruoka (2015). Adapting Improved Upper Confidence Bounds for Monte-Carlo Tree Search. Advances in Computer Games 14
• Jiao Wang, Tan Zhu, Hongye Li, Chu-Hsuan Hsueh, I-Chen Wu (2015). Belief-state Monte-Carlo tree search for Phantom games. CIG 2015
• Fabien Teytaud, Julien Dehos (2015). On the Tactical and Strategic Behaviour of MCTS when Biasing Random Simulations. ICGA Journal, Vol. 38, No. 2
• Jeff Rollason (2015). Mixing the Immiscible - MCTS and evaluation. AI Factory, October 2015 ^[29]
• S. Ali Mirsoleimani, Aske Plaat, Jaap van den Herik, Jos Vermaseren (2015). Scaling Monte Carlo Tree Search on Intel Xeon Phi. 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. TrustCom/BigDataSE/|ISPA 2015, pdf
• Peter H. Jin, Kurt Keutzer (2015). Convolutional Monte Carlo Rollouts in Go. arXiv:1512.03375
• Naoki Mizukami, Yoshimasa Tsuruoka (2015). Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models. IEEE CIG 2015, pdf
• Hendrik Baier (2015). Monte-Carlo Tree Search Enhancements for One-Player and Two-Player Domains. Ph.D. thesis, Maastricht University, pdf ^[30]
• Lars Schaefers, Marco Platzner (2015). Distributed Monte Carlo Tree Search: A Novel Technique and its Application to Computer Go. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, No. 4 ^[31]
• Bojun Huang (2015). Pruning Game Tree by Rollouts. AAAI » MT-SSS* ^[32]

2016

• David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, Demis Hassabis (2016). Mastering the game of Go with deep neural networks and tree search. Nature, Vol. 529 » AlphaGo
• Tobias Graf, Marco Platzner (2016). Using Deep Convolutional Neural Networks in Monte Carlo Tree Search. CG 2016
• Takahisa Imagawa, Tomoyuki Kaneko (2016). Monte Carlo Tree Search with Robust Exploration. CG 2016
• Joris Duguépéroux, Ahmad Mazyad, Fabien Teytaud, Julien Dehos (2016). Pruning playouts in Monte-Carlo Tree Search for the game of Havannah. CG 2016
• Peter H. Jin, Kurt Keutzer (2016). Convolutional Monte Carlo Rollouts for Computer Go. CG 2016
• Hendrik Baier, Mark Winands (2016). Time Management for Monte Carlo Tree Search. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 8, No. 3, draft as pdf
• Katsuki Ohto, Tetsuro Tanaka (2016). Application of Monte Carlo Tree Search to Curling AI. 21st Game Programming Workshop

2017

• Dap Hartmann (2017). Let's Catch the Train to Monte-Carlo. ICGA Journal, Vol. 39, No. 1, Review on Hendrik Baier's Ph.D. thesis
• 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
• 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 » AlphaZero
• Shantanu Thakoor, Surag Nair, Megha Jhunjhunwala (2017). Learning to Play Othello Without Human Knowledge. Stanford University, pdf » AlphaZero, Othello, Deep Learning ^[33]
• Hendrik Baier (2017). A Rollout-Based Search Algorithm Unifying MCTS and Alpha-Beta. Computer Games » Rollout Paradigm
• Tristan Cazenave (2017). Nested Rollout Policy Adaptation with Selective Policies. Computer Games

Forum Posts

2010 ...

• [Computer-go] learning patterns for mc go by Hendrik Baier, Computer Go Archive, April 26, 2010
• UCT surprise for checkers ! by Daniel Shawul, CCC, March 25, 2011
• MCTS without random playout? by Antonio Torrecillas, CCC, January 01, 2012 » B*
• Re: MC methods by Daniel Shawul, CCC, April 13, 2013 » Perft

2015 ...

• monte carlo tree search question by Marco Belli, CCC, January 31, 2016
• The scaling of Deep Learning MCTS Go engines by Kai Laskos, CCC, October 23, 2016 » Deep Learning, Go, MCTS

2017

• A branch to test the Monte Carlo algorithm in Stockfish by Stephane Nicolet, FishCooking, December 06, 2017 » Stockfish, AlphaZero
• Nebiyu-MCTS vs TSCP 1-0 by Daniel Shawul, CCC, December 10, 2017 » Nebiyu
• An AlphaZero inspired project by Truls Edvard Stokke, CCC, December 14, 2017 » AlphaZero
• MCTS wrapper for StockFish by Jonathan Baxter, FishCooking, December 19, 2017 » Stockfish
• Search traps in MCTS and chess by Daniel Shawul, CCC, December 25, 2017 » Sampling-Based Planning
• MCTS weakness wrt AB (via Daniel Shawul) by Chris Whittington, Rybka Forum, December 25, 2017

2018

• Alpha-Beta as a rollouts algorithm by Daniel Shawul, CCC, January 25, 2018 » Alpha-Beta, MCαβ, Scorpio
• comparing minimax and averaging MCTS with alphabeta rollouts by Daniel Shawul, CCC, March 20, 2018 » Scorpio
• MCTS beginner questions by Martin Fierz, CCC, April 25, 2018

External Links

Monte Carlo Tree Search

• Monte Carlo tree search from Wikipedia
• Sensei's Library: Monte Carlo Tree Search
• Sensei's Library: UCT
• Monte Carlo Tree Search - Home by Cameron Browne
• Lange Nacht der Wissenschaften - Long Night of Sciences Jena - 2007 by Ingo Althöfer, MC and UCT poster by Jakob Erdmann
• A Simple Alpha(Go) Zero Tutorial by Surag Nair, Stanford University, December 29, 2017 » AlphaZero, Deep Learning ^[34]
  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

• Rybka's Monte Carlo analysis by Steve Lopez, ChessBase News, February 03, 2009 » Rybka
• Monte Carlo (disambiguation) from Wikipedia
  Monte Carlo algorithm
  Monte Carlo method
  Monte Carlo
  Monte Carlo Casino
• A History of Monte Carlo
• Software Development in the UNIX Environment - Example C Program to Compute PI Using A Monte Carlo Method
• Calculation of Pi Using the Monte Carlo Method by Eve Astrid Andersson
• Slot machine from Wikipedia
• Monte-Carlo Simulation Balancing - videolectures.net by David Silver ^[35]
• Marcus Miller - State of Mind (Raúl Midón), A Night In Monte-Carlo (2010), YouTube Video
  feat. Raúl Midón, Roy Hargrove and the Monte-Carlo Philharmonic Orchestra, November 29, 2008, Monte-Carlo Jazz Festival
  

References

1. ^ Rémi Coulom (2009). The Monte-Carlo Revolution in Go. JFFoS'2008: Japanese-French Frontiers of Science Symposium, slides as pdf
2. ^ Julien Kloetzer, Hiroyuki Iida, Bruno Bouzy (2007). The Monte-Carlo approach in Amazons. CGW 2007
3. ^ Richard J. Lorentz (2008). Amazons Discover Monte-Carlo. CG 2008
4. ^ Mark Winands and Yngvi Björnsson (2009). Evaluation Function Based Monte-Carlo LOA. pdf
5. ^ Richard J. Lorentz (2010). Improving Monte-Carlo Tree Search in Havannah. CG 2010
6. ^ 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
7. ^ UCT surprise for checkers ! by Daniel Shawul, CCC, March 25, 2011
8. ^ 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
9. ^ Raghuram Ramanujan, Ashish Sabharwal, Bart Selman (2010). On Adversarial Search Spaces and Sampling-Based Planning. ICAPS 2010
10. ^ Oleg Arenz (2012). Monte Carlo Chess. B.Sc. thesis, Darmstadt University of Technology, advisor Johannes Fürnkranz, pdf
11. ^ Guillaume Chaslot, Mark Winands, Jaap van den Herik (2008). Parallel Monte-Carlo Tree Search. CG 2008, pdf
12. ^ Edvard Munch, At the Roulette Table in Monte Carlo, 1893, Edvard Munch from Wikipedia
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. ^ Jeff Rollason (2015). Mixing the Immiscible - MCTS and evaluation. AI Factory, October 2015
18. ^ Monte Carlo in LOA by Mark Watkins, Open Chess Forum, December 30, 2010
19. ^ The Settlers of Catan from Wikipedia
20. ^ Blokus Duo from Wikipedia
21. ^ Search traps in MCTS and chess by Daniel Shawul, CCC, December 25, 2017
22. ^ NoGo (ICGA Tournaments)
23. ^ Ms. Pac-Man from Wikipedia
24. ^ Scotland Yard (board game) from Wikipedia
25. ^ Re: MC methods by Daniel Shawul, CCC, April 13, 2013
26. ^ Crossings from Wikipedia
27. ^ Epaminondas from Wikipedia
28. ^ 7 Wonders (board game) from WIkipedia
29. ^ 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
30. ^ Dap Hartmann (2017). Let's Catch the Train to Monte-Carlo. ICGA Journal, Vol. 39, No. 1
31. ^ Re: Minmax backup operator for MCTS by Brahim Hamadicharef, CCC, December 30, 2017
32. ^ Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » LCZero
33. ^ GitHub - suragnair/alpha-zero-general: A clean and simple implementation of a self-play learning algorithm based on AlphaGo Zero (any game, any framework!)
34. ^ A Simple Alpha(Go) Zero Tutorial by Oliver Roese, CCC, December 30, 2017
35. ^ David Silver, Gerald Tesauro (2009). Monte-Carlo Simulation Balancing. ICML 2009, pdf

What links here?

Up one level