Project 4: Static Ghostbusters


Introduction

In this project, you will design agents that locate invisible ghosts on a grid using sensors, and then guess their locations.  For this project, the ghosts do not move.

The code for this project contains the following files, available as a zip archive.

Ghostbusters
ghostbusters.py The main code for the game of Ghostbusters. You should familiarize yourself with the general outline of this code, which you will be interacting with for the next project as well.
tutorial.py Tutorial script -- start here!
sensorDistributions.py Plug-in for the GUI interface. You can ignore this file.
gui.py The graphical user interface for Ghostbusters. You can ignore this file.
graphicsUtils.py Graphics utilities. You can ignore this file.
util.py Tools used in ghostbusters. You may be familiar with some of these by now, and they will save you a lot of time.
Agents
ghostbusterAgent.py You will implement the getAction() method in this file.
staticInferenceModule.py You will implement the getGhostTupleDistributionGivenObservations() and getReadingDistributionGivenObservations() methods in this file.
dynamicInferenceModule.py (You should not modify this file until project 5.)

 

What to submit: You will fill in portions of ghostbusterAgent.py and staticInferenceModule.py. You should submit only these files, plus a writeup and partners file as usual. Please don't change any other files.

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.

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. Instead, contact the course staff if you are having trouble.

Ghostbusters and BNs

In this CS 5300/6300 version of Ghostbusters, the goal is to locate and bust the ghost(s) hiding on the grid.  However, you aren't guessing at random.  You can obtain information about the ghosts' whereabouts by dropping sensors at grid positions.  These sensors return readings, which are correlated with the distance to the closest ghost.  You only have one try to bust each ghost, and once you finish busting, successful or not, the game ends.  There are two tasks of interest in this game.  First, we would like to compute probability distributions over ghost locations given sensor readings.  This is the inference problem.  Second, we want to decide, given our current beliefs about ghost locations, whether to sense or bust, and where.  This is the decision problem.  You will build agents to solve both of these problems.

You can probably figure out the rules just by playing, but here's the official version:

At any time, you can sense or bust.  If you wish to sense, left-click a grid location, and you will reveal the sensor reading at that location.  You cannot "re-sense" the same location.  The intuition is that time is frozen and your observation, though noisy, will not change until the world changes (which it will not do until project 5).  The observation you get from a sensor will be one of RED (closest), ORANGE, YELLOW, or GREEN (furthest), which roughly indicates how close the closest ghost is to the sensor location.  The exact sensor model is given in sensorDistributions.py.  Your agent loses one point per sensor revealed.

Once you are ready to bust, click the BUST button. It will turn red to indicate that you are in busting mode.  All you can do now is bust as many times as there are ghosts on the board.  Once all your busts are used up, you will see which were hits and which were misses, and the game will end.  All ghosts in any squares you bust are hit (you can hit multiple ghosts with a single bust if you're lucky).  Your agent gains 50 points for each ghost that is bust.

In the next project, you will also have the ability to advance time, at which point the ghosts will move and the observations will be updated, but for now we are only concerned with the one time step scenario. The "TIME+1" button is therefore intentionally greyed out.

To get started with Ghostbusters, let's play a few games.  Run ghostbusters from the command line:

  python ghostbusters.py -w -q

As before, there are many command-line options, which you can display with the -h option.  In this case, the -w flag shows the true locations of the ghosts, and the -q flag suppresses the display of agent beliefs (since you have no agent yet).

Left-click to sensor a square or click the bust button to begin busting.  Remember that once you bust, the game will end, whether you hit the ghost or not.  Try a bigger layout using (-l medium).  Now, using (-l test), a 3 by 3 layout, try sensing all 9 squares. Notice that there is no noise in the sensor readings -- that is, the information provided by RED, ORANGE, YELLOW, and GREEN is deterministic given the location of the ghost.  You can set the sensor reading distribution at the command line with (-s noisy). Take a look at sensorDistributions.py to see what the deterministic and noisy distributions look like.  It should be more difficult to find the ghost using the noisy distribution.  Try some games on the medium layout with noisy sensors and no true locations to get an idea of what we're asking the agents to do!

Question 0 (no points)  Work through the brief tutorial (tutorial.py), which provides an introduction to the major ghostbuster classes and functions you will find helpful.

Let's formalize the static ghostbusters domain as a Bayes' net.  The full network structure is shown below (for a 2x3 layout):

The G node represents the tuple of ghost positions.  You could imagine having a separate variable for each ghost; this formulation is equivalent.  You can get the prior distribution over ghost tuples from Game.getInitialDistribution().  In general, there are a lot of important Game.getX() methods, and your agents and inference modules will have self.game objects.  Note that if there is only one ghost in play, you will still get singleton tuples of locations, not just a bare location.  There is a random variable Ri,j for each position (row, col) = (i, j).  Each reading depends only on the position.  The conditional distribution for Ri,j given a value for G can be fetched with Game.getReadingDistributionGivenGhostTuple().

Question 1 (4 points)  Try running without the -q flag, if you haven't already. 

  python ghostbusters.py -w

  The GUI will now display the agent's posterior beliefs about the location of the ghost (G) given the revealed sensors ({Ri,j=ri,j}).  However, as you haven't written anything yet, there is a placeholder which always returns the prior distribution over locations.  You can control the prior distribution by invoking the game with the --prior priorstring flag, where priorstring can be either uniform (default) or border. Make sure that you exploit this information in your code by making use of getInitialDistribution(). Look at the StaticKeyboardAgent, which is actually playing the game: it delegates action choice to you, the human, and uses an ExactStaticInferenceModule to compute distributions over ghosts.
You will implement the function getGhostTupleDistributionGivenObservations() located in the ExactStaticInferenceModule class in staticInferenceModule.py.  It takes a dictionary of location / reading pair and should calculate the posterior distribution over the location of a ghost given those observations.  The returned object should be a dictionary which has all singleton tuples of all the grid locations as keys and posterior probabilities (that the ghost is in that position) as values.  You might try printing out the observations as you play to see what they look like.  Test your agent by playing with noiseless sensors (-s deterministic, which is the default): 

  python ghostbusters.py -s deterministic

You also might use -w to show the true ghost position for debugging:  

  python ghostbusters.py -w -s deterministic

Once your code seems to be working, try noisy sensor distributions (-s noisy): 

  python ghostbusters.py -w -s noisy

Note that thanks to your results from the homework, you can ignore all unobserved reading variables when you compute the posterior over G. That is, you can treat the network on the left as if it were the one on the right:

              
Hints:

Question 2 (3 points) You can put multiple ghosts on the board with the -k option.  Try a game with -k 2 -q:  

  python ghostbusters.py -w -q -k 2

You now need to make sure your inference works correctly for the case of multiple ghosts; it may already be correct, depending on how you coded your answer to question 1 (you will only turn in this more general version).  Whereas before G was essentially a ghost position, it is now a ghost tuple, and so we are calculating posteriors over ghost tuples.  For example, if we have 2 ghosts, we calculate the posterior probability of (ghost1, ghost2) being ((0,0), (0,0)), ((0,0), (0,1)), and so on.  Because the ghosts are interchangeable, you will never know which exact ghost is in which location, but you may know which k locations are occupied.  When there are multiple ghosts, the GUI will display the expected number of ghosts at each location.  We have provided a function in the mostly abstract StaticGhostbustersAgent class called getExpectedGhostCounts() which extracts expected counts from your posterior over G; make sure you understand this method.  In the single-ghost case, the expected ghosts counts are just the beliefs we compute in getGhostTupleDistributionGivenObservations().  In the k-ghost case, however, the expected number of ghosts across all locations will be k.  For example, you may have a posterior that ((0,0), (0,1)) is 0.5 and ((0,1), (0,0)) is 0.5, at which point both of (0,0) and (0,1) will have expected counts of 1.0.  Try your code with 2 and 3 ghosts. Make sure you understand why inference slows down as k increases:

  python ghostbusters.py -w -k 2

  python ghostbusters.py -w -k 3

Question 3 (5 points)

You will now write a new agent, which makes decisions using your inference code.  The simplest decision to make is where to bust given current beliefs over ghost locations G.  This computation is basically an expectimax computation, shown diagrammatically below.  At the root max node, you can select any busting option (tuple of k squares), and the expected utility (score) is the max over all actions' expected utilities.  Each action will produce an expected utility which is the expected number of ghosts in those squares times the score per ghost, GHOST_SCORE.

However, you need not bust right away.  Instead, you might sense first, revealing a single new reading, and then bust.  In this case, you would have various sensing actions available to you.  Each sensing action leads to a chance node with a distribution P(Ri,j | {r}), which describes the agent's beliefs about what reading will emerge at that location, given the previous readings.  For each such new reading, we will have an optimal busting option and the new accompanying expected utility.  Your agent should usually take the sensing action which reveals the reading which has the largest value of information, that is, expected gain in maximum expected utility.  However, once the value of the information is less that 1 point, it should stop sensing and bust.  In deciding its actions, your agent does not evaluate the futures in which it senses multiple times (though it may indeed end up sensing multiple times).  This decision process is therefore not optimal; the optimal agent would also explicitly consider the possibility of sensing more than once before busting.  In other words, you have an agent with look-ahead depth 2 for its action selection.

The search tree for this process is represented in the following diagram:

You should build an agent which not only computes posterior beliefs, but also makes decisions, using the at-most-one-sensor look-ahead described above.  You will need to implement StaticVPIAgent.getAction() in ghostbusterAgent.py and ExactStaticInferenceModule.getReadingDistributionGivenObservations() in staticInferenceModule.py .  You may wish to think first about the one-ghost case before generalizing to the multi-ghost case, but the code should be the same either way.  Test your VPI agent with (-p vpi): first using deterministic sensors (-s deterministic): 

  python ghostbusters.py -w -p vpi -s deterministic

and then with noisy sensors (-s noisy):  

  python ghostbusters.py -w -p vpi -s noisy

It should work very well (better than 90%) in the deterministic case, but might sometimes make obviously non-optimal decisions in the noisy case, because of the limited look-ahead. Make sure it works with multiple ghosts as well (NOTE: this will be a lot slower than the single ghost case): 

  python ghostbusters.py -w -p vpi -k 2

Hints: