MCTS for perft estimation

[Daniel Shawul]

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]

Thanks Daniel. And welcome to the forum!