Use Python to fill in the missing code. In search.py you will implement generic search algorithms which are called by pacman (in search.py).

Please use the template provided (in the comments of depth first search) to complete the code for the functions.

# search.py # --------- # Licensing Information: Please do not distribute or publish solutions to this # project. You are free to use and extend these projects for educational # purposes. The Pacman AI projects were developed at UC Berkeley, primarily by # John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu). # For more info, see

""" In search.py, you will implement generic search algorithms which are called by Pacman agents (in searchAgents.py). """

import util

class SearchProblem: """ This class outlines the structure of a search problem, but doesn't implement any of the methods (in object-oriented terminology: an abstract class).

You do not need to change anything in this class, ever. """

def getStartState(self): """ Returns the start state for the search problem """ util.raiseNotDefined()

def isGoalState(self, state): """ state: Search state

Returns True if and only if the state is a valid goal state """ util.raiseNotDefined()

def getSuccessors(self, state): """ state: Search state

For a given state, this should return a list of triples, (successor, action, stepCost), where 'successor' is a successor to the current state, 'action' is the action required to get there, and 'stepCost' is the incremental cost of expanding to that successor """ util.raiseNotDefined()

def getCostOfActions(self, actions): """ actions: A list of actions to take

This method returns the total cost of a particular sequence of actions. The sequence must be composed of legal moves """ util.raiseNotDefined()

def tinyMazeSearch(problem): """ Returns a sequence of moves that solves tinyMaze. For any other maze, the sequence of moves will be incorrect, so only use this for tinyMaze """ from game import Directions s = Directions.SOUTH w = Directions.WEST return [s,s,w,s,w,w,s,w]

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())) """ util.raiseNotDefined() # closedset = set() # 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 # # ... print("Start:", problem.getStartState())

""" YOUR CODE HERE """

def breadthFirstSearch(problem): """ YOUR CODE HERE """ util.raiseNotDefined()

def uniformCostSearch(problem): """ YOUR CODE HERE """ util.raiseNotDefined()

def nullHeuristic(state, problem=None): """ A heuristic function estimates the cost from the current state to the nearest goal in the provided SearchProblem. This heuristic is trivial. """ return 0

def aStarSearch(problem, heuristic=nullHeuristic): """ YOUR CODE HERE """ util.raiseNotDefined()

# Abbreviations bfs = breadthFirstSearch dfs = depthFirstSearch astar = aStarSearch ucs = uniformCostSearch