Convergence of Monte Carlo Tree Search in Simultaneous Move Games
In this paper, we study Monte Carlo tree search (MCTS) in zero-sum extensive-form games with perfect information and simultaneous moves. We present a general template of MCTS algorithms for these games, which can be instantiated by various selection methods. We formally prove that if a selection method is $\epsilon$-Hannan consistent in a matrix game and satisfies additional requirements on exploration, then the MCTS algorithm eventually converges to an approximate Nash equilibrium (NE) of the extensive-form game. We empirically evaluate this claim using regret matching and Exp3 as the selection methods on randomly generated and worst case games. We confirm the formal result and show that additional MCTS variants also converge to approximate NE on the evaluated games.
Code (0)
등록된 구현이 없습니다.
Tasks
FormSimilar Papers 제목 키워드 기반
Monte Carlo Tree Search for a single target search game on a 2-D lattice
Monte Carlo Tree Search (MCTS) is a branch of stochastic modeling that utilizes decision trees for optimization, mostly applied to artificial intelligence (AI) game players. This project imagines a game in which an AI pl…
Monte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms
Monte Carlo Tree Search and Monte Carlo Search have good results for many combinatorial problems. In this paper we propose to use Monte Carlo Search to design mathematical expressions that are used as exploration terms f…
Measurable Monte Carlo Search Error Bounds
Monte Carlo planners can often return sub-optimal actions, even if they are guaranteed to converge in the limit of infinite samples. Known asymptotic regret bounds do not provide any way to measure confidence of a recomm…
Monte Carlo Tree Search Based Tactical Maneuvering
In this paper we explore the application of simultaneous move Monte Carlo Tree Search (MCTS) based online framework for tactical maneuvering between two unmanned aircrafts. Compared to other techniques, MCTS enables effi…
Feature Acquisition using Monte Carlo Tree Search
Feature acquisition algorithms address the problem of acquiring informative features while balancing the costs of acquisition to improve the learning performances of ML models. Previous approaches have focused on calcula…