Home

Homework 2

Table of Contents

Task 1 Preparation

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.txt and two folders: layouts and py.
  • 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.

Task 1 (20 pts)

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

Task 2 (80 pts)

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
                # ...

Task 3 (Extra credit, +25 pts)

Implement breadth-first search for pacman, in the breadthFirstSearch function. Test with:

  • python py/pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
Intro to AI material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.