Ms Pac-Man versus Ghost-Team Competition

Simon M. Lucas

Note: some of the software descriptions on this web page are now out of date.  For the most recent code check out the source from here: http://code.google.com/p/ms-pacman/ (or download the .zip file from the download section there).

This competition will run in conjunction with IEEE CEC 2011.

See also: Ms Pac-Man screen capture competition.

Contents

Introduction

Ms. Pac-Man is a challenging and interesting game that is usually viewed form the perspective of the Ms. Pac-Man agent, and this has already been the subject of an on-going series of competitions.  The game is also provides an excellent environment for testing multi-agent strategies for controlling the team of ghosts, with the aim either of optimising the playability of the game, or simply to minimise the score obtained by the agent.  It is this latter more measurable objective that provides the focus of this competition.  For this purpose an efficient simulator of the game has been developed with simple software interfaces with which to connect your controllers.  The screenshot below shows a game in progress on the simulator.  A future aim is to finish work on an adapter to the Ms. Pac-Man Screen Capture Competition so that agent controllers that adhere to the interfaces provided here can be used for both competition.

The software is written in Java, and currently only a Java interface is provided.  There are plans to make this available via network and web interfaces, but that's work in progress.

At each game tick the controllers (for agent and for ghost-team) are provided with the current state of the game.

For the competition the game runs in real time with approximately 25 game ticks per second.  Each controller will run in a separate thread (or possibly a separate JVM) and can take as long as it wants to respond.  The natural downside of taking too long is that the game state it's reasoning about may be out of date.  Each cycle the game engine waits for 40ms, then updates it's state based on the most recent outputs (joystick directions) from each controller. 

The simulator can also be run in full-speed non-visual synchronous mode, which may exceed 100 games per second (depending on complexity and ability of controller; more able controllers lead to longer-lasting games) and is useful for evolving controllers.

 

Rules

The aim for a Pac-Man agent is to obtain the highest average score against each ghost-team, given 20 games.  The winning agent is the one who obtains the highest average against most ghost teams.  The average of the averages will be used as a tie-break.

Each of these games is based on a single life (unlike the original game that had three lives plus an extra life at 10,000 points).

The aim for a ghost-team controller is to minimise the average score obtained against it by each agent.  The winning ghost team against each agent will be team with the lowest average score against most teams.  The lowest average of the averages will be used as a tie-break.

Contestants may provide both an agent controller and a ghost-team controller, but these should not collude to provide an advantage to an opponent via self-sacrifice.

Software Interfaces

The software kit is provided complete with source code for all the implementing classes.  However, implementation details may change, and therefore to make your controllers more resilient to change, they should only refer to the interfaces described in this section. 

The interfaces and classes listed below are fairly stable but will undergo some minor modifications.  In particular, GameStateInterface should also return the level.

Note that in Java, method declarations in interfaces are public by default so there's no need to specify each method as being public.

GameStateInterface

import java.util.BitSet;

public interface GameStateInterface {
    GameStateInterface copy();
    void next(int pacDir, int[] ghostDirs);
    Agent getPacman();
    MazeInterface getMaze();
    BitSet getPills();
    BitSet getPowers();
    GhostState[] getGhosts();
    int getScore();
    int getGameTick();
    int getEdibleGhostScore();
}

The state of the pills and power-pills are stored in BitSets.  On the plus side this enables a very compact encoding of this aspect of the Game State.  On the minus side, it means a bit more work to get meaningful information such as finding the nearest pill (but not too much - see NearestPillDistance for an example of how to get this information).

AgentInterface

The interface for the Pac-Man agent has a single method action which takes the game state as input and returns the desired movement direction.  Any complexity is encapsulated in the Game State, the public methods of which are listed in the Game State Interface.

public interface AgentInterface {
    // the return value specifies the direction of the joystick
    int action(GameStateInterface gs);
}

GhostTeamInterface

This similar to the AgentInterface, except that it returns an array of ints, one for each ghost.

public interface GhostTeamController {
    public int[] getActions(GameStateInterface gs);
}

MazeInterface

The MazeInterface class gives access to all public information accessible about the maze.

public interface MazeInterface {
    int dist(Node a, Node b);
    ArrayList<Node> getPowers();
    ArrayList<Node> getPills();
    ArrayList<Node> getMap();
    int getWidth();
    int getHeight();
    Node[][] getNode2DArray();
    Node ghostStart();
    Node pacStart();
    Node getNode(int x, int y);
    Node getNode(int index);
}

Agent

The Agent class stores the current state of the Ms. Pac-Man agent in the game engine.  This is defined by the current position of it.

public class Agent implements Constants {
    // the only state of a PacMan agent is it's current direction
    // and location in the maze
    // (Pac-Man will continue along current direction until it hits a wall)
    public Node current;
    int curDir;

// ... rest of class omitted

GhostState

Holds the state of a single ghost.  Ghosts have three possible states (edible, inedible, and returning, the latter one shown as a pair of eyes).  The edible state is stored as an int that decrements each game tick until the ghost is no longer edible.  The previous node is stored to prevent the ghost from turning back on itself (unless a global reversal event is raised).  The delayCounter and delay variables store how long the ghost waits at the start of the level before leaving the lair, and the current state of the delay.

public class GhostState implements Constants {
    public int edibleTime;
    public Node current, previous;
    int curDir;
    int delay;
    int delayCounter;

Node

The maze is modelled as a set of nodes, and stores these nodes in two ways: as a two-dimensional array of Node, and as a Node Graph, where the graph stores the adjacent nodes to each node.  To enable efficient computation, each Node has a unique node index going from zero to (n-1), where there are n nodes in the graph.  It also stores the indexes into the pill and power pill bit vectors, in the case that the node has an associated pill or power-pill.

The screen snippet below shows the graph nodes coloured in red.  Although the game agents appear to move smoothly around the maze, they are actually moving from one graph node to the next.  In the image below the pills are offset slightly for display purposes, but in the model they reside exactly at graph node locations.

Sample Agent Controllers

This section provides the code for some sample controllers to help get you started.

Pure Random Controller

This controller makes a random choice of joystick state direction every time step.  There are 5 joystick states (up, down, left, right, neutral) but most of the time only two will be valid directions.  Just as in the original game, if an invalid direction is selected then the Pac-Man continues on her current direction.

public class RandomAgent implements AgentInterface, Constants {
    public int action(GameStateInterface gs) {
        return rand.nextInt(dx.length); 
    }
}

Random Controller with No Reversal

This performs slightly better than the pure random controller, since it spends less time going pointlessly back and forth.  It creates an array list of possible next nodes, which are all the adjacent nodes not including the previous node the agent was at, then selects one of these at random.

public class RandomNonReverseAgent implements AgentInterface, Constants {
    Node prev;
    public int action(GameStateInterface gs) {
        Node cur = gs.getPacman().current;
        ArrayList<Node> possibles = new ArrayList<Node>();
        for (Node n : cur.adj) {
            if (!n.equals(prev)) possibles.add(n);
        }
        Node next = possibles.get(rand.nextInt(possibles.size()));
        prev = cur;
        return Utilities.getWrappedDirection(cur, next, gs.getMaze());
    }
}

Nearest Pill Eater

This agent finds the nearest food pill (ignoring power pills) and heads straight for it, regardless of any ghosts in the way!  

public class SimplePillEater implements AgentInterface, Constants {

    NearestPillDistance npd = new NearestPillDistance();

    public int action(GameStateInterface gs) {
        Node current = gs.getPacman().current;
        // update the score function with the current node
        // and the game state
        npd.score(gs, current);
        // now choose the next state by scoring the adjacent
        // nodes with this function
        Node next = Utilities.getClosest(current.adj, npd.closest, gs.getMaze());
        // return the direction of the next node
        int dir = Utilities.getWrappedDirection(current, next, gs.getMaze());
        return dir;
    }
}

This uses a node value function: NearestPillDistance, code shown below.  This demonstrates how to access the set of pills via the MazeInterface class, and to use the pillIndex of each node to check whether or not it has already been eaten.

This demonstrates how to check access the set of pills via the MazeInterface class, and to use the pillIndex of each node to check whether or not it has already been eaten.

public class NearestPillDistance implements NodeScore {
    static int max = Integer.MAX_VALUE;

    public double score(GameStateInterface gs, Node node) {
        // most obvious way: iterate over the set of pills
        int minDist = max;
        for (Node n : gs.getMaze().getPills()) {
            // check the state of this pill
            // by querying the BitSet of pill states
            if (gs.getPills().get(n.pillIndex)) {
                // this pill is on, but is it closer?
                if (gs.getMaze().dist(node, n) < minDist) {
                    minDist = gs.getMaze().dist(node, n);
                    closest = n;
                }
            }
        }
        return minDist;
    }
}

Sample Ghost Team Controllers

Remember that ghosts are not normally allowed to reverse direction, so the only choice points are at junctions.  Despite this, the ghost team controller is polled every game tick.  Hence the controller can update it's planning ready to respond immediately when a decision is actually required.  However, all the controllers below are stateless and apply the same logic every time getActions is called.

RandTeam

The random ghost team chooses a random direction for each ghost every time the action method is called.  The game engine enforces the no-reverse rule, so these random choices are only effective at junctions.  The complete code (apart from import statements) is shown below.

public class RandTeam implements GhostTeamController, Constants {
    int[] dirs;
    public RandTeam() {
        // no need to create an array every time
        this.dirs = new int[nGhosts];
    }

    public int[] getActions(GameStateInterface gs) {
        // choose a random direction every time
        // the game engine will enforce legality
        for (int i=0; i<dirs.length; i++) {
             dirs[i] = rand.nextInt(dx.length);
        }
        return dirs;
    }
}

LegacyTeam

This implements the ghost controllers from [1].  Note that some utility methods are used to simplify the code.  Each ghost in this team is based on a node value controller: it selects the adjacent node which optimises the value of some node score function.  The behaviours (which follow from the node score functions) are as follows for each ghost in turn, where each of these scoring functions (except for Sue) is based on minimising a distance to Pac-Man:

public class LegacyTeam implements GhostTeamController, Constants {
    // this team follows the same algorithm as the simulator
    // used for Lucas, Proceedings of IEEE CIG 2005
    int[] dirs;
    NodeScore[] scorers;
    ArrayList<Node> options;
    GhostProxy[] proxies;

    public LegacyTeam() {
        this.dirs = new int[nGhosts];
        options = new ArrayList<Node>();
        scorers = new NodeScore[]{
            new PathScore(), new EuclideanScore(),
            new ManhattanScore(), new RandScore(),
        };
    }

    public int[] getActions(GameStateInterface gs) {
      for (int i=0; i<dirs.length; i++) {
            GhostState gh = gs.getGhosts()[i];
            options.clear();
            for (Node n : gh.current.adj) {
                // turning back is not a valid option
                // only consider valid options
                if (!n.equals(gh.previous)) options.add(n);
            }
            dirs[i] = Utilities.getMinDir(
                options, gh.current, scorers[i], gs);
        }
        return dirs;
    }
}

Software toolkit

The current software toolkit is provided here: http://code.google.com/p/ms-pacman/  

It provides all you need to get started in writing some hand-coded controllers, but does not include any software for neural networks or evolutionary algorithms.  There are many classes, and use of a good IDE such as Intellij IDEA, Eclipse, or Netbeans is strongly recommended. 

Get started by running the class screenpac.model.Game in module screenpac.  This runs the controllers in synchronous mode for maximum efficiency and simplicity.  Note the boolean variable visual at the head of this source file.  Setting this true runs a single game in visual mode.  Setting this false runs 100 games with no display.  For the controllers provided, 100 games in non-visual mode takes around 1 second on a Dell XPS 1330M laptop.

Also provided is the screenpac.model.GameThread class.  This runs the game in asynchronous mode, with each controller running in a separate thread.  Each cycle, the controllers are notified of the current game state and the game thread then waits for 40ms before updating the game state and continuing to the next cycle.  If controllers do not respond in time then their previous response is used.

Soon to come is the client-server software that will enable to game thread and the controller threads to run in separate JVMs, and on separate machines.

The code is split into two modules for historic reasons.  The old module is called pacman and the new module is called screenpac.  A future release may remove the pacman module.  Currently it is only used to create the maze graph. 

The current release includes all four original mazes.

Submitting an Entry

Submissions should include all the code (including all the source code) required to run your controller, a brief (e.g. 3-page) report explaining your method, and include a statement of the average score it obtains against the supplied sample agents.  This should all be packaged up in a .zip file and submitted by email to Simon Lucas.

Entry conditions and Dates

IEEE CEC 2011

Please notify Simon Lucas of your intention to submit an entry for this competition, stating whether you intend to provide an agent controller or a ghost-team controller (or both).

There will be a prize of $250 for the winning entry in each of the two categories (ghost team and agent), subject to a sufficient level of achievement.  This is defined as significantly outperforming the supplied benchmark controllers (which will not be particularly strong).  The cash prize is only open to registered conference delegates.  Anyone can enter remotely, and the winner will receive an official IEEE Certificate.

Dates

Controllers must be submitted by May 20th 2011.  The final results will be presented during the competitions session at IEEE CEC 2011 (5-8 June).

References

[1] Simon M. Lucas, Evolving a Neural Network Location Evaluator to Play Ms. Pac-Man, IEEE Symposium on Computational Intelligence and Games (2005), pages: 203 -- 210 [pdf]