Monte Carlo Tree Search: a review of recent modifications and applications
By Maciej Swiechowski, K. Godlewski, B. Sawicki, Jacek Ma'ndziuk. Artificial Intelligence Review, 2021
441 citations recorded by the source corpus.
Monte Carlo Tree Search (MCTS) is a powerful approach to designing game-playing bots or solving sequential decision problems. The method relies on intelligent tree search that balances exploration and exploitation. MCTS performs random sampling in the form of simulations and stores statistics of actions to make more educated choices in each subsequent iteration. The method has become a state-of-the-art technique for combinatorial games. However, in more complex games (e.g. those with a high branching factor or real-time ones) as well as in various practical domains (e.g. transportation, scheduling or security) an efficient MCTS application often requires its problem-dependent modification or integration with other techniques. Such domain-specific modifications and hybrid approaches are the main focus of this survey. The last major MCTS survey was published in 2012. Contributions that appeared since its release are of particular interest for this review.
Subfields: Artificial Intelligence, Developmental and Educational Psychology, Sociology and Political Science
View Paper: https://www.semanticscholar.org/paper/c7fa68b000db6bca4ba10ec42565497f7df91f02
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Damai Dai
- Peiyi Wang
- Zhihong Shao
- Samrat Phatale
- Abhinav Rastogi
- Andy Zhou
- Haohan Wang
- Michal Shlapentokh-Rothman
In Sociology and Political Science
Citations in the corpus
- Improve Mathematical Reasoning in Language Models by Automated Process Supervision (2024, positive): “AlphaGo (Silver et al., 2016) and AlphaGo Zero (Silver et al., 2017) were able to achieve great performance with MCTS and deep reinforcement learning.”
- Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations (2023, methodology): “Inspired by Monto Carlo Tree Search (Kocsis & Szepesvári, 2006; Coulom, 2006; Silver et al., 2016; ´Swiechowski et al., 2023), we define the quality of a reasoning step as its potential to deduce the correct answer.”
- Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models (2023, methodology): “MCTS runs for k episodes; for each episode, it starts from the root (i.e., initial state) and iteratively conducts two steps to expand the tree: 1) Expansion , where multiple children states s are explored from the current parent state p by sampling n actions, and 2) Selection , where the children w”