Logic and searching.
Unseen ghosts will soon be trapped.
Spock would be so proud.
In this project, your Pacman agent will use propositional logic to hunt ghosts it cannot see. You will first warm up building logic sentences and running them through a SAT solver (Questions 1 and 2). You will then build up, piece by piece, the knowledge base of a hybrid agent: an agent that combines logical inference (to prove which squares are safe) with search-based planning (to decide where to go next). By the end, your agent will explore a Wumpus World-inspired Pacman board, prove where the hidden ghosts are, and trap every one of them, eating food for points along the way, without ever stepping on a square it cannot prove safe.
Download: all the code and supporting files are in
logic_plan.zip. Download it, unzip it, and change into the
logic_plan directory.
Play the game: the best introduction to the assignment is to play a game of Wumpus-Pacman yourself, right now (move with 'w', 'a', 's', 'd' or the arrow keys; press 't' to toggle trapping mode, and 'v' to reveal the hidden ghosts and food):
python3.12 wumpus.py
The rules of the game are described in The Wumpus-Pacman World section below.
As in previous programming assignments, this assignment includes an autograder for you to grade your answers on your machine. This can be run with the command:
python3.12 autograder.py
See the autograder tutorial in Project 0 for more information about using the autograder.
The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore.
logicPlan.py |
Where your logic sentences, knowledge base, and safety inference will reside (Questions 1-5). |
hybridAgents.py |
Where your exploration and hybrid agents will reside (Questions 6-7). |
logic.py |
Propositional logic code originally from https://code.google.com/p/aima-python/ with modifications for our project. There are several useful utility functions for working with logic in here. |
wumpus.py |
The Wumpus-Pacman game itself: rules, percepts, traps, and the command-line interface. The
docstring at the top and the GameState.getPercept method are worth reading. |
searchUtil.py |
A* search over safe squares, used by the provided planning helpers in
hybridAgents.py. |
pycosat_test.py |
Quick test main function that checks that the pycosat module is installed correctly. |
game.py |
The logic behind how the Pacman world works. The only thing you might want to look at in here is the Grid class. |
test_cases/ |
Directory containing the test cases for each question |
logic_utils.py |
Utility functions for logic.py |
util.py |
Utility functions primarily for other projects. |
logic_planTestClasses.py |
Project specific autograding test classes |
wumpusDisplay.py |
Graphics for the Wumpus-Pacman game |
wumpusKeyboardAgents.py |
Keyboard interface to control Pacman in the Wumpus-Pacman game |
graphicsUtils.py |
Support for Pacman graphics |
textDisplay.py |
ASCII graphics for Pacman |
ghostAgents.py |
Agents to control ghosts |
layout.py |
Code for reading layout files and storing their contents |
autograder.py |
Project autograder |
testParser.py |
Parses autograder test and solution files |
testClasses.py |
General autograding test classes |
Files to Edit and Submit: You will fill in portions of logicPlan.py and
hybridAgents.py during the assignment. You should submit these files with your code and
comments. Please do not change the other files in this distribution or submit any of our original
files other than these 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. 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 projects 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.
We have compiled a list of frequently asked questions and common mistakes on various problems in this assignment. Please read this list carefully, and refer back to this before asking any questions on the discussion board.
PropSymbolExpr class carefully and make sure you know how to
construct symbols with indices like G[3,4]walls is a Grid
(see game.py): walls[x][y] is True if there is a wall at
(x, y)self.recordTrap before returning a trap action, or your knowledge base
will contradict itself laterIn the first part of this project, you will be working with the Expr class defined in
logic.py to build propositional logic sentences. An Expr object is implemented as
a tree with logical operators (\(\land, \lor, \neg, \Rightarrow, \Leftrightarrow\)) at each node and with
literals (\(A, B, C\)) at the leaves. The sentence
\[ (A \land B) \Leftrightarrow (\neg C \lor D) \]
would be represented as the tree

To instantiate a symbol named 'A', call the constructor like this:
A = Expr('A')
The Expr class allows you to use Python operators to build up these expressions. The following
are the available Python operators and their meanings:
~A: \(\neg A\)A & B: \(A \land B\)A | B: \(A \lor B\)A >> B: \(A \Rightarrow B\)A % B: \(A \Leftrightarrow B\)So to build the expression \(A \land B\), you would type this:
A = Expr('A')
B = Expr('B')
a_and_b = A & B
Note: A to the left of the assignment operator in that example is just a Python
variable name, i.e. symbol1 = Expr('A') would have worked just as well.)
Important: A & B & C will give the expression
((A & B) & C). If instead you want (A & B & C), as you will for
these problems, use logic.conjoin, which takes a list of expressions as input and returns one
expression that is the conjunction of all the inputs. The & operator in Python is a binary
operator and builds an unbalanced binary tree if you chain it several times, whereas conjoin
builds a tree that is one level deep with all the inputs extending directly from the &
operator at the root. logic.disjoin is similarly defined for |. The autograder for
Question 1 will require that you use logic.conjoin and logic.disjoin wherever you
could otherwise chain several & operators or several | operators. If you keep
with this convention for later problems, it will help with debugging because you will get more readable
expressions.
There is additional, more detailed documentation for the Expr class in logic.py.
Expr, it must start with an upper case character. You will get
non-obvious errors later if you don't follow this convention.
Expr instances. For example, if you intend to create the
expression x = Expr('A') & Expr('B'), you don't want to accidentally type
x = Expr('A & B'). The former will be a logical expression of the symbol 'A' and the
symbol 'B', while the latter will be a single symbol (Expr) named 'A & B'.
A SAT (satisfiability) solver takes a logic expression which encodes the rules of the world and returns a model (true and false assignments to logic symbols) that satisfies that expression if such a model exists. To efficiently find a possible model from an expression, we take advantage of the pycosat module, which is a Python wrapper around the picoSAT library.
Unfortunately, this requires installing this module/library on each machine.
To install this software in the Andrew Linux servers:
ssh -Y <andrewid>@unix.andrew.cmu.edu python3.12 -m pip install --user pycosat --upgrade setuptools There should be no errors.To install this software on your own machine (Mac and Unix), please follow these steps:
python3.12 -m pip install pycosat python3.12 -m pip install --user pycosat --upgrade setuptools To install this software on your own machine (Windows), please follow these steps:
python3.12 -m pip install pycosat Microsoft Visual C++ 14.0 or greater is required. error, visit this link and download MSVC v143 - VS 2022 C++ x64/x86 build tools (Latest) and Windows 10/11 SDK(depending on your system)Testing pycosat installation:
After unzipping the project code and changing to the project code directory, run:
python3.12 pycosat_test.py
This should output:
[1, -2, -3, -4, 5].
Please let us know if you have issues with this setup. This is critical to completing the project, and we don't want you to spend your time fighting with this installation process.
This question will give you practice working with logic. The logic.Expr data type used in the
project to represent propositional logic sentences.
Fill in the functions sentence1(), sentence2(), and sentence3() in
the file logicPlan.py, which ask you to create specific logic.Expr instances.
For sentence1(), create one logic.Expr instance that represents that the
following three sentences are true. Do not do any logical simplification, just put them in in this form in
this order.
\[ A \lor B \]
\[ \neg A \Leftrightarrow \neg B \lor C \]
\[ \neg A \lor \neg B \lor C \]
For sentence2(), create one logic.Expr instance that represents that the
following four sentences are true. Again, do not do any logical simplification, just put them in in this
form in this order.
\[ C \Leftrightarrow B \lor D \]
\[ A \Rightarrow \neg B \land \neg D \]
\[ \neg (B \land \neg C) \Rightarrow A \]
\[ \neg D \Rightarrow C \]
Later in the project, we will have symbols with names like \(G[3, 4]\), which represents that a ghost is
at position \((3, 4)\), and we will use them in logic expressions like the above in place of
\(A, B, C, D\). The logic.PropSymbolExpr constructor is a useful tool for creating symbols
like \(G[3, 4]\) that have numerical information encoded in their name (for this, you would type
PropSymbolExpr('G', 3, 4)).
Using the logic.PropSymbolExpr constructor,
create symbols WumpusAlive[0], WumpusAlive[1], WumpusBorn[0],
and WumpusKilled[0], and create one logic.Expr instance which encodes the
following three English sentences as propositional logic in this order without any simplification:
The Wumpus is alive at time 1 if and only if he was alive at time 0 and he was not killed at time 0 or he was not alive at time 0 and he was born at time 0.
At time 0, the Wumpus cannot both be alive and be born.
The Wumpus is born at time 0.
Are sentence1(), sentence2(), and
sentence3() satisfiable? If so, try to find a satisfying assignment. (This is not graded, but
is a good self-check to make sure you understand what's happening here.)
Before you continue, try instantiating a small sentence, e.g.
\(A \land B \implies C\) and call logic.to_cnf on it. Inspect the output and make sure you
understand it (refer to AIMA section 7.5.2 for details on the algorithm logic.to_cnf
implements).
Now, implement a small function
findModel(sentence), which uses logic.to_cnf to convert the input sentence into
Conjunctive Normal Form (the form required by the SAT solver), then passes it to the SAT solver using
logic.pycoSAT to find a satisfying assignment to the symbols in sentence, i.e., a
model. A model is a dictionary of the symbols in your expression and a corresponding assignment of True or
False. You can test your code on sentence1(), sentence2(), and
sentence3() by opening an interactive session in Python and running
findModel(sentence1()) and similar queries for the other two. Do they match what you
thought?
To test and debug your code run:
python3.12 autograder.py -q q1
You can also run one test at a time with the -t flag. Each question's tests live in the
test_cases directory, one .test file per test (with a matching
.solution file holding the expected result):
$ ls test_cases/q1 CONFIG correctSentence3.solution findModelSentence2.test correctSentence1.solution correctSentence3.test findModelSentence3.solution correctSentence1.test findModelSentence1.solution findModelSentence3.test correctSentence2.solution findModelSentence1.test correctSentence2.test findModelSentence2.solution
So, for example, to run only the first sentence test:
python3.12 autograder.py -t test_cases/q1/correctSentence1
(The trailing .test is optional: -t test_cases/q1/correctSentence1.test, as
tab-completion gives you, works too.)
Implement the following three logic expressions in logicPlan.py:
atLeastOne(literals): Return a single expression (Expr) in CNF that is true only if at
least one expression in the input list is true. Each input expression will be a literal.atMostOne(literals): Return a single expression (Expr) in CNF that is true only if at most
one expression in the input list is true. Each input expression will be a literal. There are multiple ways
to implement this function. If you find your algorithm timing out on later problems maybe it is helpful
to revisit the implementation of this function.exactlyOne(literals): Return a single expression (Expr) in CNF that is true only if exactly
one expression in the input list is true. Each input expression will be a literal.Each of these methods takes a list of logic.Expr literals and returns a single
logic.Expr expression that represents the appropriate logical relationship between the
expressions in the input list. An additional requirement is that the returned Expr must be in CNF
(conjunctive normal form). You may NOT use the logic.to_cnf function in your method
implementations (or any of the helper functions logic.eliminate_implications,
logic.move_not_inwards, and logic.distribute_and_over_or).
Important: When implementing your agents in the later questions, you will not have to
worry about CNF until right before sending your expression to the SAT solver (at which point you can use
findModel from question 1). logic.to_cnf implements the algorithm from section 7.5
in AIMA. However, on certain worst-case inputs, the direct implementation of this algorithm can result in
exponentially sized sentences. In fact, a certain non-CNF implementation of one of these three functions is
one such worst case. So if you find yourself needing the functionality of atLeastOne,
atMostOne, or exactlyOne for a later question, make sure to use the functions
you've already implemented here to avoid accidentally coming up with that non-CNF alternative and passing it
to logic.to_cnf.
You may utilize the logic.pl_true function to test the output of your expressions.
pl_true takes an expression and a model and returns True if and only if the expression is true
given the model.
To test and debug your code run:
python3.12 autograder.py -q q2
The rest of the project takes place in a Wumpus World-inspired variant of Pacman, implemented in
wumpus.py. Pacman hunts ghosts, but cannot see them, and stepping onto a square
occupied by a live ghost is fatal. Fortunately, Pacman carries two tools:
'TrapNorth',
'TrapSouth', 'TrapEast', and 'TrapWest' place a trap in the
corresponding adjacent square (Pacman does not move that turn). If a ghost is there, it is captured: it
stays on the board, greyed out, and is harmless from then on. If the square was empty, the trap is
wasted. By default Pacman has one trap per ghost.Ghosts never move. The game is won the moment every ghost has been trapped; the food is worth points along the way (on a board with no ghosts, eating all the food wins instead). The game is lost if Pacman steps onto a live ghost. Ghosts and food are hidden by default: visible food would give away which squares are ghost-free.
Play a game yourself to get a feel for the world, if you have not already (move with 'w', 'a', 's', 'd' or the arrow keys; press 't' to toggle trapping mode, and 'v' to reveal the ghosts and food):
python3.12 wumpus.py
By default, every game is played on a freshly generated random board hiding four ghosts, so no two
games are alike (-f replays the same board). Random boards come with no promises: most fall
to careful play, but on some only a lucky gamble wins. For a board that is always winnable
without guessing, play the fixed classic board with -l wumpusClassic: there, a careful
player can prove where every ghost is from PKE readings alone before ever risking a step, so if you die,
it was avoidable! For a gentler warm-up try -l wumpusTiny or -l wumpusHunt7
(also winnable without guessing), or use -l to try any layout in the layouts
directory.
Your agents will not get to see the game state. Instead, each turn they receive a percept, a Python dict with exactly four entries:
percept['pacman'] |
Pacman's current (x, y) position |
percept['pkeReading'] |
True if a live ghost is adjacent to Pacman right now |
percept['walls'] |
the walls Grid: walls[x][y] is True if (x, y)
is a wall |
percept['traps'] |
how many traps Pacman has left |
Note that with the way the grid is laid out, the leftmost, bottommost space occupiable by Pacman (assuming there isn't a wall there) is (1, 1), as shown below (not (0, 0)).

This is exactly the hybrid-agent setting of AIMA chapter 7.7, "Agents Based on Propositional Logic": the agent turns its percept history into a propositional knowledge base, asks a SAT solver what the knowledge base entails about the world, and then uses ordinary search to plan a route through squares it has proven safe. Questions 3-5 build the knowledge base and the inference; Questions 6-7 build the agents.
Since the ghosts never move, none of the symbols in this knowledge base need a time index. We will use
just two families of symbols: \(G[x, y]\), meaning there is a ghost at \((x, y)\), and \(PKE[x, y]\),
meaning the PKE meter reads True at \((x, y)\). In your code, always build these with the constants
defined at the top of logicPlan.py: PropSymbolExpr(ghost_str, x, y) and
PropSymbolExpr(pke_str, x, y).
A PKE reading on its own is just a bit. To make it mean something, the knowledge base needs the rule that connects the reading to ghosts: the meter reads True at a square exactly when a ghost is in one of the adjacent non-wall squares.
Implement pkeRule(position, walls) in logicPlan.py. Given a position
(x, y) and the walls Grid, it should return a single logic.Expr
encoding
\[ PKE[x, y] \Leftrightarrow \bigvee_{\text{non-wall neighbors } (n_x, n_y)} G[n_x, n_y] \]
For example, on a board where \((2, 1)\) has open squares to its East and West and walls to its North and
South, pkeRule((2, 1), walls) should return an expression equivalent to
\(PKE[2,1] \Leftrightarrow (G[1,1] \lor G[3,1])\).
Important: squares inside walls must not appear in the rule: a ghost can never be inside
a wall, and the autograder checks that your rule does not mention them. Use logic.disjoin for
the disjunction. You may assume the query square itself is not a wall and has at least one non-wall
neighbor.
To test and debug your code run:
python3.12 autograder.py -q q3
The test cases start with a dead-end square that has only a single open neighbor; if your rule is wrong, debug it there before worrying about the four-neighbor cases.
As Pacman walks around, he accumulates two kinds of knowledge: squares that are known to be ghost-free (every square he has safely stood on, for a start), and the PKE readings he has taken. Your job is to assemble all of it into one list of logic sentences.
Implement buildKnowledgeBase(pkeReadings, knownSafePositions, walls) in
logicPlan.py, where pkeReadings is a dict mapping positions to the boolean
reading observed there, and knownSafePositions is a set of positions known to hold no ghost.
Return a list of logic.Expr instances containing:
The order of the list does not matter. What does matter is that you assert nothing about squares Pacman knows nothing about: the autograder evaluates your knowledge base only over the symbols it is allowed to mention, and a knowledge base that asserts extra facts will fail.
To test and debug your code run:
python3.12 autograder.py -q q4
The first test has no readings at all (just two safe squares), so you can check the safe-position facts in isolation before adding the reading logic.
Now for the inference. Given everything Pacman knows, a square falls into exactly one of three categories, and your agent will need to distinguish all three:
SAFE: the knowledge base entails that there is no ghost there. Pacman may step
here.NOT_SAFE: the knowledge base entails that there is a ghost there. Pacman must
not step here, but a trap thrown here is guaranteed to catch a ghost.UNSURE: the knowledge base allows both possibilities. Entering is a gamble.Implement isSafe(position, pkeReadings, knownSafePositions, walls) in
logicPlan.py, returning one of the three constants SAFE, NOT_SAFE,
or UNSURE defined at the top of the file (do not return bare strings you typed yourself;
use the constants).
Remember from lecture how entailment reduces to satisfiability:
\[ KB \models \alpha \quad\text{if and only if}\quad KB \land \neg\alpha \text{ is unsatisfiable} \]
You already have all the pieces: buildKnowledgeBase gives you \(KB\) as a list,
logic.conjoin turns a list into one sentence, and findModel from Question 1
tells you whether a sentence is satisfiable. Two findModel calls are enough to distinguish
the three answers; work out on paper which two sentences to check before you code.
To test and debug your code run:
python3.12 autograder.py -q q5
The test cases build up from trivial to subtle, in order: a known-safe square, a square nothing is known about, a square cleared by a False reading, a ghost pinned down by a True reading in a corridor, a True reading with two possible culprits (provably neither can be called safe!), and finally a scenario where several readings combine to pin a ghost to one square. If a test fails, debug it before moving to the next one; each builds on the reasoning of the previous.
Hint: if you have SAFE and NOT_SAFE swapped, revisit the entailment formula above: to prove the square safe you must show that "there is a ghost here" is impossible, i.e. that \(KB \land G[x,y]\) has no model.
Time to put the inference to work. Implement getAction of the
SafeExplorationAgent class in hybridAgents.py: an agent that explores the board
while only ever standing on squares it has proven safe.
The class already sets up three pieces of state in __init__ for you to maintain:
self.pkeReadings (dict of readings taken), self.safePositions (set of squares
proven safe), and self.visited (set of squares Pacman has stood on). Each turn, your
getAction(percept) should:
self.pkeReadings.findAllSafeStatus(pkeReadings,
knownSafePositions, walls), and add every square it proves SAFE to
self.safePositions.planToNearest(currentPosition, goalPositions, allowedPositions, walls).None to give up if there is nothing safe left
to explore (the game ends in a loss, but a dignified one).Note that the agent replans from scratch every turn. That is fine: each new percept can change what is provably safe, so yesterday's route may be obsolete anyway.
Because this agent never uses traps, it can only win on boards with no ghosts: eating all the food wins
the game when there are no ghosts to trap. That is exactly what the autograder tests it on. Start with the
easiest test, a three-square ghost-free corridor. When run with -q or -t, the
autograder shows each game graphically so you can watch your agent work (add --no-graphics to
turn that off):
python3.12 autograder.py -t test_cases/q6/exploration1_corridor
Each of these tests is a small text file that contains its own custom layout, so you can always see exactly what board a test plays on:
$ cat test_cases/q6/exploration1_corridor.test class: "WumpusGameTest" # A ghost-free corridor: walk East, eating the food. agent: "SafeExplorationAgent" layoutName: "safeCorridor" layout: """ %%%%% %P..% %%%%% """
You can also watch your agent roam the larger boards from the layouts directory
(start simple!):
python3.12 wumpus.py -p SafeExplorationAgent -l wumpusSafe1
python3.12 wumpus.py -p SafeExplorationAgent -l wumpusSafe2
python3.12 wumpus.py -p SafeExplorationAgent -l wumpusSafe3
For fun, watch it on a board that does have a ghost: it explores everything it can prove safe, then gives up rather than gamble:
python3.12 wumpus.py -p SafeExplorationAgent -l wumpusMaybeSafe
To test and debug your code run:
python3.12 autograder.py -q q6
Debugging hints:
self.safePositions before planning.The exploration agent stops the moment nothing more can be proven safe. The full hybrid agent keeps going: it uses its traps to make squares safe, and when all else fails, takes a calculated gamble.
Implement getAction of the HybridAgent class in hybridAgents.py.
Start each turn exactly like the exploration agent (record the percept, update the knowledge base, and
classify every square), then choose an action by working down this strategy list, using the first tier
that produces a plan:
SAFE square, travelling only
through safe squares. (This is Question 6's behavior.)NOT_SAFE, plan a
route to the nearest such square (travelling through safe squares, with the ghost square itself as the
final step) and replace the final action of the plan with its Trap variant (e.g.
'East' becomes 'TrapEast'). A trap thrown at a proven ghost is never
wasted.UNSURE square the same way; if a
trap is available, replace the final action with its Trap variant, so the square is trapped just before
Pacman would step in. Sometimes the board leaves no certainty to work with, and a hybrid agent has to
accept that.Return the first action of the chosen plan, or None to give up if no tier produces one.
Since the agent replans every turn, only the first action is ever executed; the trap-substitution on the
final step matters on the turn the agent is standing right next to its target.
One subtlety is handled for you. When a trap fires, the target square becomes safe no
matter what was there, but any earlier True PKE reading next to that square may have been
caused by the ghost that was just captured, so those readings are now stale, and keeping them would make
the knowledge base contradict itself. The provided recordTrap method handles both updates.
Your only obligation: whenever the action you are about to return is a trap action, call
self.recordTrap(currentPosition, action) first. (Read recordTrap; it is short,
and understanding why stale readings must be forgotten is the best logic exercise in this
project.)
Start with the easiest autograder test: one ghost in a corridor, where the PKE readings pin it down
exactly (as in Question 6, -q and -t show the games graphically, and the test
file contains the board):
python3.12 autograder.py -t test_cases/q7/hybrid1_corridorGhost
Then watch your agent hunt on the larger boards, again starting simple:
python3.12 wumpus.py -p HybridAgent -l wumpusTiny
python3.12 wumpus.py -p HybridAgent -l wumpusMaybeSafe
python3.12 wumpus.py -p HybridAgent -l wumpus1
python3.12 wumpus.py -p HybridAgent -l wumpus3
python3.12 wumpus.py -p HybridAgent -l wumpusHunt7
(Press 'v' during a game to reveal the ghosts and food and see how the agent's deductions line up with reality.)
To test and debug your code run:
python3.12 autograder.py -q q7
Debugging hints:
percept['traps'] > 0.
Complete Questions 1 through 7 as specified in the project instructions. Then upload
logicPlan.py and hybridAgents.py to Gradescope.
Prior to submitting, be sure you run the autograder on your own machine. Running the autograder locally will help you to debug and expediate your development process. The autograder can be invoked on your own machine using the command:
python3.12 autograder.py
To run the autograder on a single question, such as question 3, invoke it by
python3.12 autograder.py -q q3
Note that running the autograder locally will not register your grades with us. Remember to submit your code when you want to register your grades for this assignment.
The autograder on Gradescope might take a while but don't worry: so long as you submit before the due date, it's not late.