Rolling Horizon Evolutionary Algorithms for General Video Game Playing
2021
Abstract
General video game playing aims to design an artificial agent capable of rational thought, which would achieve high-level play in any game, thus needing to remove domain knowledge and introduce techniques to gather information and statistics about the previously unknown game. While Monte Carlo Tree Search has dominated the area, Rolling Horizon Evolutionary Algorithms (RHEA) were shown in early work to have the potential of reaching an even better performance. This thesis presents a series of experiments carried out to analyse the performance and behaviour of RHEA, which evolves, online, a sequence of actions to play in a game. We analyse its various properties and parameters, as well as combinations with other algorithms. Results obtained are favourable and outperform previous state-of-the-art in several games. A deeper visual analysis tool, VERTIGO, was created to enable the capture of statistics live during any of the games within the General Video Game AI framework. The features extracted were also used to predict RHEA's performance, with great results even from the very early stages of a game. The multitude of parameters resulting from the several studies led to work on automatic optimisation, using the N-Tuple Bandit Evolutionary Algorithm and several other simpler methods. The algorithm's parameters were tuned both offline and online with mixed results, but high promise is found in helping the algorithm generalise better across a wider range of games, and even observe first win rates in extremely difficult environments. Applications of the algorithm in different games are also explored: RHEA is very aggressive in Pommerman, competitive in Tribes and a top contender in tabletop and real-life physics-simulating games. The thesis finally discusses new research directions and how RHEA could interact with humans and other artificial systems within the context of a present, continuous, 'always-on', interactive game-playing entity.URL: https://rdgain.github.io/assets/pdf/papers/gaina2021phd.pdf
Cite this work
@phdthesis{gaina2021phd,
author= {Raluca D. Gaina},
title= {{Rolling Horizon Evolutionary Algorithms for General Video Game Playing}},
year= {2021},
month= {May},
school= {Queen Mary University of London, UK},
url= {https://rdgain.github.io/assets/pdf/papers/gaina2021phd.pdf},
abstract= {General video game playing aims to design an artificial agent capable of rational thought, which would achieve high-level play in any game, thus needing to remove domain knowledge and introduce techniques to gather information and statistics about the previously unknown game. While Monte Carlo Tree Search has dominated the area, Rolling Horizon Evolutionary Algorithms (RHEA) were shown in early work to have the potential of reaching an even better performance. This thesis presents a series of experiments carried out to analyse the performance and behaviour of RHEA, which evolves, online, a sequence of actions to play in a game. We analyse its various properties and parameters, as well as combinations with other algorithms. Results obtained are favourable and outperform previous state-of-the-art in several games. A deeper visual analysis tool, VERTIGO, was created to enable the capture of statistics live during any of the games within the General Video Game AI framework. The features extracted were also used to predict RHEA's performance, with great results even from the very early stages of a game. The multitude of parameters resulting from the several studies led to work on automatic optimisation, using the N-Tuple Bandit Evolutionary Algorithm and several other simpler methods. The algorithm's parameters were tuned both offline and online with mixed results, but high promise is found in helping the algorithm generalise better across a wider range of games, and even observe first win rates in extremely difficult environments. Applications of the algorithm in different games are also explored: RHEA is very aggressive in Pommerman, competitive in Tribes and a top contender in tabletop and real-life physics-simulating games. The thesis finally discusses new research directions and how RHEA could interact with humans and other artificial systems within the context of a present, continuous, 'always-on', interactive game-playing entity.},
}
Comments
Content