Title: Monte Carlo Tree Search for Asymmetric Trees,
Abstract: We present an extension of Monte Carlo Tree Search (MCTS) that strongly
increases its efficiency for trees with asymmetry and/or loops. Asymmetric
termination of search trees introduces a type of uncertainty for which the
standard upper confidence bound (UCB) formula does not account. Our first
algorithm (MCTS-T), which assumes a non-stochastic environment, backs-up tree
structure uncertainty and leverages it for exploration in a modified UCB
formula. Results show vastly improved efficiency in a well-known asymmetric
domain in which MCTS performs arbitrarily bad. Next, we connect the ideas about
asymmetric termination to the presence of loops in the tree, where the same
state appears multiple times in a single trace. An extension to our algorithm
(MCTS-T+), which in addition to non-stochasticity assumes full state
observability, further increases search efficiency for domains with loops as
well. Benchmark testing on a set of OpenAI Gym and Atari 2600 games indicates
that our algorithms always perform better than or at least equivalent to
standard MCTS, and could be first-choice tree search algorithms for
non-stochastic, fully-observable environments.