Efficient Sampling Method for Monte Carlo Tree Search Problem
Summary :
We consider Monte Carlo tree search problem, a variant of Min-Max 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 min-max 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.3 pp.392-398
- Publication Date
- 2014/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E97.D.392
- 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
Authors
Kazuki TERAOKA
Fujitsu Limited
Kohei HATANO
Kyushu University
Eiji TAKIMOTO
Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuki TERAOKA, Kohei HATANO, Eiji TAKIMOTO, "Efficient Sampling Method for Monte Carlo Tree Search Problem" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 3, pp. 392-398, March 2014, doi: 10.1587/transinf.E97.D.392.
Abstract: We consider Monte Carlo tree search problem, a variant of Min-Max 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 min-max 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E97.D.392/_p
Copy
@ARTICLE{e97-d_3_392,
author={Kazuki TERAOKA, Kohei HATANO, Eiji TAKIMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Sampling Method for Monte Carlo Tree Search Problem},
year={2014},
volume={E97-D},
number={3},
pages={392-398},
abstract={We consider Monte Carlo tree search problem, a variant of Min-Max 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 min-max 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.},
keywords={},
doi={10.1587/transinf.E97.D.392},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Efficient Sampling Method for Monte Carlo Tree Search Problem
T2 - IEICE TRANSACTIONS on Information
SP - 392
EP - 398
AU - Kazuki TERAOKA
AU - Kohei HATANO
AU - Eiji TAKIMOTO
PY - 2014
DO - 10.1587/transinf.E97.D.392
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2014
AB - We consider Monte Carlo tree search problem, a variant of Min-Max 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 min-max 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.
ER -
English
