Using Genetic Programming for Agents in Non-Deterministic Games

Abstract

The aim of this thesis is to explore the possibility of using Genetic Programming to create agents that play non-deterministic games at a human level. The game that is used to test the hypothesis is Ms. Pac-Man; an old arcade game. The reason for choosing this game is that there is a competition whose object it is to create an agent for the game only using the visual data of the game. This allows me to compare my results against human players and, others who have been trying to solve the same problem. The best score a human has achieved is 921,360 points by Abdner Ashman in 2005, while the agents in the competition have only received a score of 36,280 points. A modified emulator is used to run the original binary of the game. The modifications are made to allow the agents easier access to key properties of the game. They also make it possible to run the game as a background process, which allows more than one emulator to run in parallel over multiple machines. This makes it easier to run larger populations over many generations. The ideas around how to solve the problem sees large changes during the development of the project. A path-finding algorithm, A*, is introduced to decrease the search space for the GP Library. The algorithm is modified by the agents to control where to move. Even though the results from the thesis are not as good as hoped, we do see agents that perform near competition level. The late discovery of a bug in the game-API made progress difficult. Especially since a large amount of time was used on different solutions to the problem that proved ineffective. However, the thesis does show that it is possible to make agents, through Genetic Programming, that improves when playing non-deterministic games. Further research is needed to show if this approach may prove better than humans at playing Ms. Pac-Man.