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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:AEU.10048/1087 |
| Date | 06 1900 |
| Creators | Tom, David |
| Contributors | Mueller, Martin (Computing Science), Buro, Michael (Computing Science), Hayes, Robert (Chemical and Materials Engineering) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 433743 bytes, application/pdf |
| Relation | D. Tom and M. Mueller. A Study of UCT and its Enhancements. In Advances in Computer Games 12, 2009. To appear in LNCS. |
Page generated in 0.0071 seconds