Assignment 2: Ms. Pac-Man

This assignment is worth 20 points and has two parts.

1. Uniform-cost search (10 pts)

Implement uniform-cost search in Java. Write a general-purpose implementation that can search any problem that implements this interface:

// S = state type
interface Problem<S> {
  S initialState();
  List<Integer> actions(S state);
  S result(S state, int action);
  boolean isGoal(S state);
  int cost(S state, int action);        
}

(You may optionally modify this interface so that costs have type double rather than int. You may also optionally make the action type generic, since we will do that in the next assignment anyway.)

Provide a search() method that returns a Node<S> representing the goal node that was found, or null if no goal was found. Node<S> should contain at least these fields:

class Node<S> {
  public S state;
  public Node<S> parent;  // parent node, or null if this is the start node
  public int action;  // the action we took to get here from the parent
  public int pathCost;  // total cost from parent to this node
  …
}

You may add any more fields and/or methods to Node<S> that you like.

Your code should live in a class that looks like this:

// uniform-cost search
class Ucs<S> {
  public static <S> Node<S> search(Problem<S> prob) {
    … your implementation here …
  }     
}

Then the caller can invoke your search method like this, for example:

  Problem<Integer> p = new MyPuzzle();
  Node<Integer> result = Ucs.search(p);

Here are two Problem instances that you can use for testing:

It would be wise to ensure that your uniform-cost search implementation works on these problems before attempting to use it in your Ms. Pac-Man agent.

hints

    1. Check whether the new path is cheaper than the existing path. If it is, you want to record it, but you cannot simply update the path cost of the existing frontier node, since that will not change its position in the priority queue. Instead, you can remove the existing frontier node from the queue, and add a new node representing the new and cheaper path. With this approach, you will never have two nodes in the queue that represent the same state. However, removing an existing node is potentially slow, since the remove method of PriorityQueue runs in O(N).

    2. Check whether the new path is cheaper than the existing path. If it is, then add a new node representing the new and cheaper path, but leave the existing node in place in the queue as well, to avoid the expensive remove operation. With this approach, there may be multiple nodes in the queue that have the same state. So whenever you remove a node from the queue, you must check whether its state is already in the explored set. If so, you have already handled that state, so you should ignore the node.

    3. Always add a new node representing the new path, even if it is more expensive than the existing path. With this approach, you will have more duplicate nodes in the queue than in approach (2). As in approach (2), when you remove a node from the queue you will need to check whether it has already been explored.

    For the problems we will be solving in this course, any of these approaches is probably OK. If you use approach (1) or (2), you will need some way to quickly check whether a given state is in the frontier so that you can find its existing path cost. One way to do that is to use a HashMap<S, Node<S>> to keep a map from states to frontier nodes.

2. Ms. Pac-Man (10 pts)

Use uniform-cost search to play Ms. Pac-Man.

Download the Ms. Pac-Man Java code from the MsPacMan-vs-Ghosts-AI repository. Write your agent in the class game.controllers.pacman.examples.MyPacMan. I have provided a skeletal implementation in MyPacMan.java.

I recommend the following basic approach. In your agent code, create an instance of the Problem<S> interface above and call Ucs.search() on every game tick. Perform a uniform-cost search over the physical maze graph, not the abstract tree of game states. (Be sure that you understand the difference between these.)

Every possible position in the maze is a different node in the maze graph. There are about 1,000 of these (the exact number varies from level to level) and they are evenly spaced throughout the maze. Fortunately 1,000 is a small enough number that you can perform a uniform-cost search over this graph in under 40 ms (the per-tick time limit).

The initial node for your search should be Ms. Pac-Man's current position. I recommend that every pellet be a goal node, unless it is close to a non-edible ghost. Edible ghosts also make great goal nodes. :)

When Ucs.search() returns a goal Node, you can follow the parent chain all the way up to the initial node to find out which action was taken first. That is the direction that Ms. Pac-Man should go.

Assign costs to graph edges as necessary to avoid going along undesirable paths. Any edge that ends at a non-edible ghost should have a very high cost. You may also want to give high costs to edges that are close to ghost positions, or that move in a direction toward the ghosts. If you want to be smarter, consider not only where the ghosts are now, but where they are heading.

Remember that uniform-cost search (i.e. Dijkstra's algorithm) does not work for negative edge weights. So don't be tempted to assign negative weights to edges that lead to places you do want to go, such as power pellets – that won't work. A better approach is to make these be goal nodes.

scoring

I will test your agent using the main program in the class EvaluationAgentConsole in the cz.cuni.mff.amis.pacman.tournament package. That class is preconfigured to test your MyPacMan agent by playing 30 games, each with a different random seed. Note that in each game Ms. Pac-Man initially has 3 lives and may potentially go through many different levels.

To score 10 points for this part of the assignment, your agent must score an average of at least 10,000 points per game. I will give partial credit for lower scores, but no credit for any agent that averages less than 5,000 points per game.

All agents submitted before the soft deadline for this assignment will be entered into a tournament. Entries will be ranked by highest average score. In the tournament, I will evaluate agents by playing as many random games as necessary to ensure that the differences in average scores are statistically valid.

api

Study the API in interface Game; it has everything you need to find about the game state. Note that

Here are some of the most important methods: