
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Efficient Sampling Method for Monte Carlo Tree Search Problem
Kazuki TERAOKA Kohei HATANO Eiji TAKIMOTO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E97D
No.3
pp.392398 Publication Date: 2014/03/01
Online ISSN: 17451361 Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—) Category: Computational Learning Theory, Game Keyword: Monte Carlo tree search, random sampling, game, UCT,
Full Text: PDF(453.5KB) >>Buy this Article
Summary:
We consider Monte Carlo tree search problem, a variant of MinMax tree search problem where the score of each leaf is the expectation of some Bernoulli variables and not explicitly given but can be estimated through (random) playouts. The goal of this problem is, given a game tree and an oracle that returns an outcome of a playout, to find a child node of the root which attains an approximate minmax score. This problem arises in two player games such as computer Go. We propose a simple and efficient algorithm for Monte Carlo tree search problem.

