Evolving game-specific UCB alternatives for general video game playing

Ivan Bravi, Ahmed Khalifa, Christoffer Holmgård, Julian Togelius

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    At the core of the most popular version of the Monte Carlo Tree Search (MCTS) algorithm is the UCB1 (Upper Confidence Bound) equation. This equation decides which node to explore next, and therefore shapes the behavior of the search process. If the UCB1 equation is replaced with another equation, the behavior of the MCTS algorithm changes, which might increase its performance on certain problems (and decrease it on others). In this paper, we use genetic programming to evolve replacements to the UCB1 equation targeted at playing individual games in the General Video Game AI (GVGAI) Framework. Each equation is evolved to maximize playing strength in a single game, but is then also tested on all other games in our test set. For every game included in the experiments, we found a UCB replacement that performs significantly better than standard UCB1. Additionally, evolved UCB replacements also tend to improve performance in some GVGAI games for which they are not evolved, showing that improvements generalize across games to clusters of games with similar game mechanics or algorithmic performance. Such an evolved portfolio of UCB variations could be useful for a hyper-heuristic game-playing agent, allowing it to select the most appropriate heuristics for particular games or problems in general.

    Original languageEnglish (US)
    Title of host publicationApplications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings
    EditorsJ.Ignacio Hidalgo, Carlos Cotta, Ting Hu, Alberto Tonda, Paolo Burrelli, Matt Coler, Giovanni Iacca, Michael Kampouridis, Antonio M. Mora Garcia, Giovanni Squillero, Anthony Brabazon, Evert Haasdijk, Jacqueline Heinerman, Fabio D Andreagiovanni, Jaume Bacardit, Trung Thanh Nguyen, Sara Silva, Ernesto Tarantino, Anna I. Esparcia-Alcazar, Gerd Ascheid, Kyrre Glette, Stefano Cagnoni, Paul Kaufmann, Francisco Fernandez de Vega, Michalis Mavrovouniotis, Mengjie Zhang, Federico Divina, Kevin Sim, Neil Urquhart, Robert Schaefer
    PublisherSpringer Verlag
    Pages393-406
    Number of pages14
    ISBN (Print)9783319558486
    DOIs
    StatePublished - 2017
    Event20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017 - Amsterdam, Netherlands
    Duration: Apr 19 2017Apr 21 2017

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume10199 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017
    CountryNetherlands
    City Amsterdam
    Period4/19/174/21/17

    Keywords

    • General AI
    • Genetic programming
    • Monte-Carlo tree search

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Evolving game-specific UCB alternatives for general video game playing'. Together they form a unique fingerprint.

  • Cite this

    Bravi, I., Khalifa, A., Holmgård, C., & Togelius, J. (2017). Evolving game-specific UCB alternatives for general video game playing. In J. I. Hidalgo, C. Cotta, T. Hu, A. Tonda, P. Burrelli, M. Coler, G. Iacca, M. Kampouridis, A. M. Mora Garcia, G. Squillero, A. Brabazon, E. Haasdijk, J. Heinerman, F. D Andreagiovanni, J. Bacardit, T. T. Nguyen, S. Silva, E. Tarantino, A. I. Esparcia-Alcazar, G. Ascheid, K. Glette, S. Cagnoni, P. Kaufmann, F. F. de Vega, M. Mavrovouniotis, M. Zhang, F. Divina, K. Sim, N. Urquhart, ... R. Schaefer (Eds.), Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings (pp. 393-406). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10199 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-55849-3_26