Undergraduate thesis


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


  • Hector Laria Mantecón
  • Jorge Sanchez Cremades
  • José Miguel Tajuelo Garrigós
  • Jorge Vieira Luna


Medium vs Legacy
High vs Legacy



Click on the legend entries to hide.

Pac-Man Ghosts Score Level Time
max avg std max avg std max avg std
Low-level Random 900 151 117 1 0.071 0.257 5094 2151 972.1
Medium-level 64600 48558 10780 18 15 3.4 24000 21579 4470
High-level 55480 32704 13237 18 10.4 4.3 24000 17457 6784
Low-level Legacy 120 120 0 0 0 0 600 425 34.5
Medium-level 15960 6358 2883 3 0.9 0.7 4973 1916 730
High-level 20040 5972 2832 4 1 0.6 8364 2026 1020