UCB伯克利经典人工智能project-Pacman吃豆人-code，测试满分&有bonus

# searchAgents.py # --------------- # Licensing Information: You are free to use or extend these projects for # educational purposes provided that (1) you do not distribute or publish # solutions, (2) you retain this notice, and (3) you provide clear # attribution to UC Berkeley, including a link to http://ai.berkeley.edu. # # Attribution Information: The Pacman AI projects were developed at UC Berkeley. # The core projects and autograders were primarily created by John DeNero # (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel (pabbeel@cs.berkeley.edu). """ This file contains all of the agents that can be selected to control Pacman. To select an agent, use the '-p' option when running pacman.py. Arguments can be passed to your agent using '-a'. For example, to load a SearchAgent that uses depth first search (dfs), run the following command: > python pacman.py -p SearchAgent -a fn=depthFirstSearch Commands to invoke other search strategies can be found in the project description. Please only change the parts of the file you are asked to. Look for the lines that say "*** YOUR CODE HERE ***" The parts you fill in start about 3/4 of the way down. Follow the project description for details. Good luck and happy searching! """ from game import Directions from game import Agent from game import Actions from util import manhattanDistance from search import breadthFirstSearch import time import search class GoWestAgent(Agent): "An agent that goes West until it can't." def getAction(self, state): "The agent receives a GameState (defined in pacman.py)." if Directions.WEST in state.getLegalPacmanActions(): return Directions.WEST else: return Directions.STOP ####################################################### # This portion is written for you, but will only work # # after you fill in parts of search.py # ####################################################### class SearchAgent(Agent): """ This very general search agent finds a path using a supplied search algorithm for a supplied search problem, then returns actions to follow that path. As a default, this agent runs DFS on a PositionSearchProblem to find location (1,1) Options for fn include: depthFirstSearch or dfs breadthFirstSearch or bfs Note: You should NOT change any code in SearchAgent """ def __init__(self, fn='depthFirstSearch', prob='PositionSearchProblem', heuristic='nullHeuristic'): # Warning: some advanced Python magic is employed below to find the right functions and problems # Get the search function from the name and heuristic if fn not in dir(search): raise AttributeError(fn + ' is not a search function in search.py.') func = getattr(search, fn) if 'heuristic' not in func.__code__.co_varnames: print('[SearchAgent] using function ' + fn) self.searchFunction = func else: if heuristic in globals().keys(): heur = globals()[heuristic] elif heuristic in dir(search): heur = getattr(search, heuristic) else: raise AttributeError(heuristic + ' is not a function in searchAgents.py or search.py.') print('[SearchAgent] using function %s and heuristic %s' % (fn, heuristic)) # Note: this bit of Python trickery combines the search algorithm and the heuristic self.searchFunction = lambda x: func(x, heuristic=heur) # Get the search problem type from the name if prob not in globals().keys() or not prob.endswith('Problem'): raise AttributeError(prob + ' is not a search problem type in SearchAgents.py.') self.searchType = globals()[prob] print('[SearchAgent] using problem type ' + prob) def registerInitialState(self, state): """ This is the first time that the agent sees the layout of the game board. Here, we choose a path to the goal. In this phase, the agent should compute the path to the goal and store it in a local variable. All of the work is done in this method! state: a GameState object (pacman.py) """ if self.searchFunction == None: raise Exception("No search function provided for SearchAgent") starttime = time.time() problem = self.searchType(state) # Makes a new search problem self.actions = self.searchFunction(problem) # Find a path totalCost = problem.getCostOfActions(self.actions) print('Path found with total cost of %d in %.1f seconds' % (totalCost, time.time() - starttime)) if '_expanded' in dir(problem): print('Search nodes expanded: %d' % problem._expanded) def getAction(self, state): """ Returns the next action in the path chosen earlier (in registerInitialState). Return Directions.STOP if there is no further action to take. state: a GameState object (pacman.py) """ if 'actionIndex' not in dir(self): self.actionIndex = 0 i = self.actionIndex self.actionIndex += 1 if i < len(self.actions): return self.actions[i] else: return Directions.STOP class PositionSearchProblem(search.SearchProblem): """ A search problem defines the state space, start state, goal test, successor function and cost function. This search problem can be used to find paths to a particular point on the pacman board. The state space consists of (x,y) positions in a pacman game. Note: this search problem is fully specified; you should NOT change it. """ def __init__(self, gameState, costFn=lambda x: 1, goal=(1, 1), start=None, warn=True, visualize=True): """ Stores the start and goal. gameState: A GameState object (pacman.py) costFn: A function from a search state (tuple) to a non-negative number goal: A position in the gameState """ self.walls = gameState.getWalls() self.startState = gameState.getPacmanPosition() if start != None: self.startState = start self.goal = goal self.costFn = costFn self.visualize = visualize if warn and (gameState.getNumFood() != 1 or not gameState.hasFood(*goal)): print 'Warning: this does not look like a regular search maze' # For display purposes self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE def getStartState(self): return self.startState def isGoalState(self, state): isGoal = state == self.goal # For display purposes only if isGoal and self.visualize: self._visitedlist.append(state) import __main__ if '_display' in dir(__main__): if 'drawExpandedCells' in dir(__main__._display): # @UndefinedVariable __main__._display.drawExpandedCells(self._visitedlist) # @UndefinedVariable return isGoal def getSuccessors(self, state): """ Returns successor states, the actions they require, and a cost of 1. As noted in search.py: 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 """ successors = [] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: