Title

Monte Carlo Tree Search: a review of recent modifications and applications
Link to the text (Springer Nature AI Review)
Link to PDF (66 pages)

BibTex to copy

@article{mctsSurvey2022,
doi = {10.1007/s10462-022-10228-y}, url = {https://doi.org/10.1007/s10462-022-10228-y}, year = {2023}, published = {19 July 2022}, volume = {56}, issue = {3}, pages = {2497--2562}, author = {Maciej {\'S}wiechowski and Konrad Godlewski and Bartosz Sawicki and Jacek Ma{\'n}dziuk}, title = {{Monte Carlo Tree Search: a review of recent modifications and applications}}, journal = {Artificial Intelligence Review} }
Sections

The survey consists of 9 sections. Researchers complimented me on Sections 5 and 7, in particular as most of the previous texts about MCTS were focused on games.
  • Section 1 - Introduction
  • Section 2 - Classic MCTS
  • - describes the base variant of the algorithm and the basic vocabulary
  • Section 3 - Games with Perfect Information
  • - focuses on extensions for games, wherein full information about the state is always available to all players.
    - subsections: action reduction, UCT alternatives, early termination, and opponent modelling.
  • Section 4 - Games with Imperfect Information
  • - subsections: determinization, information sets, heavy playouts, policy update, master combination (e.g. for competitions), and opponent modelling.
  • Section 5 - Combining MCTS with Machine Learning
  • - the best of both worlds?
  • Section 6 - MCTS with Evolutionary Methods
  • - topics such as: evolving heuristic functions, evolving policies, Rolling Horizon EA, and Evolutionary MCTS.
  • Section 7 - MCTS Applications Beyond Games
  • - e.g. in planning, security, chemical synthesis, scheduling, and logistics.
  • Section 8 - Parallelization
  • - how to execute MCTS on multiple cores and/or machines
  • Section 9 - Conclusions
  • - including predictions of future trends
Abstract

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.