A Cellular Automaton Based Controller for a Ms. Pac-Man Agent
  Video games can be used as an excellent test bed for Artificial Intelligence
(AI) techniques. They are challenging and non-deterministic, this makes it very
difficult to write strong AI players. An example of such a video game is Ms.
Pac-Man. In this paper we will outline some of the previous techniques used to
build AI controllers for Ms. Pac-Man as well as presenting a new and novel
solution. My technique utilises a Cellular Automaton (CA) to build a
representation of the environment at each time step of the game. The basis of
the representation is a 2-D grid of cells. Each cell has a state and a set of
rules which determine whether or not that cell will dominate (i.e. pass its
state value onto) adjacent cells at each update. Once a certain number of
update iterations have been completed, the CA represents the state of the
environment in the game, the goals and the dangers. At this point, Ms. Pac-Man
will decide her next move based only on her adjacent cells, that is to say, she
has no knowledge of the state of the environment as a whole, she will simply
follow the strongest path. This technique shows promise and allows the
controller to achieve high scores in a live game, the behaviour it exhibits is
interesting and complex. Moreover, this behaviour is produced by using very
simple rules which are applied many times to each cell in the grid. Simple
local interactions with complex global results are truly achieved.
