- 542 views
- 462 downloads
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
- Spring 2010
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- 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.