TY - GEN
T1 - Evolving game-specific UCB alternatives for general video game playing
AU - Bravi, Ivan
AU - Khalifa, Ahmed
AU - Holmgård, Christoffer
AU - Togelius, Julian
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - General AI
KW - Genetic programming
KW - Monte-Carlo tree search
UR - http://www.scopus.com/inward/record.url?scp=85017548504&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85017548504&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-55849-3_26
DO - 10.1007/978-3-319-55849-3_26
M3 - Conference contribution
AN - SCOPUS:85017548504
SN - 9783319558486
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 393
EP - 406
BT - Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings
A2 - Hidalgo, J.Ignacio
A2 - Cotta, Carlos
A2 - Hu, Ting
A2 - Tonda, Alberto
A2 - Burrelli, Paolo
A2 - Coler, Matt
A2 - Iacca, Giovanni
A2 - Kampouridis, Michael
A2 - Mora Garcia, Antonio M.
A2 - Squillero, Giovanni
A2 - Brabazon, Anthony
A2 - Haasdijk, Evert
A2 - Heinerman, Jacqueline
A2 - D Andreagiovanni, Fabio
A2 - Bacardit, Jaume
A2 - Nguyen, Trung Thanh
A2 - Silva, Sara
A2 - Tarantino, Ernesto
A2 - Esparcia-Alcazar, Anna I.
A2 - Ascheid, Gerd
A2 - Glette, Kyrre
A2 - Cagnoni, Stefano
A2 - Kaufmann, Paul
A2 - de Vega, Francisco Fernandez
A2 - Mavrovouniotis, Michalis
A2 - Zhang, Mengjie
A2 - Divina, Federico
A2 - Sim, Kevin
A2 - Urquhart, Neil
A2 - Schaefer, Robert
PB - Springer Verlag
T2 - 20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017
Y2 - 19 April 2017 through 21 April 2017
ER -