Monte Carlo Tree Search (MCTS) Algorithm
Jump to navigation
Jump to search
A Monte Carlo Tree Search (MCTS) Algorithm is a tree search algorithm that is a Monte Carlo search algorithm.
- Context:
- It can be implemented by a Monte Carlo Tree Search System (that solves an MCTS task).
- Example(s):
- Counter-Example(s):
- See: Search Algorithm, Decision Process, Go-Playing Algorithm.
References
2017
- (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/Monte_Carlo_tree_search Retrieved:2017-10-8.
- In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in game play. Two leading examples of Monte Carlo tree search are the computer game Total War: Rome II's implementation in their high level campaign AI and recent computer Go programs, but it also has been used in other board games, as well as real-time video games and non-deterministic games such as poker (see history section).
2012
- (Gelly et al., 2012) ⇒ Sylvain Gelly, Levente Kocsis, Marc Schoenauer, Michèle Sebag, David Silver, Csaba Szepesvári, and Olivier Teytaud. (2012). “The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions.” In: Communications of the ACM Journal, 55(3). doi:10.1145/2093548.2093574
2012b
- (Browne et al., 2012) ⇒ Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. (2012). “A Survey of Monte Carlo Tree Search Methods.” In: Computational Intelligence and AI in Games, IEEE Transactions on, 4(1). doi:10.1109/TCIAIG.2012.2186810
- 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. ...