Pacman spends his life running from ghosts, but things were not always so. Legend has it that many years ago, Pacman’s great grandfather Grandpac learned to hunt ghosts for sport. However, he was blinded by his power and could only track ghosts by their banging and clanging.
In this assignment, you will design Pacman agents that use sensors to locate and eat invisible ghosts. You’ll advance from locating single, stationary ghosts to hunting packs of multiple moving ghosts with ruthless efficiency.
This assignment includes an autograder for you to grade your answers on your machine. This can be run on all questions with the command:
python autograder.py
It can be run for one particular question, such as q2, by:
python autograder.py -q q2
It can be run for one particular test by commands of the form:
python autograder.py -t test_cases/q1/1-ObsProb
The code for this part of the assignment contains the following files, available as a zip archive.
| Files you'll edit: | |
bustersAgents.py |
Agents for playing the Ghostbusters variant of Pacman. |
inference.py |
Code for tracking ghosts over time using their sounds. |
| Not used for this version of the assignment: | |
bayesNet.py |
The BayesNet and Factor classes. |
factorOperations.py |
Operations to compute new joint or marginalized probability tables. |
| Supporting files you can ignore: | |
busters.py |
The main entry to Ghostbusters (replacing Pacman.py). |
bustersGhostAgents.py |
New ghost agents for Ghostbusters. |
distanceCalculator.py |
Computes maze distances, caches results to avoid re-computing. |
game.py |
Inner workings and helper classes for Pacman. |
ghostAgents.py |
Agents to control ghosts. |
graphicsDisplay.py |
Graphics for Pacman. |
graphicsUtils.py |
Support for Pacman graphics. |
keyboardAgents.py |
Keyboard interfaces to control Pacman. |
layout.py |
Code for reading layout files and storing their contents. |
util.py |
Utility functions. |
Files to Edit and Submit: You will fill in portions
of bustersAgents.py, inference.py,
and factorOperations.py during the
assignment. Once you have completed the assignment, you will submit
inference.py and bustersAgents.py. Please do not change the other files in this distribution or submit any of our original files other than this file.
Evaluation: Your code will be autograded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. However, the correctness of your implementation – not the autograder’s judgements – will be the final judge of your score. If necessary, we will review and grade assignments individually to ensure that you receive due credit for your work.
Academic Dishonesty: We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else’s code and submit it with minor changes, we will know. These cheat detectors are quite hard to fool, so please don’t try. We trust you all to submit your own work only; please don’t let us down. If you do, we will pursue the strongest consequences available to us.
Getting Help: You are not alone! If you find yourself stuck on something, contact the course staff for help. Office hours, section, and the discussion forum are there for your support; please use them. If you can’t make our office hours, let us know and we will schedule more. We want these assignments to be rewarding and instructional, not frustrating and demoralizing. But, we don’t know when or how to help unless you ask.
Discussion: Please be careful not to post spoilers.
In this version of Ghostbusters, the goal is to hunt down scared but invisible ghosts. Pacman, ever resourceful, is equipped with sonar (ears) that provides noisy readings of the Manhattan distance to each ghost. The game ends when Pacman has eaten all the ghosts. To start, try playing a game yourself using the keyboard.
python busters.py
The blocks of color indicate where the each ghost could possibly be, given the noisy distance readings provided to Pacman. The noisy distances at the bottom of the display are always non-negative, and always within 7 of the true distance. The probability of a distance reading decreases exponentially with its difference from the true distance.
Your primary task for this part of the assignment is to implement inference to track the ghosts. For the keyboard based game above, a crude form of inference was implemented for you by default: all squares in which a ghost could possibly be are shaded by the color of the ghost. Naturally, we want a better estimate of the ghost’s position.
While watching and debugging your code with the autograder, it will
be helpful to have some understanding of what the autograder is doing.
There are 2 types of tests in this assignment, as differentiated by their .test files found in the subdirectories of the test_cases folder. For tests of class DoubleInferenceAgentTest,
you will see visualizations of the inference distributions generated by
your code, but all Pacman actions will be pre-selected according to the
actions of the staff implementation. This is necessary to allow
comparision of your distributions with the staff’s distributions. The
second type of test is GameScoreTest, in which your BustersAgent will actually select actions for Pacman and you will watch your Pacman play and win games.
It is possible, though unlikely, for the autograder to time
out if running the tests with graphics. To accurately determine whether
or not your code is efficient enough, you should run the tests with the
--no-graphics
flag. If the autograder passes with this flag, then you will receive
full points, even if the autograder times out with graphics.
We will use the Forward Algorithm for HMM’s for exact inference.
For the rest of the tracking part of the assignment, we will be using the DiscreteDistribution class defined in inference.py
to model belief distributions and weight distributions. This class is
an extension of the built-in Python dictionary class, where the keys are
the different discrete elements of our distribution, and the
corresponding values are proportional to the belief or weight that the
distribution assigns that element. This question asks you to fill in the
missing parts of this class, which will be crucial for later questions
(even though this question itself is worth no points).
First, fill in the normalize
method, which normalizes the values in the distribution to sum to one,
but keeps the proportions of the values the same. Use the total
method to find the sum of the values in the distribution. For an empty
distribution or a distribution where all of the values are zero, do
nothing. Note that this method modifies the distribution directly,
rather than returning a new distribution.
Second, fill in the sample
method, which draws a sample from the distribution, where the
probability that a key is sampled is proportional to its corresponding
value. Assume that the distribution is not empty, and not all of the
values are zero. Note that the distribution does not necessarily have to
be normalized prior to calling this method. You may find Python’s
built-in random.random() function useful for this question.
There are no autograder tests for this question, but the correctness of your implementation can be easily checked. We have provided Python doctests as a starting point, and you can feel free to add more and implement other tests of your own. You can run the doctests using:
python -m doctest -v inference.py
Note that, depending on the implementation details of the sample method, some correct implementations may not pass the doctests that are provided. To thoroughly check the correctness of your sample method, you should instead draw many samples and see if the frequency of each key converges to be proportional of its corresponding value.
In this question, you will implement the getObservationProb method in the InferenceModule base class in inference.py.
This method takes in an observation (which is a noisy reading of the
distance to the ghost), Pacman’s position, the ghost’s position, and the
position of the ghost’s jail, and returns the probability of the noisy
distance reading given Pacman’s position and the ghost’s position. In
other words, we want to return
.
The distance sensor has a probability distribution over distance
readings given the true distance from Pacman to the ghost. This
distribution is modeled by the function busters.getObservationProbability(noisyDistance, trueDistance), which returns and is provided for you. You should use this function to help you solve the problem, and use the provided manhattanDistance function to find the distance between Pacman’s location and the ghost’s location.
However, there is the special case of jail that we have to handle as
well. Specifically, when we capture a ghost and send it to the jail
location, our distance sensor deterministically returns None, and nothing else (observation = None
if and only if ghost is in jail). One consequence of this is that if
the ghost’s position is the jail position, then the observation is None
with probability 1, and everything else with probability 0. Make sure
you handle this special case in your implementation; we effectively have
a different set of rules for whenever ghost is in jail, as well as
whenever observation is None.
To test your code and run the autograder for this question:
python autograder.py -q q1
In this question, you will implement the observeUpdate method in ExactInference class of inference.py
to correctly update the agent’s belief distribution over ghost
positions given an observation from Pacman’s sensors. You are
implementing the online belief update for observing new evidence. The observeUpdate
method should, for this problem, update the belief at every position on
the map after receiving a sensor reading. You should iterate your
updates over the variable self.allPositions
which includes all legal positions plus the special jail position.
Beliefs represent the probability that the ghost is at a particular
location, and are stored as a DiscreteDistribution object in a field called self.beliefs, which you should update.
Before typing any code, write down the equation of the inference problem you are trying to solve. You should use the function self.getObservationProb
that you wrote in the last question, which returns the probability of
an observation given Pacman’s position, a potential ghost position, and
the jail position. You can obtain Pacman’s position using gameState.getPacmanPosition(), and the jail position using self.getJailPosition().
In the Pacman display, high posterior beliefs are represented by bright colors, while low beliefs are represented by dim colors. You should start with a large cloud of belief that shrinks over time as more evidence accumulates. As you watch the test cases, be sure that you understand how the squares converge to their final coloring.
Note: your busters agents have a separate inference module for each
ghost they are tracking. That’s why if you print an observation inside
the observeUpdate function, you’ll only see a single number even though there may be multiple ghosts on the board.
To run the autograder for this question and visualize the output:
python autograder.py -q q2
If you want to run this test (or any of the other tests) without graphics you can add the following flag:
python autograder.py -q q2 --no-graphics
In the previous question you implemented belief updates for Pacman based on his observations. Fortunately, Pacman’s observations are not his only source of knowledge about where a ghost may be. Pacman also has knowledge about the ways that a ghost may move; namely that the ghost can not move through a wall or more than one space in one time step.
To understand why this is useful to Pacman, consider the following scenario in which there is Pacman and one Ghost. Pacman receives many observations which indicate the ghost is very near, but then one which indicates the ghost is very far. The reading indicating the ghost is very far is likely to be the result of a buggy sensor. Pacman’s prior knowledge of how the ghost may move will decrease the impact of this reading since Pacman knows the ghost could not move so far in only one move.
In this question, you will implement the elapseTime method in ExactInference. The elapseTime
step should, for this problem, update the belief at every position on
the map after one time step elapsing. Your agent has access to the
action distribution for the ghost through self.getPositionDistribution. In order to obtain the distribution over new positions for the ghost, given its previous position, use this line of code:
newPosDist = self.getPositionDistribution(gameState, oldPos)
Where oldPos refers to the previous ghost position. newPosDist is a DiscreteDistribution object, where for each position p in self.allPositions, newPosDist[p] is the probability that the ghost is at position p at time t + 1, given that the ghost is at position oldPos at time t.
Note that this call can be fairly expensive, so if your code is timing
out, one thing to think about is whether or not you can reduce the
number of calls to self.getPositionDistribution.
Before typing any code, we suggest you write down the equation of the inference problem you are trying to solve. The task here is a little different from the generic HMM problem described in the slides and text in that you are tracking multiple objects. However, you can think of each ghost as a separeate HMM, i.e., you don't need to tack their joint distribution.
In order to test your predict implementation separately from your update implementation in the previous question, this question will not make use of your update implementation.
Since Pacman is not observing the ghost’s actions, these actions will not impact Pacman’s beliefs. Over time, Pacman’s beliefs will come to reflect places on the board where he believes ghosts are most likely to be given the geometry of the board and ghosts’ possible legal moves, which Pacman already knows.
For the tests in this question we will sometimes use a ghost with random movements and other times we will use the GoSouthGhost.
This ghost tends to move south so over time, and without any
observations, Pacman’s belief distribution should begin to focus around
the bottom of the board. To see which ghost is used for each test case
you can look in the .test files.
You may find the diagram below showing Bayes Net/ Hidden Markov model for
what is happening helpful in organizing your thoughts. Still, you should rely on the above description for
implementation because some parts are implemented for you (i.e. getPositionDistribution is abstracted to be .
To run the autograder for this question and visualize the output:
python autograder.py -q q3
If you want to run this test (or any of the other tests) without graphics you can add the following flag:
python autograder.py -q q3 --no-graphics
As you watch the autograder output, remember that lighter squares indicate that pacman believes a ghost is more likely to occupy that location, and darker squares indicate a ghost is less likely to occupy that location. For which of the test cases do you notice differences emerging in the shading of the squares? Can you explain why some squares get lighter and some squares get darker?
Now that Pacman knows how to use both his prior knowledge and his
observations when figuring out where a ghost is, he is ready to hunt
down ghosts on his own. We will use your observeUpdate and elapseTime
implementations together to keep an updated belief distribution, and
your simple, greedy agent will choose an action based on the latest
ditsibutions at each time step. In the simple greedy strategy, Pacman
assumes that each ghost is in its most likely position according to his
beliefs, then moves toward the closest ghost. Up to this point, Pacman
has moved by randomly selecting a valid action.
Implement the chooseAction method in GreedyBustersAgent in bustersAgents.py.
Your agent should first find the most likely position of each remaining
uncaptured ghost, then choose an action that minimizes the maze
distance to the closest ghost.
To find the maze distance between any two positions pos1 and pos2, use self.distancer.getDistance(pos1, pos2). To find the successor position of a position after an action:
successorPosition = Actions.getSuccessor(position, action)
You are provided with livingGhostPositionDistributions, a list of DiscreteDistribution objects representing the position belief distributions for each of the ghosts that are still uncaptured.
If correctly implemented, your agent should win the game in q8/3-gameScoreTest
with a score greater than 700 at least 8 out of 10 times. Note: the
autograder will also check the correctness of your inference directly,
but the outcome of games is a reasonable sanity check.
We can represent how our greedy agent works with the following modification to the previous diagram. The arc from the previous time step obseravtions to the pacman state reflects how Pacman is making his action choices. (Not everybody will find this sort of visualization helpful, so don't let it confuse you if you alread feel confident in how you are thinking about this problem.)
To run the autograder for this question and visualize the output:
python autograder.py -q q4
If you want to run this test (or any of the other tests) without graphics you can add the following flag:
python autograder.py -q q4 --no-graphics