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

  • Monte-Carlo
  • RAVE
  • UCT
  • Abstract Games
  • RAVE-max
  • Artificial Intelligence

• Graduation date

  Spring 2010

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3WX3C

• 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.