Hunt the Wumpus is a classic text-based hide and seek game, originally written in BASIC (yes, BASIC) in the early 1970s. Subsequent versions introduced many variations on the original theme, but in each adaptation the player assumes the role of an Agent who moves throughout a maze in the hunt for a deadly Wumpus.
Little is known about the elusive Wumpus, as all those who stumble upon it are immediately eaten. There does, however, seem to be a fairly universal consensus that it has suckers, which allow it to navigate the deadly Pits scattered throughout its labyrinthine home. The only hope the Agent has of killing the Wumpus without being eaten is to fire an arrow at it from afar, taking the Wumpus by surprise.
The Wumpus world is composed of R rooms, with W Wumpii, P Pits, and B Bats scattered uniformly at random throughout the rooms. A Wumpus, a Pit, and a Bat can all coexist in the same room, but two hazards of the same type cannot be in the same room at once.
Each room has C portals on average, but may have as many as 8 or as few as 1. The only guarantee is that the rooms and portals form a connected graph. Be careful: the magic portals connecting rooms don't necessarily respect the normal concept of adjacency; a portal on the North side of one room may connect to the West side of a room at the other end of the cave!
The Agent begins in a random room, which is guaranteed not to contain any hazards. At the start of the game, the Agent has A arrows.
On entering a room containing a Wumpus or a Pit, the Agent is immediately killed. On entering a room containing a Bat, there is a probability M that the Bat carries the Agent to another room (including the original room) uniformly at random. If the Agent is carried to a room containing a Wumpus or a Pit, the Agent is killed as usual. Otherwise, if the Agent is carried to a room containing another Bat, that Bat carries the agent to another random room with probability 1. This repeats until the Agent is either killed or carried to a currently safe room.
In rooms adjacent to or containing a Pit, the Agent perceives a Breeze with probability 1. In rooms containing (but not adjacent to) a Bat, the Agent perceives Chittering with probability 1.
In rooms adjacent to or containing a Wumpus, the agent perceives a Stench with probability S1 if there is no Breeze and probability S2 if there is a Breeze. In rooms not containing or adjacent to a Wumpus, the Agent perceives a Stench with probability S3 if there is no Breeze, and probability S4 if there is a Breeze. The locations of stenches are fixed at the beginning of the game, so re-entering a room or killing a Wumpus won't change the Stench of a room.
During each turn, the Agent has the option of either moving or shooting in any direction. Moving or shooting in a direction where there is no portal causes the Agent to perceive a Bump. Moving in a valid direction sends the Agent through the appropriate portal to another room. An arrow fired through a portal will move into the adjacent room, striking any Wumpus or Agent in its path.
Striking a Wumpus with an arrow kills it, and causes the Agent to perceive a Scream. Striking the Agent with an arrow kills them, and ends the game. If the Agent runs out of arrows without killing every Wumpus in the maze, the remaining Wumpii attack and eat the now helpless Agent. The only way for the Agent to win is to kill every Wumpus in the maze before running out of arrows or being killed by a hazard.
The stencil code is in /course/cs141/pub/src/wumpus. Try playing a round of the game yourself with the command python wumpus.py (this begins a game using the default settings, using the HumanAgent solver which asks for instructions via the command line).
To play the game, simply enter an action ("M" to move or "S" to fire an arrow) and a direction (one of the 8 compass directions, e.g. "N" or "SW"), separated by a space. The HumanAgent will let you know what room you're in, which room it connects to in each direction, and any sensory information you detect in the current room.
In this default version of the game, the maze has 20 rooms (R=20), 1 Wumpus (W=1), and 3 Pits (P=3, B=0). The Agent begins with 1 arrow (A=1). The Stench probabilities are deterministic and noiseless by default, with S1=S2=1 and S3=S4=0, meaning that the Agent perceives a Stench if and only if the current room contains or is adjacent to a Wumpus. Although there are no Bats by default, the default setting for M (the probability that a Bat will move the Agent) is 0.5. The default Agent implementation is HumanAgent.
In general, the command to run the game is python wumpus.py [<agent>] [<flag> <value>]*, where <agent> is the name of an Agent class (e.g. "Human"), and <flag> is a hyphen followed by a variable as named in the Gameplay section (e.g. "-W" for the number of Wumpii or "-S2" for the probability of perceiving a real stench in the presence of a breeze).
In addition, you can use the "-T" flag to specify a test file, from which the game will load seed data if the file exists and into which the game will write seed data if it doesn't. This will hopefully make testing much simpler, as you can isolate any bugs that occur in your code by repeatedly running with the same pseudorandom numbers. A test file contains two random number generator seeds. One is for internal use by the game, to generate the maze and to determine when bats move. The other is used to seed the random number generator passed to your Agent at each round. If your code uses randomness to decide on an action, we highly recommend that you use this provided RNG in order to allow for consistency in testing.
Finally, you can use the "-V" flag to specify verbose output (this is only on by default when using HumanAgent), and the "-Y" flag to set a delay in milliseconds, to watch your Agent in action.
Your primary task for this project will be to write code that infers the probability of various hazards. A very small percentage of your total grade will be based on an Agent you build yourself, which should go beyond the naive Agents we provide in trying to maximize the overall probability of winning the game. Every class you will need to modify is located in wumpus_agents.py
Every method you are responsible for filling in includes as one of its parameters a KnownWorld object, which encodes what you've learned so far about the Wumpus world. The KnownWorld can be queried for things like the rooms you've visited and their contents, the neighbors of a room, and game parameters like Stench probabilities and the number of Pits. The complete specification for this class is in wumpus_world.py. You should familiarize yourself with this class, as the information it provides will be crucial for making inferences about the world.
In order to successfully navigate the Wumpus world, an Agent absolutely must be able to infer the probability that a room contains a certain hazard. The RationalAgent class provides this capability. Any Agent implementation which works by formally reasoning about the probability of encountering a hazard extends this class (a HumanAgent is, of course, not a RationalAgent).
You are responsible for filling in the following methods in the RationalAgent class. You will probably want to do them in this order:
This is a HumanAgent augmented with the power of rationality! It still leaves its actions up to a human, but it prints out the probability of each hazard before asking what to do. Use this class to test out your RationalAgent inference methods, and to show those Wumpii who's boss!
This Agent extends RationalAgent. It first makes all moves which are known to be safe, then chooses the move with the lowest probability of encountering a hazard. The Agent will fire an arrow only if it will strike a Wumpus with probability at least 1-S3 (one minus the probability of perceiving a false stench).
You are responsible for filling in the following method in the NaiveSafeAgent class:
This Agent behaves like NaiveSafeAgent, except that it makes the move with the smallest probability of death, as opposed to the smallest probability of encountering a hazard. This means that being dropped by a Bat in a safe room is acceptable, whereas in NaiveSafeAgent simply encountering a bat is to be avoided.
For up to 5 points of extra credit, you may fill in the following method in the BatSafeAgent class:
To give you a chance to play around in the Wumpus world, you'll also be implementing your own CleverAgent, which should perform somewhat better than BatSafeAgent. The skeleton of this class is located in wumpus_agents.py. As inference is the primary focus of this project, the performance of your CleverAgent is only weighted at 15 points, as described in the Grading section.
You are responsible for filling in the following method in the CleverAgent class:
RationalAgent provides a number of useful utility methods for implementing your CleverAgent:
In addition, the KnownWorld class can serve as a Python dictionary, allowing you to cache and retrieve arbitrary data using the normal dictionary syntax known_world[key].
You'll be graded on two things in this assignment.
Each case below is worth 5 points. We'll be running each case 100 times, with the same seeds for the whole class, and basing your score on your CleverAgent's average performance.
We'll allow up to 30 minutes in total to run all three 100-run test cases while grading. If you find your code is running too slowly, try caching frequently-computed information in the known_world dictionary. In addition, make sure not to query for danger probabilities unless absolutely necessary, as this is an expensive operation. Instead, take a hint from the NaiveSafeAgent and decide on a destination and a path, then move there without making additional queries.
Please note that one thing you absolutely must not do to improve your CleverAgent's performance is to make your RationalAgent inference methods less exact. If you want to speed up your CleverAgent by writing separate approximate versions of these methods that's okay, but don't approximate in RationalAgent or you'll lose points for accuracy.
When testing your code, we will be running every submission using the same 100 seeds for each test case, and we guarantee that these seeds will elicit as good or better performance than above from our NaiveSafeAgent implementation. In other words, don't worry about us randomly testing the whole class on a set of impossible mazes, or about testing one person with a good set but another with a bad set.
The command is cs141_handin wumpus. You only need to turn in wumpus_agents.py along with a readme declaring anything we should know such as requiring python2.7.