Interesting games through stage complexity and topology

Abstract

In (Yannakakis and Hallam, 2004) we saw that the online learning (OLL) mechanism proposed is a robust approach which manages to emerge opponents (i.e Ghosts)

that increase the interest of the prey-predator, multiagent Pac-Man computer game. It also demonstrated

high adaptability to changing types of Pac-Man player (i.e. playing strategies) in a relevantly simple playing stage. In the work presented here we attempt to test the OLL mechanism over more complex stages and furthermore to explore the relation between the interest measure and the topology of the stage. In order to distinguish between

stages of different complexity, we require an appropriate measure to quantify this feature of the stage. This

measure is as follows

C = 1/E{L} (1)

where C is the complexity measure and E{L} is the average corridor length of the stage.

According to (1), complexity is inversely proportional to the average corridor length of the stage. That is, the longer the average corridor length, the easier for the

Ghosts to block Pac-Man and, therefore, the less complex the stage.