The Pacman Project

Abstract

This project has been made for the University of Maastricht, Faculty of Humanities and Sciences. It is part of the Master Artificial Intelligence and was planned to run from Febuary to June 2008. The project incorporates several courses; Games and AI, Knowledge Management and Knowledge-System Development, Intelligent Search Techniques and Knowledge Retrieval.
The goal of the project was to create a real-life Pac-Man game, like the one being played in the streets of Manhattan, but partially automated in such a way players could run through the city using Personal Digital Assistants (PDA). The PDA-application was intended to be an assistant to the person playing the game, giving them advice about where to go. The project-group tutor was Dr. J. Derks and the project examiners were Dr. E. Hoenkamp and Dr.ir. P.H.M. Spronck. We would take a moment here to thank them for their work and guidance, it has been a great help to us throughout the project.

 

1.1 Introduction

PacMan is a game in which a player directs an agent (Pacman) through a maze. The goal of Pacman is to collect pills. In order to collect them, Pacman has to move through virtually all corridors in the maze.

The challenge for Pacman is posed by the four ghosts, named Inky, Pinky, Dinky, and Clyde (don’t ask me why). The ghosts hunt for Pacman, and when one of them manages to touch Pacman, Pacman loses a life.

On the maze there are also four power pills. If Pacman collects one of those, for a short period of time he can kill the ghosts by touching them.

 

Figure 1.1
Figure 1.1 - PacMan

 

Some people have approached this game in a zany way: they play it live. One of them dons a Pacman suit, while the others don ghost suits, and the ghosts start to hunt Pacman on the streets. For instance, PacManhattan describes a live Pacman game that takes place on New York’s Manhattan Island.

 

Figure 1.2
Figure 1.2 - A Live Pacman player

 

In PacManhattan, the state of the game is maintained by five generals, who are located in one room. Each of the generals is in phone contact with one of the players. It seems possible to get rid of these generals, and let a digital technology take care of maintaining the game state (note that the presence of the generals might be necessary because of the high buildings in Manhattan which makes GPS systems unreliable; however, that need not be the case for other cities).

 

1.2 The Live Pacman Assistant

The goal of the project is to build an intelligent Live Pacman assistant.
Imagine this: In a city (for instance Maastricht), virtual pills are dropped in several streets. A Pacman player must visit these streets to collect the pills. One to four ghost players are attempting to hunt down Pacman. The Pacman player wins when he manages to collect all the pills. The ghost players win if they manage to touch Pacman. If Pacman consumes a power pill, he is invincible for two minutes and can destroy ghosts by touching them. A destroyed ghost has to return to his start position before being allowed to hunt Pacman again. These are basically the rules of PacManhattan.

 

Figure 1.3
Figure 1.3 - The generals at work

 

All players carry a mobile phone or PDA with a built-in GPS and network connection. A server application collects the GPS data, so it knows where all the players are and which pills are still in the game world. The server can decide when Pacman wins (when all pills are collected) or when the ghosts win (when one of them is in the same location as Pacman; alternatively, in the case of noisy GPS data, the players declare the game over when Pacman is caught).
The server provides the players with the locations of the pills. Of course, pills that are collected are not included. It also provides each player with the position of all the ghosts. This means that Pacman knows where everybody is, but the ghosts do not know where Pacman is, although they might be able to deduce the location of Pacman from the disappearance of pills. Note that if there are relatively few pills, the game starts to gain similarities with the classic board game Scotland Yard.
An intelligent Live Pacman assistant will support Pacman and/or the ghosts in deciding where they should move. To this end, they have to collect map data and other relevant data online, reason about this data, and quickly provide advice on the direction in which a player should move. Players can ignore such advice, just as they can ignore advice from a TomTom, simply by moving differently.

In short:

 

1.3 The Assignments

The students should implement the Live Pacman server, and assistants for both Pacman and the ghosts. Depending on the number of students involved, different groups are created for implementing a ghost assistant and a Pacman assistant (though both should, of course, use the same server data).
If the students cannot get access to suitable hardware, a simulation environment will be made available, where each player drives a virtual agent on a map displayed on a PC; however, actual city data should be used, and the assistants should collect their data from the web.

 

1.4 Schedule

During the first period, students develop a concrete plan for the system and look into background literature if available. They should also design and implement a prototype intelligence for the assistants, who guides players traversing a simple graph (so no real city data).
During the second period, the students research what suitable city data amounts to, how it can be collected, and how it can be used to create a data structure that the assistants can use to reason with.
During the third period, the students will implement the server and assistants, and evaluate their results.
If the students wish to approach the project in different steps, that is allowed, as long as they communicate this to the examiners.

 

1.5 Project Coordination & Members

The examiner of project AI 1-2 is Pieter Spronck supported by Eduard Hoenkamp.
Jean Derks is coordinating the project and tutoring the groups. Every week he will have a meeting with each project group.

The members of this project are:

 

Index | Next >>>