Investigating UCT and RAVE: Steps towards a more robust method

The Monte-Carlo Tree Search (MCTS) algorithm Upper Confidence bounds applied to Trees (UCT) has become extremely popular in computer games research. Because of the importance of this family of algorithms, a deeper understanding of when and how their different enhancements work is desirable. To avoid hard-to-analyze intricacies of tournament-level programs in complex games, this work focuses on a simple abstract game: Sum of Switches (SOS).;In the SOS environment we measure the performance of UCT and two of popular enhancements: Score Bonus and the Rapid Action Value Estimation (RAVE) heuristic. RAVE is often a strong estimator, but there are some situations where it misleads a search. To mimic such situations, two different error models for RAVE are explored: random error and systematic bias. We introduce a new, more robust version of RAVE called RAVE-max to better cope with errors.