A Survey of Monte Carlo Tree Search Methods
The DOI matches its Crossref record; 220 of the 233 references it cites were found in a registry or an index.
Abstract
Monte Carlo tree search (MCTS) is a recently proposed search method that combines the precision of tree search with the generality of random sampling. It has received considerable interest due to its spectacular success in the difficult problem of computer Go, but has also proved beneficial in a range of other domains. This paper is a survey of the literature to date, intended to provide a snapshot of the state of the art after the first five years of MCTS research. We outline the core algorithm's derivation, impart some structure on the many variations and enhancements that have been proposed, and summarize the results from the key game and nongame domains to which MCTS methods have been applied. A number of open research questions indicate that the field is ripe for future work.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source doesn’t support the claim as written.
In the citing paper
“RL algorithms such as Deep Q-Network (DQN) [9], Proximal Policy Optimization (PPO) [10], and Monte Carlo Tree Search (MCTS) [11] disregard the previous trajectories.”
From Playtesting: What is Beyond Personas (2023) · cites this paper as [11]
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Items 201–220 of 220
Experiments in Monte-Carlo Amazons (ゲーム情報学(GI) Vol.2010-GI-24)
Kloetzer, J. (2010) · Medical Entomology and Zoology · Cited by 4
Müller, M. (2010) · ERA: Education and Research Archive (University of Alberta) · doi:10.7939/r3c24qp5j · Cited by 4 · cited 1×
“In addition, the use of transpositions allows information to be shared between these extra nodes where the state is unchanged.”
BackgroundOn the Laziness of Monte-Carlo Game Tree Search in Non-tight Situations
Althöfer, I. (2008) · Cited by 4
Cazenave, T., & Saffidine, A. (2010) · Cited by 3
To Create Intelligent Adaptive Neuro-Controller of Game Opponent from UCT-Created Data
Fu, Y., Yang, S. Y., He, S., Yang, J., Liu, X., Chen, Y., & Ji, D. (2009) · International Conference on Fuzzy Systems and Knowledge Discovery (FSKD) · doi:10.1109/fskd.2009.746 · Cited by 3 · cited 1×
“[88] used MCTS methods to improve the performance of their joint”
Methodvan den Herik, H. J. (2010) · ICGA Journal · Cited by 3
(2007) · Springer eBooks · doi:10.1007/978-0-387-49431-9_4 · Cited by 3
Towards MCTS for Creative Domains.
Browne, C. (2011) · Cited by 3
Self-citationImprovements and Evaluation of the Monte Carlo Tree Search Algorithm
Rimmel, A. (2009) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 2
Optimizing player's satisfaction through DDA of game AI by UCT for the Game Dead-End
Zhang, Y., He, S., Wang, J., Gao, Y., Yang, J., Yu, X., & Sha, L. (2010) · International Conference on Natural Computation (ICNC) · doi:10.1109/icnc.2010.5583721 · Cited by 2 · cited 1×
“Wins, draws and losses in simulations are assigned rewards of +1 , 0 and − 1 respectively (as usual), but proven wins and losses are assigned rewards of + ∞ and −∞ .”
BackgroundComputational and human intelligence in blind Go
Chou, P.-C., Doghmen, H., Lee, C.-S., Teytaud, F., Teytaud, O., Wang, H., Wang, M., Wu, L., & Yen, S.-J. (2011) · IEEE Conference on Computational Intelligence and Games (CIG) · doi:10.1109/cig.2011.6032012 · Cited by 2
CASTRO wins the Havannah Tournament
Lorentz, R. J. (2010) · ICGA Journal · doi:10.3233/icg-2010-33411 · Cited by 2
Using Intelligent Search Techniques to Play the Game Khet
Nijssen, J. A. M., & UITERWIJK, J. W. H. M. (2009) · Research Publications (Maastricht University) · doi:10.13140/2.1.1046.6082 · Cited by 2
Upper Confidence Trees and Billiards for Optimal Active Learning
Rolet, P., Sébag, M., & Teytaud, O. (2009) · HAL · Cited by 1
Analysis and Implementation of the Game OnTop
Briesemeister, R. (2009) · Cited by 1
Helmstetter, B., Lee, C.-S., Teytaud, F., Teytaud, O., Wang, M., & Yen, S.-J. (2011) · IEEE Conference on Computational Intelligence and Games (CIG) · doi:10.1109/cig.2011.6032014 · Cited by 1
Monte-Carlo Simulation Balancing Applied to 9x9 Go
Huang, S.-C. J., Coulom, R., & Lin, S.-S. (2010) · ICGA Journal · doi:10.3233/icg-2010-33402 · Cited by 1 · cited 1×
“5), a learned 3 × 3 pattern library [107] and sophisticated time management [108].”
BackgroundCASTRO Wins Havannah Tournament
Lorentz, R. J. (2012) · ICGA Journal · doi:10.3233/icg-2012-35115 · Cited by 1 · cited 1×
“Databases of opening move sequences of known utility.”
BackgroundMonte-Carlo approximation of temperature
Cazenave, T. (2015) · Cambridge University Press eBooks · doi:10.1017/9780511820809.004 · Cited by 1
(2010) · DSpace@MIT (Massachusetts Institute of Technology)
Research works printed but not linked: 34
- Entries marked with an asterisk (*) denote support material that does not directly cite MCTS methods
- [6] * --, 'Game Self-Play with Pure Monte-Carlo: The Basin Structure,' Friedrich-Schiller Univ., Jena, Tech. Rep., 2010. -
- [9] J. Asmuth and M. L. Littman, 'Approaching Bayes-optimalilty using Monte-Carlo tree search,' in Proc. 21st Int. Conf. Automat. Plan. Sched. , Freiburg, Germany, 2011. -
- [23] J. Borsboom, J.-T. Saito, G. M. J.-B. Chaslot, and J. W. H. M. Uiterwijk, 'A Comparison of Monte-Carlo Methods for Phantom Go,' in Proc. BeNeLux Conf. Artif. Intell. , Utrecht, Netherlands, 2007, pp. 57-64. -
- [29] --, 'On the Dangers of Random Playouts,' Int. Comp. Games Assoc. J. , vol. 34, no. 1, pp. 25-26, 2010. -
- Brügmann, 1993, Monte Carlo Go
- [37] --, 'Evolving Monte-Carlo Tree Search Algorithms,' Univ. Paris 8, Dept. Inform., Tech. Rep., 2007. -
- [53] G. M. J.-B. Chaslot, L. Chatriot, C. Fiter, S. Gelly, J.-B. Hoock, J. Perez, A. Rimmel, and O. Teytaud, 'Combining expert, offline, transient and online knowledge in Monte-Carlo exploration,' Lab. Rech. Inform. (LRI), Paris, Tech. Rep., 2008. -
- [74] N. G. P. Den Teuling, 'Monte-Carlo Tree Search for the Simultaneous Move Game Tron,' Univ. Maastricht, Netherlands, Tech. Rep., 2011. -
- [77] --, 'Move Ordering vs Heavy Playouts: Where Should Heuristics be Applied in Monte Carlo Go,' in Proc. 3rd North Amer. Game-On Conf. , Gainesville, Florida, 2007, pp. 35-42. -
- [81] M. Enzenberger, M. M¨ uller, B. Arneson, and R. B. Segal, 'Fuego - An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search,' IEEE Trans. Comp. Intell. AI Games , vol. 2, no. 4, pp. 259-270, 2010. - · DOI · Paper page
- [85] --, 'Simulation Control in General Game Playing Agents,' in Proc. Int. Joint Conf. Artif. Intell. Workshop Gen. Game Playing , Pasadena, California, 2009, pp. 21-26. -
- [90] S. Gelly, 'A Contribution to Reinforcement Learning; Application to Computer-Go,' Ph.D. dissertation, Univ. Paris-Sud, France, 2007. -
- [107] S.-C. Huang, 'New Heuristics for Monte Carlo Tree Search Applied to the Game of Go,' Ph.D. dissertation, Nat. Taiwan Normal Univ., Taipei, 2011. -
- [120] L. Kocsis, C. Szepesv´ ari, and J. Willemson, 'Improved MonteCarlo Search,' Univ. Tartu, Estonia, Tech. Rep. 1, 2006. -
- [121] S. K¨ onnecke and J. Waldmann, 'Efficient Playouts for the Havannah Abstract Board Game,' Hochschule Technik, Leipzig, Tech. Rep., 2009. -
- [131] * S. Lopez, 'Rybka's Monte Carlo analysis,' 2008. [Online]. Available: http://www.chessbase.com/newsdetail.asp?newsid= 5075 -
- [142] J. M´ ehat and T. Cazenave, 'Ary: A Program for General Game Playing,' Univ. Paris 8, Dept. Inform., Tech. Rep., 2008. - · doi:10.1163/1573-3912_ei2glos_sim_gi_00259
- [143] --, 'Monte-Carlo Tree Search for General Game Playing,' Univ. Paris 8, Dept. Info., Tech. Rep., 2008. -
- [151] K. Q. Nguyen, T. Miyama, A. Yamada, T. Ashida, and R. Thawonmas, 'ICE gUCT,' Int. Comput. Entertain. Lab., Ritsumeikan Univ., Tech. Rep., 2011. -
- [152] J. P. A. M. Nijssen, 'Playing Othello Using Monte Carlo,' Strategies , pp. 1-9, 2007. -
- [154] J. P. A. M. Nijssen and J. W. H. M. Uiterwijk, 'Using Intelligent Search Techniques to Play the Game Khet,' Maastricht Univ., Netherlands, Netherlands, Tech. Rep., 2009. -
- [164] --, 'On the Behavior of UCT in Synthetic Search Spaces,' in Proc. 21st Int. Conf. Automat. Plan. Sched. , Freiburg, Germany, 2011. -
- [176] C. D. Rosin, 'Nested Rollout Policy Adaptation for Monte Carlo Tree Search,' in Proc. 22nd Int. Joint Conf. Artif. Intell. , Barcelona, Spain, 2011, pp. 649-654. -
- [180] A. Saffidine, 'Utilisation dUCT au Hex,' Ecole Normale Super. Lyon, France, Tech. Rep., 2008. -
- [181] --, 'Some Improvements for Monte-Carlo Tree Search, Game Description Language Compilation, Score Bounds and Transpositions,' M.S. thesis, Paris-Dauphine Lamsade, France, 2010. -
- [188] F. C. Schadd, 'Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis,' M.S. thesis, Maastricht Univ., Netherlands, 2009. -
- [192] L. Schaefers, M. Platzner, and U. Lorenz, 'UCT-Treesplit - Parallel MCTS on Distributed Memory,' in Proc. 21st Int. Conf. Automat. Plan. Sched. , Freiburg, Germany, 2011. -
- [194] J. Sch¨ afer, 'The UCT Algorithm Applied to Games with Imperfect Information,' Diploma thesis, Otto-Von-Guericke Univ. Magdeburg, Germany, 2008. -
- [196] M. Shafiei, N. R. Sturtevant, and J. Schaeffer, 'Comparing UCT versus CFR in Simultaneous Games,' in Proc. Int. Joint Conf. Artif. Intell. Workshop Gen. Game Playing , Pasadena, California, 2009. -
- [206] J. A. Stankiewicz, 'Knowledge-Based Monte-Carlo Tree Search in Havannah,' M.S. thesis, Maastricht Univ., Netherlands, 2011. -
- [208] N. Sylvester, B. Lohre, S. Dodson, and P. D. Drake, 'A Linear Classifier Outperforms UCT in 9x9 Go,' in Proc. Int. Conf. Artif. Intell. , Las Vegas, Nevada, 2011, pp. 804-808. -
- [231] G. M. J. Williams, 'Determining Game Quality Through UCT Tree Shape Analysis,' M.S. thesis, Imperial Coll., London, 2010. -
- [236] M. H. M. Winands, Y. Bj¨ ornsson, and J.-t. Saito, 'Monte Carlo Tree Search in Lines of Action,' IEEE Trans. Comp. Intell. AI Games , vol. 2, no. 4, pp. 239-250, 2010. - · DOI
Cited by
Mastering the game of Go with deep neural networks and tree search
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016) · Nature · doi:10.1038/nature16961 · Cited by 15,612
“The previous major breakthrough in computer Go, the introduction of MCTS, led to corresponding advances in many other domains; for example, general game-playing, classical planning, partially observed planning, scheduling, and constraint satisfaction 35,36 .”
BackgroundMastering the game of Go without human knowledge
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017) · Nature · doi:10.1038/nature24270 · Cited by 9,084
“Once trained, these networks were combined with a Monte Carlo tree search (MCTS) 13–15 to provide a lookahead search, using the policy network to narrow down the search to highprobability moves, and using the value network (in conjunction with Monte Carlo rollouts using a fast rollout policy) to…”
MethodRecent advances and applications of machine learning in solid-state materials science
Schmidt, J., Marques, M. R. G., Botti, S., & Marques, M. A. L. (2019) · npj Computational Materials · doi:10.1038/s41524-019-0221-0 · Cited by 2,607
SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient
Yu, L., Zhang, W., Wang, J., & Yu, Y. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10804 · Cited by 2,285
The Arcade Learning Environment: An Evaluation Platform for General Agents
Bellemare, M. G., Naddaf, Y., Veness, J., & Bowling, M. (2013) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3912 · Cited by 2,161
“By expanding the more valuable branches of the tree and carrying out a random simulation at the leaf nodes, UCT is known to perform well in many different settings (Browne et al., 2012).”
Background
Metadata
- Authors
- Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., & Colton, S.
- Affiliations
- Imperial College London (GB)
- University of Bradford (GB)
- University of Essex (GB)
- ORCID
- Venue
- IEEE Transactions on Computational Intelligence and AI in Games
- Published
- 2012-03
- Volume
- 4
- Issue
- 1
- Pages
- 1-43
- ISSN
- 1943-068X (ISSN-L)
- 1943-0698
- OpenAlex
- W2126316555
- Semantic Scholar
- c37f1baac3c8ba30250084f067167ac3837cf6fd
- Cited by
- 2,970
- References
- 233
- Citations by year
- 2026: 163 · 2025: 220 · 2024: 244 · 2023: 269 · 2022: 294 · 2021: 308 · 2020: 305 · 2019: 263 · 2018: 230 · 2017: 186 · 2016: 155 · 2015: 117 · 2014: 125 · 2013: 60 · 2012: 28
- FWCI
- 103.94
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Computational Intelligence and AI in Games (publishedVersion)
- Research Publications (Maastricht University) (publishedVersion)
- Open Access at Essex (University of Essex) (acceptedVersion)
- Research Publications (Maastricht University) (submittedVersion, public-domain)
- Funders
- Engineering and Physical Sciences Research Council (EP/H048588/1, EP/H049061/2, EP/H049061/1, EP/I001964/1)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Keywords
- Monte Carlo tree search, computer Go, search algorithms, random sampling, game-playing agents, open research questions
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.