Monte Carlo Tree Search: A Review of Recent Modifications and Applications

• URL: http://arxiv.org/abs/2103.04931v2
• Date: Tue, 9 Mar 2021 13:04:22 GMT
• Title: Monte Carlo Tree Search: A Review of Recent Modifications and Applications
• Authors: Maciej \'Swiechowski, Konrad Godlewski, Bartosz Sawicki, Jacek Ma\'ndziuk
• Abstract summary: 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. The method has become a state-of-the-art technique for games, however, in more complex games.
• Score: 0.17205106391379024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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 has been published in 2012. Contributions that appeared since its release are of particular interest for this review.

Related papers

• PathFinder: Guided Search over Multi-Step Reasoning Paths [80.56102301441899]
  We propose PathFinder, a tree-search-based reasoning path generation approach. It enhances diverse branching and multi-hop reasoning through the integration of dynamic decoding. Our model generalizes well to longer, unseen reasoning chains, reflecting similar complexities to beam search with large branching factors.
  arXiv  Detail & Related papers  (2023-12-08T17:05:47Z)
• LightZero: A Unified Benchmark for Monte Carlo Tree Search in General Sequential Decision Scenarios [32.83545787965431]
  Building agents based on tree-search planning capabilities with learned models has achieved remarkable success in classic decision-making problems, such as Go and Atari. It has been deemed challenging or even infeasible to extend Monte Carlo Tree Search (MCTS) based algorithms to diverse real-world applications. In this work, we introduce LightZero, the first unified benchmark for deploying MCTS/MuZero in general sequential decision scenarios.
  arXiv  Detail & Related papers  (2023-10-12T14:18:09Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring [15.308312172985486]
  This work investigates the Monte Carlo Tree Search (MCTS) method combined with dedicateds for solving the Weighted Vertex Coloring Problem. In addition to the basic MCTS algorithm, we study several variants where conventional random simulation is replaced by other simulation strategies. We conduct experiments on well-known benchmark instances to assess these combined MCTS variants.
  arXiv  Detail & Related papers  (2023-04-24T14:50:33Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning. CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance. It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
  arXiv  Detail & Related papers  (2022-10-04T07:34:06Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Monte Carlo Tree Search for high precision manufacturing [55.60116686945561]
  We make use of an expert-based simulator and adapt the MCTS default policy to deal with the manufacturing process. Common reasons for this are that there is no efficient simulator of the process available or there exist problems in applying MCTS to the complex rules of the process.
  arXiv  Detail & Related papers  (2021-07-28T14:56:17Z)
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
  When developing an algorithm for optimization, it is commonly assumed that parameters such as edge weights are exactly known as inputs. In this article, we review recently proposed techniques for pure exploration problems with limited feedback.
  arXiv  Detail & Related papers  (2020-12-31T12:40:52Z)
• Playing Carcassonne with Monte Carlo Tree Search [0.0]
  We explore the use of the vanilla Monte Carlo Tree Search (MCTS) and the Rapid Action Value Estimation (MCTS-RAVE) in the game of Carcassonne. We compare the strengths of the MCTS-based methods with the Star2.5 algorithm, previously reported to yield competitive results in the game of Carcassonne.
  arXiv  Detail & Related papers  (2020-09-27T22:35:53Z)
• Unlucky Explorer: A Complete non-Overlapping Map Exploration [0.949996206597248]
  We introduce the Maze Dash puzzle as an exploration problem where the agent must find a Hamiltonian Path visiting all the cells. An optimization has been applied to the proposed Monte-Carlo Tree Search (MCTS) algorithm to obtain a promising result. Our comparison indicates that the MCTS-based approach is an up-and-coming method that could cope with the test cases with small and medium sizes.
  arXiv  Detail & Related papers  (2020-05-28T17:19:24Z)
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search [8.22379888383833]
  Combination of Monte-Carlo Tree Search (MCTS) and deep reinforcement learning is state-of-the-art in two-player perfect-information games. We describe a search algorithm that uses a variant of MCTS which we enhanced by 1) a novel action value normalization mechanism for games with potentially unbounded rewards, 2) defining a virtual loss function that enables effective search parallelization, and 3) a policy network, trained by generations of self-play, to guide the search.
  arXiv  Detail & Related papers  (2020-05-22T18:02:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.