Introduction

Ever since the birth of video-games we’ve seen Artificial Intelligence techniques applied to them: Character behaviour, enemy strategies, pathfinding, etc. We want to explore Grammatical Evolution (a Genetic Programming variant) to evolve game strategies generated from the derivation of defined grammar rules. For this purpose, we experimented with the evolution of a bot for Ms. Pac-Man, a well-known game which can have many sub-goals, like surviving the most time possible, eating the most pills, killing as many ghosts as it can, or go through a lot of levels before dying to the ghosts.

Particularly, we experimented with controllers based on two different grammars, with high and medium level actions respectively. Due to the complexity of video-games and how useful it could be for an artificial intelligence to modify its behaviour in real time, we want to check the results of multi-objective optimization in grammatical evolution. And how we can achieve the subgoals we consider more important in a situation by simply changing the evaluation functions we use in the grammatical evolution algorithm.

In this work we will show that this approach based on Grammatical Evolution gets excellent results and we will see that bots produced can obtain high scores and complete several levels, even better results than the coded bots included, or other known evolutionary bots.

• Undergraduate thesis Detailed description of all the work behind this project (not completely in English, sorry). link
• Paper Scientific article published on CoSECiVi
  Spanish Society for VideoGame Sciences Conference
  2017. link

Examples

Grammars

Results

Click on the legend entries to hide.