Combining Monte-Carlo Tree Search with Proof-Number Search

2022-06-08 · Elliot Doe, Mark H. M. Winands, Dennis J. N. J. Soemers, Cameron Browne

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%.

📄 PDF Abstract BibTeX arXiv:2206.03965

Code (0)

등록된 구현이 없습니다.

Tasks

Decision Making

Methods 이 논문이 사용한 방법론

Monte-Carlo Tree Search Monte-Carlo Tree Search is a planning algorithm that accumulates value estimates obtained from Monte Carlo simulations in order to successively direct simulations towards more…

Monte Carlo Tableau Proof Search

2016-11-18 · Michael Färber, Cezary Kaliszyk, Josef Urban

We study Monte Carlo Tree Search to guide proof search in tableau calculi. This includes proposing a number of proof-state evaluation heuristics, some of which are learnt from previous proofs. We present an implementatio…

Automated Theorem Proving

Proof Number Based Monte-Carlo Tree Search

2023-03-16 · Jakub Kowalski, Elliot Doe, Mark H. M. Winands, Daniel Górski 외

This paper proposes a new game-search algorithm, PN-MCTS, which combines Monte-Carlo Tree Search (MCTS) and Proof-Number Search (PNS). These two algorithms have been successfully applied for decision making in a range of…

Decision Making

TacticToe: Learning to Prove with Tactics

2018-04-02 · Thibault Gauthier, Cezary Kaliszyk, Josef Urban, Ramana Kumar 외

We implement a automated tactical prover TacticToe on top of the HOL4 interactive theorem prover. TacticToe learns from human proofs which mathematical technique is suitable in each proof situation. This knowledge is the…

CPU

Expected Work Search: Combining Win Rate and Proof Size Estimation

2024-05-09 · Owen Randall, Martin Müller, Ting Han Wei, Ryan Hayward

We propose Expected Work Search (EWS), a new game solving algorithm. EWS combines win rate estimation, as used in Monte Carlo Tree Search, with proof size estimation, as used in Proof Number Search. The search efficiency…

Position

StarCraft II Build Order Optimization using Deep Reinforcement Learning and Monte-Carlo Tree Search

2020-06-12 · Islam Elnabarawy, Kristijana Arroyo, Donald C. Wunsch II

The real-time strategy game of StarCraft II has been posed as a challenge for reinforcement learning by Google's DeepMind. This study examines the use of an agent based on the Monte-Carlo Tree Search algorithm for optimi…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+2