Evolving UCT alternatives for general video game playing

Abstract

We use genetic programming to evolve alternatives to the UCB1 heuristic used in the standard UCB formulation of Monte Carlo Tree Search. The fitness function is the performance of MCTS based on the evolved equation on playing particular games from the General Video Game AI framework. Thus, the evolutionary process aims to create MCTS variants that perform well on particular games; such variants could later be chosen among by a hyper-heuristic game-playing agent. The evolved solutions could also be analyzed to understand the games better. Our results show that the heuristic used for node selection matters greatly to performance, and the vast majority of heuristics perform very badly; furthermore, we can evolve heuristics that perform comparably to UCB1 in several games. The evolved heuristics differ greatly between games.