About | |

What is MCTS? Monte Carlo Tree Search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems, typically move planning in combinatorial games. It combines the generality of random simulation with the precision of tree search. Research interest in MCTS has risen sharply due to its spectacular success with computer Go and potential application to a number of other difficult problems. Its application extends beyond games, and MCTS can theoretically be applied to any domain that can be described in terms of { Basic Algorithm The basic MCTS algorithm is simple: a search tree is built, node by node, according to the outcomes of simulated playouts. The process can be broken down into the following steps. 1. Selection 2. Expansion 3. Simulation 4. Backpropagation See the Tutorial page for an example of this process in action. Each node must contain two important pieces of information: an estimated value based on simulation results and the number of times it has been visited. In its simplest and most memory efficient implementation, MCTS will add one child node per iteration. Note, however, that it may be beneficial to add more than one child node per iteration depending on the application. Node Selection Bandits and UCB
where vi is the estimated value of the node, ni is the number of the times the node has been visited and N is the total number of times that its parent has been visited. C is a tunable bias parameter. Exploitation vs Exploration MCTS and UCT UCT may be described as a special case of MCTS, that is: UCT = MCTS + UCB. Benefits MCTS offers a number of advantages over traditional tree search methods. Aheuristic Asymmetric This makes MCTS suitable for games with large branching factors such as 19x19 Go. Such large combinatorial spaces typically cause problems for standard depth- or breadth-based search methods, but the adaptive nature of MCTS means that it will (eventually) find those moves that appear optimal and focus its search effort there. Anytime Elegant Drawbacks MCTS has few drawbacks, but they can be major. Playing Strength Speed Luckily, the performance of the algorithm can be sigificantly improved using a number of techniques. Improvements Dozens of MCTS enhancements have been suggested to date. These can generally be described as being either domain knowledge or domain independent. Domain Knowledge Domain knowledge can yield significant improvements, at the expense of speed and loss of generality. Domain Independent Context
It seems remarkable that this elegant algorithm was not discovered much sooner! Research Interest There have been over 150 research papers written on topics related to MCTS since its inception a few years ago, averaging out to over one new publication every fortnight. These include some 50 suggested variations, enhancements and optimisations to the algorithm, which would not be far from the total number of enhancements suggested for traditional tree search since its introduction in 1928. This new field of study is currently a hot research topic in AI, with many open research questions still to be addressed and answered. MCTS: State of the Art Imperial College London held the first international MCTS workshop in August 2010 on the theme of O. Teytaud, "State of the Art: What is MCTS, where is it now, and where is it going?” 2010 [Online]. Available: http://www.aigamesnetwork.org/_media/main:events:london2010.pdf M. Müller, “Challenges in Monte Carlo Tree Search,” 2010 [Online]. Available: http://www.aigamesnetwork.org/_media/main:events:london2010-mcts-challenges.pdf R. Hayward, “MoHex: Computer Hex world champion,” 2010 [Online]. Available: http://www.aigamesnetwork.org/_media/main:events:mohextalk.pdf H. Finnsson and Y. Björnsson, “CadiaPlayer: MCTS in General Game Playing,” 2010 [Online]. Available: http://www.aigamesnetwork.org/_media/main:events:cadiaplayer_lic_slides_print.pdf A. Rimmel, “Havannah, Monte Carlo Enhancements and Linear Transforms,” 2010 [Online]. Available: http://www.aigamesnetwork.org/_media/main:events:presmctsworkshop_rimmel.pdf |