Download this ZIP file with the Pacman source code: pacman.zip. This code, and the idea for the assignment, comes from UC Berkeley.
- Unzip the code.
- Open up the Windows Command Line or Mac Terminal or Linux Terminal.
- Change your directory to the folder with the pacman code. You should
see a file called
commands.txtand two folders:layoutsandpy. - Run some of these commands (as listed in
commands.txt) to make sure your setup works.python py/pacman.py(use your arrow keys to control pacman)python py/pacman.py --layout tinyMaze --pacman GoWestAgent- etc.
I want to make sure you can execute pacman. Tell me (in one sentence) what happens when you run this command:
python py/pacman.py --layout tinyMaze --pacman GoWestAgent
Tell me the last message printed on your console window when you run this command:
python py/pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
Open the file py/search.py and find the function depthFirstSearch
(line 70) which reads:
def depthFirstSearch(problem):
"""
Search the deepest nodes in the search tree first [p 85].
Your search algorithm needs to return a list of actions that reaches
the goal. Make sure to implement a graph search algorithm [Fig. 3.7].
To get started, you might want to try some of these simple commands to
understand the search problem that is being passed in:
print "Start:", problem.getStartState()
print "Is the start a goal?", problem.isGoalState(problem.getStartState())
print "Start's successors:", problem.getSuccessors(problem.getStartState())
"""
"*** YOUR CODE HERE ***"
util.raiseNotDefined()Take this template and finish the code so that depth-first search works. You can test it with pacman by running this command:
python py/pacman.py -l mediumMaze -p SearchAgent -a fn=dfs
Note that the comments above the code will be helpful. Submit just
this file (search.py) to the Dropbox, along with a text file with
your answers to Task 1.
def depthFirstSearch(problem):
"""
Search the deepest nodes in the search tree first [p 85].
Your search algorithm needs to return a list of actions that reaches
the goal. Make sure to implement a graph search algorithm [Fig. 3.7].
To get started, you might want to try some of these simple commands to
understand the search problem that is being passed in:
print "Start:", problem.getStartState()
print "Is the start a goal?", problem.isGoalState(problem.getStartState())
print "Start's successors:", problem.getSuccessors(problem.getStartState())
"""
closedset = []
openset = [problem.getStartState()] # openset starts with starting state
parents = {}
while len(openset) > 0:
state = openset.pop() # get most-recently-added element from openset
# ...
if # ...
print "Found goal!"
# retrieve series of steps that brought us here (use the parents map)
actions = []
while state != problem.getStartState():
# ...
print actions # just to see the resulting actions
return actions
else:
for (next_state, action, cost) in problem.getSuccessors(state):
# next_state is something like (4, 2) (coordinates)
# action is something like WEST
# cost is not used for depth-first search
# ...Implement breadth-first search for pacman, in the breadthFirstSearch
function. Test with:
python py/pacman.py -l mediumMaze -p SearchAgent -a fn=bfs