IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 4, NO. 1, MARCH 2012 10
Fig. 3. Asymmetric tree growth [68].
any moment in time; allowing the algorithm to run for
additional iterations often improves the result.
It is possible to approximate an anytime version of
minimax using iterative deepening. However, the gran-
ularity of progress is much coarser as an entire ply is
added to the tree on each iteration.
3.4.3 Asymmetric
The tree selection allows the algorithm to favour more
promising nodes (without allowing the selection proba-
bility of the other nodes to converge to zero), leading
to an asymmetric tree over time. In other words, the
building of the partial tree is skewed towards more
promising and thus more important regions. Figure 3
from [68] shows asymmetric tree growth using the BAST
variation of MCTS (4.2).
The tree shape that emerges can even be used to gain a
better understanding about the game itself. For instance,
Williams [231] demonstrates that shape analysis applied
to trees generated during UCT search can be used to
distinguish between playable and unplayable games.
3.5 Comparison with Other Algorithms
When faced with a problem, the a priori choice between
MCTS and minimax may be difficult. If the game tree
is of nontrivial size and no reliable heuristic exists for
the game of interest, minimax is unsuitable but MCTS
is applicable (3.4.1). If domain-specific knowledge is
readily available, on the other hand, both algorithms
may be viable approaches.
However, as pointed out by Ramanujan et al. [164],
MCTS approaches to games such as Chess are not as
successful as for games such as Go. They consider a
class of synthetic spaces in which UCT significantly
outperforms minimax. In particular, the model produces
bounded trees where there is exactly one optimal action
per state; sub-optimal choices are penalised with a fixed
additive cost. The systematic construction of the tree
ensures that the true minimax values are known.
12
In
this domain, UCT clearly outperforms minimax and the
gap in performance increases with tree depth.
Ramanujan et al. [162] argue that UCT performs
poorly in domains with many trap states (states that lead
to losses within a small number of moves), whereas iter-
ative deepening minimax performs relatively well. Trap
states are common in Chess but relatively uncommon
in Go, which may go some way towards explaining the
algorithms’ relative performance in those games.
3.6 Terminology
The terms MCTS and UCT are used in a variety of
ways in the literature, sometimes inconsistently, poten-
tially leading to confusion regarding the specifics of the
algorithm referred to. For the remainder of this survey,
we adhere to the following meanings:
• Flat Monte Carlo: A Monte Carlo method with
uniform move selection and no tree growth.
• Flat UCB: A Monte Carlo method with bandit-based
move selection (2.4) but no tree growth.
• MCTS: A Monte Carlo method that builds a tree to
inform its policy online.
• UCT: MCTS with any UCB tree selection policy.
• Plain UCT: MCTS with UCB1 as proposed by Kocsis
and Szepesv
´
ari [119], [120].
In other words, “plain UCT” refers to the specific algo-
rithm proposed by Kocsis and Szepesv
´
ari, whereas the
other terms refer more broadly to families of algorithms.
4VARIATIONS
Traditional game AI research focusses on zero-sum
games with two players, alternating turns, discrete ac-
tion spaces, deterministic state transitions and perfect
information. While MCTS has been applied extensively
to such games, it has also been applied to other domain
types such as single-player games and planning prob-
lems, multi-player games, real-time games, and games
with uncertainty or simultaneous moves. This section
describes the ways in which MCTS has been adapted
to these domains, in addition to algorithms that adopt
ideas from MCTS without adhering strictly to its outline.
4.1 Flat UCB
Coquelin and Munos [68] propose flat UCB which effec-
tively treats the leaves of the search tree as a single multi-
armed bandit problem. This is distinct from flat Monte
Carlo search (2.3) in which the actions for a given state
are uniformly sampled and no tree is built. Coquelin
and Munos [68] demonstrate that flat UCB retains the
adaptivity of standard UCT while improving its regret
bounds in certain worst cases where UCT is overly
optimistic.
12. This is related to P-game trees (7.3).