MCTS for perft estimation

Monte Carlo Tree Search
Daniel Shawul
Posts: 2
Joined: Sun Jan 31, 2016 5:06 am

MCTS for perft estimation

Postby Daniel Shawul » Sun Jan 31, 2016 7:34 pm

Perft (partial game tree size) estimation can be a good testbed for MCTS experiments.

https://dl.dropboxusercontent.com/u/552 ... /perft.pdf

Abstract

Partial game tree sizes can be estimated using different methods
among which the most accurate is conducting monte-carlo simulations
of random games. This process resembles monte-carlo tree search
(MCTS) method as used for game playing in Computer Go, but it
has also some interesting differences. For instance the reward assigned
to a simulation is actually contained in the path taken, not in the terminal
position as is common in game playing. The article investigates
a new application of MCTS that is not meant for game playing but
estimating game tree size itself. The simplicity of the problem makes
it an ideal playground for studying MCTS method in general. All the
components of MCTS namely simulation, back-propagation, selection
and expansion are applicable for this problem as well, and comparisons
with MCTS for game playing are made whenever possible. The
selection policy most commonly used in MCTS, i.e. upper confidence
bound (UCB) formula, is inappropriate for this application thus new
formulae are derived for optimal tree and default selection policies.
The result is a partial game tree size estimator that converges rapidly
to a lower variance.

Rémi Coulom
Posts: 104
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: MCTS for perft estimation

Postby Rémi Coulom » Sun Jan 31, 2016 11:07 pm

Thanks Daniel. And welcome to the forum!


Return to “MCTS”

Who is online

Users browsing this forum: No registered users and 0 guests