Abstract
General video game playing is a challenging research area in which the goal is to find one algorithm that can play many games successfully. 'Monte Carlo Tree Search' (MCTS) is a popular algorithm that has often been used for this purpose. It incrementally builds a search tree based on observed states after applying actions. However, the MCTS algorithm always plans over actions and does not incorporate any higher level planning, as one would expect from a human player. Furthermore, although many games have similar game dynamics, often no prior knowledge is available to general video game playing algorithms. In this paper, we introduce a new algorithm called 'Option Monte Carlo Tree Search' (O-MCTS). It offers general video game knowledge and high level planning in the form of 'options', which are action sequences aimed at achieving a specific subgoal. Additionally, we introduce 'Option Learning MCTS' (OL-MCTS), which applies a progressive widening technique to the expected returns of options in order to focus exploration on fruitful parts of the search tree. Our new algorithms are compared to MCTS on a diverse set of twenty-eight games from the general video game AI competition. Our results indicate that by using MCTS's efficient tree searching technique on options, O-MCTS outperforms MCTS on most of the games, especially those in which a certain subgoal has to be reached before the game can be won. Lastly, we show that OL-MCTS improves its performance on specific games by learning expected values for options and moving a bias to higher valued options.
| Original language | English |
|---|---|
| Title of host publication | 2016 IEEE Conference on Computational Intelligence and Games, CIG 2016 |
| Publisher | IEEE |
| ISBN (Electronic) | 9781509018833 |
| DOIs | |
| Publication status | Published - 2 Jul 2016 |
| Event | 2016 IEEE Conference on Computational Intelligence and Games, CIG 2016 - Santorini, Greece Duration: 20 Sept 2016 → 23 Sept 2016 |
Publication series
| Name | IEEE Conference on Computatonal Intelligence and Games, CIG |
|---|---|
| Volume | 0 |
| ISSN (Print) | 2325-4270 |
| ISSN (Electronic) | 2325-4289 |
Conference
| Conference | 2016 IEEE Conference on Computational Intelligence and Games, CIG 2016 |
|---|---|
| Country/Territory | Greece |
| City | Santorini |
| Period | 20/09/16 → 23/09/16 |
Bibliographical note
Publisher Copyright:© 2016 IEEE.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
Fingerprint
Dive into the research topics of 'Monte Carlo Tree Search with options for general video game playing'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver