Combining Monte-Carlo Tree Search with Proof-Number Search

• URL: http://arxiv.org/abs/2206.03965v1
• Date: Wed, 8 Jun 2022 15:28:42 GMT
• Title: Combining Monte-Carlo Tree Search with Proof-Number Search
• Authors: Elliot Doe and Mark H. M. Winands and Dennis J. N. J. Soemers and Cameron Browne
• Abstract summary: Proof-Number Search (PNS) and Monte-Carlo Tree Search (MCTS) have been successfully applied for decision making in a range of games. This paper proposes a new approach called PN-MCTS that combines these two tree-search methods by incorporating the concept of proof and disproof numbers into the UCT formula of MCTS. Experimental results demonstrate that PN-MCTS outperforms basic MCTS in several games including Lines of Action, MiniShogi, Knightthrough, and Awari, achieving win rates up to 94.0%.
• Score: 5.354801701968199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Proof-Number Search (PNS) and Monte-Carlo Tree Search (MCTS) have been successfully applied for decision making in a range of games. This paper proposes a new approach called PN-MCTS that combines these two tree-search methods by incorporating the concept of proof and disproof numbers into the UCT formula of MCTS. Experimental results demonstrate that PN-MCTS outperforms basic MCTS in several games including Lines of Action, MiniShogi, Knightthrough, and Awari, achieving win rates up to 94.0%.

Related papers

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• 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)
• Proof Number Based Monte-Carlo Tree Search [1.93674821880689]
  This paper proposes a new game-search algorithm, PN-MCTS, which combines Monte-Carlo Tree Search (MCTS) and Proof-Number Search (PNS) We define three areas where the additional knowledge provided by the proof and disproof numbers gathered in MCTS trees might be used. Experiments show that PN-MCTS is able to outperform MCTS in all tested game domains, achieving win rates up to 96.2% for Lines of Action.
  arXiv  Detail & Related papers  (2023-03-16T16:27:07Z)
• 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)
• 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)
• Prioritized Architecture Sampling with Monto-Carlo Tree Search [54.72096546595955]
  One-shot neural architecture search (NAS) methods significantly reduce the search cost by considering the whole search space as one network. In this paper, we introduce a sampling strategy based on Monte Carlo tree search (MCTS) with the search space modeled as a Monte Carlo tree (MCT) For a fair comparison, we construct an open-source NAS benchmark of a macro search space evaluated on CIFAR-10, namely NAS-Bench-Macro.
  arXiv  Detail & Related papers  (2021-03-22T15:09:29Z)
• Dual Monte Carlo Tree Search [0.0]
  We show that Dual MCTS performs better than one of the most widely used neural MCTS algorithms, AlphaZero, for various symmetric and asymmetric games. Dual MCTS uses two different search trees, a single deep neural network, and a new update technique for the search trees using a combination of the PUCB, a sliding-window, and the epsilon-greedy algorithm.
  arXiv  Detail & Related papers  (2021-03-21T23:34:11Z)
• Monte Carlo Tree Search: A Review of Recent Modifications and Applications [0.17205106391379024]
  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.
  arXiv  Detail & Related papers  (2021-03-08T17:44:15Z)
• Learning to Stop: Dynamic Simulation Monte-Carlo Tree Search [66.34387649910046]
  Monte Carlo tree search (MCTS) has achieved state-of-the-art results in many domains such as Go and Atari games. We propose to achieve this goal by predicting the uncertainty of the current searching status and use the result to decide whether we should stop searching.
  arXiv  Detail & Related papers  (2020-12-14T19:49:25Z)
• 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)

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.