An investigation into the effectiveness of heavy rollouts in UCT

Abstract

Monte Carlo Tree Search (MCTS) is a family of directed search algorithms that has gained widespread attention in recent years, with its domain-independent nature making it particularly attractive to fields such as General Game Playing. Despite the vast amount of research into MCTS, the dynamics of the algorithm are still not yet fully understood. In particular, the effect of using knowledge-heavy or biased rollouts in MCTS still remains largely unknown, with surprising results demonstrating that better-informed rollouts do not necessarily result in stronger agents. We show that MCTS is well-suited to a class of domains possessing a smoothness property, and that any error due to incorrect bias is compounded in non-smooth domains, particularly for low-variance simulations.