Asymmetric Move Selection Strategies in Monte-Carlo Tree Search: Minimizing the Simple Regret at Max Nodes

2016-05-08 · Yun-Ching Liu, Yoshimasa Tsuruoka

The combination of multi-armed bandit (MAB) algorithms with Monte-Carlo tree search (MCTS) has made a significant impact in various research fields. The UCT algorithm, which combines the UCB bandit algorithm with MCTS, is a good example of the success of this combination. The recent breakthrough made by AlphaGo, which incorporates convolutional neural networks with bandit algorithms in MCTS, also highlights the necessity of bandit algorithms in MCTS. However, despite the various investigations carried out on MCTS, nearly all of them still follow the paradigm of treating every node as an independent instance of the MAB problem, and applying the same bandit algorithm and heuristics on every node. As a result, this paradigm may leave some properties of the game tree unexploited. In this work, we propose that max nodes and min nodes have different concerns regarding their value estimation, and different bandit algorithms should be applied accordingly. We develop the Asymmetric-MCTS algorithm, which is an MCTS variant that applies a simple regret algorithm on max nodes, and the UCB algorithm on min nodes. We will demonstrate the performance of the Asymmetric-MCTS algorithm on the game of $9\times 9$ Go, $9\times 9$ NoGo, and Othello.

📄 PDF Abstract BibTeX arXiv:1605.02321

Code (0)

등록된 구현이 없습니다.

Convergence of Monte Carlo Tree Search in Simultaneous Move Games

2013-12-01 · NeurIPS 2013 12 · Viliam Lisy, Vojta Kovarik, Marc Lanctot, Branislav Bosansky

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 inst…

Form

Learning Position Evaluation Functions Used in Monte Carlo Softmax Search

2019-01-30 · Harukazu Igarashi, Yuichi Morioka, Kazumasa Yamamoto

This paper makes two proposals for Monte Carlo Softmax Search, which is a recently proposed method that is classified as a selective search like the Monte Carlo Tree Search. The first proposal separately defines the node…

Position Reinforcement Learning

Monte Carlo Methods for the Game Kingdomino

2018-07-12 · Magnus Gedda, Mikael Z. Lagerkvist, Martin Butler

Kingdomino is introduced as an interesting game for studying game playing: the game is multiplayer (4 independent players per game); it has a limited game depth (13 moves per player); and it has limited but not insignifi…

What Makes Good Few-shot Examples for Vision-Language Models?

2024-05-22 · Zhaojun Guo, Jinghui Lu, Xuejing Liu, Rui Zhao 외

Despite the notable advancements achieved by leveraging pre-trained vision-language (VL) models through few-shot tuning for downstream tasks, our detailed empirical study highlights a significant dependence of few-shot l…

Active Learning Few-Shot Learning Prompt Learning

Monte Carlo Game Solver

2020-01-15 · Tristan Cazenave

We present a general algorithm to order moves so as to speedup exact game solvers. It uses online learning of playout policies and Monte Carlo Tree Search. The learned policy and the information in the Monte Carlo tree a…