Investigating UCT and RAVE: steps towards a more robust method

  • Author / Creator
    Tom, David
  • 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.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.