Reactiveness and navigation in computer games: Different needs, different approaches

This paper presents an approach to the Mario AI Benchmark problem, using the A* algorithm for navigation, and an evolutionary process combining routines for the reactiveness of the resulting bot. The Grammatical Evolution system was used to evolve Behaviour Trees, combining both types of routines, while the highly dynamic nature of the environment required specific approaches to deal with over-fitting issues. The results obtained highlight the need for specific algorithms for the different aspects of controlling a bot in a game environment, while Behaviour Trees provided the perfect representation to combine all those algorithms.

I. Introduction

Computer games can be an extremely challenging benchmark for Evolutionary Algorithms, and for Artificial Intelligence in general. The challenges presented go from static or dynamic path planning and single move optimisation, to adaptation in dynamic environments, learning and cooperative behaviours. Extra challenges include the need for humanlike behaviours, avoidance of repetitiveness, and conformity to the ability of human-opponents.