Introduction to Artificial Intelligence (Computer Science ,Python)
LLLLEE
homework_1_search.ziphomework_1_search/autograder.py
# autograder.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). # imports from python standard library import grading import imp import optparse import os import re import sys import projectParams import random random.seed(0) try: from pacman import GameState except: pass # register arguments and set default values def readCommand(argv): parser = optparse.OptionParser(description = 'Run public tests on student code') parser.set_defaults(generateSolutions=False, edxOutput=False, gsOutput=False, muteOutput=False, printTestCase=False, noGraphics=False) parser.add_option('--test-directory', dest = 'testRoot', default = 'test_cases', help = 'Root test directory which contains subdirectories corresponding to each question') parser.add_option('--student-code', dest = 'studentCode', default = projectParams.STUDENT_CODE_DEFAULT, help = 'comma separated list of student code files') parser.add_option('--code-directory', dest = 'codeRoot', default = "", help = 'Root directory containing the student and testClass code') parser.add_option('--test-case-code', dest = 'testCaseCode', default = projectParams.PROJECT_TEST_CLASSES, help = 'class containing testClass classes for this project') parser.add_option('--generate-solutions', dest = 'generateSolutions', action = 'store_true', help = 'Write solutions generated to .solution file') parser.add_option('--edx-output', dest = 'edxOutput', action = 'store_true', help = 'Generate edX output files') parser.add_option('--gradescope-output', dest = 'gsOutput', action = 'store_true', help = 'Generate GradeScope output files') parser.add_option('--mute', dest = 'muteOutput', action = 'store_true', help = 'Mute output from executing tests') parser.add_option('--print-tests', '-p', dest = 'printTestCase', action = 'store_true', help = 'Print each test case before running them.') parser.add_option('--test', '-t', dest = 'runTest', default = None, help = 'Run one particular test. Relative to test root.') parser.add_option('--question', '-q', dest = 'gradeQuestion', default = None, help = 'Grade one particular question.') parser.add_option('--no-graphics', dest = 'noGraphics', action = 'store_true', help = 'No graphics display for pacman games.') (options, args) = parser.parse_args(argv) return options # confirm we should author solution files def confirmGenerate(): print('WARNING: this action will overwrite any solution files.') print('Are you sure you want to proceed? (yes/no)') while True: ans = sys.stdin.readline().strip() if ans == 'yes': break elif ans == 'no': sys.exit(0) else: print('please answer either "yes" or "no"') # TODO: Fix this so that it tracebacks work correctly # Looking at source of the traceback module, presuming it works # the same as the intepreters, it uses co_filename. This is, # however, a readonly attribute. def setModuleName(module, filename): functionType = type(confirmGenerate) classType = type(optparse.Option) for i in dir(module): o = getattr(module, i) if hasattr(o, '__file__'): continue if type(o) == functionType: setattr(o, '__file__', filename) elif type(o) == classType: setattr(o, '__file__', filename) # TODO: assign member __file__'s? #print(i, type(o)) #from cStringIO import StringIO def loadModuleString(moduleSource): # Below broken, imp doesn't believe its being passed a file: # ValueError: load_module arg#2 should be a file or None # #f = StringIO(moduleCodeDict[k]) #tmp = imp.load_module(k, f, k, (".py", "r", imp.PY_SOURCE)) tmp = imp.new_module(k) exec(moduleCodeDict[k] in tmp.__dict__) setModuleName(tmp, k) return tmp import py_compile def loadModuleFile(moduleName, filePath): with open(filePath, 'r') as f: return imp.load_module(moduleName, f, "%s.py" % moduleName, (".py", "r", imp.PY_SOURCE)) def readFile(path, root=""): "Read file from disk at specified path and return as string" with open(os.path.join(root, path), 'r') as handle: return handle.read() ####################################################################### # Error Hint Map ####################################################################### # TODO: use these ERROR_HINT_MAP = { 'q1': { "<type 'exceptions.IndexError'>": """ We noticed that your project threw an IndexError on q1. While many things may cause this, it may have been from assuming a certain number of successors from a state space or assuming a certain number of actions available from a given state. Try making your code more general (no hardcoded indices) and submit again! """ }, 'q3': { "<type 'exceptions.AttributeError'>": """ We noticed that your project threw an AttributeError on q3. While many things may cause this, it may have been from assuming a certain size or structure to the state space. For example, if you have a line of code assuming that the state is (x, y) and we run your code on a state space with (x, y, z), this error could be thrown. Try making your code more general and submit again! """ } } import pprint def splitStrings(d): d2 = dict(d) for k in d: if k[0:2] == "__": del d2[k] continue if d2[k].find("\n") >= 0: d2[k] = d2[k].split("\n") return d2 def printTest(testDict, solutionDict): pp = pprint.PrettyPrinter(indent=4) print("Test case:") for line in testDict["__raw_lines__"]: print(" |", line) print("Solution:") for line in solutionDict["__raw_lines__"]: print(" |", line) def runTest(testName, moduleDict, printTestCase=False, display=None): import testParser import testClasses for module in moduleDict: setattr(sys.modules[__name__], module, moduleDict[module]) testDict = testParser.TestParser(testName + ".test").parse() solutionDict = testParser.TestParser(testName + ".solution").parse() test_out_file = os.path.join('%s.test_output' % testName) testDict['test_out_file'] = test_out_file testClass = getattr(projectTestClasses, testDict['class']) questionClass = getattr(testClasses, 'Question') question = questionClass({'max_points': 0}, display) testCase = testClass(question, testDict) if printTestCase: printTest(testDict, solutionDict) # This is a fragile hack to create a stub grades object grades = grading.Grades(projectParams.PROJECT_NAME, [(None,0)]) testCase.execute(grades, moduleDict, solutionDict) # returns all the tests you need to run in order to run question def getDepends(testParser, testRoot, question): allDeps = [question] questionDict = testParser.TestParser(os.path.join(testRoot, question, 'CONFIG')).parse() if 'depends' in questionDict: depends = questionDict['depends'].split() for d in depends: # run dependencies first allDeps = getDepends(testParser, testRoot, d) + allDeps return allDeps # get list of questions to grade def getTestSubdirs(testParser, testRoot, questionToGrade): problemDict = testParser.TestParser(os.path.join(testRoot, 'CONFIG')).parse() if questionToGrade != None: questions = getDepends(testParser, testRoot, questionToGrade) if len(questions) > 1: print('Note: due to dependencies, the following tests will be run: %s' % ' '.join(questions)) return questions if 'order' in problemDict: return problemDict['order'].split() return sorted(os.listdir(testRoot)) # evaluate student code def evaluate(generateSolutions, testRoot, moduleDict, exceptionMap=ERROR_HINT_MAP, edxOutput=False, muteOutput=False, gsOutput=False, printTestCase=False, questionToGrade=None, display=None): # imports of testbench code. note that the testClasses import must follow # the import of student code due to dependencies import testParser import testClasses for module in moduleDict: setattr(sys.modules[__name__], module, moduleDict[module]) questions = [] questionDicts = {} test_subdirs = getTestSubdirs(testParser, testRoot, questionToGrade) for q in test_subdirs: subdir_path = os.path.join(testRoot, q) if not os.path.isdir(subdir_path) or q[0] == '.': continue # create a question object questionDict = testParser.TestParser(os.path.join(subdir_path, 'CONFIG')).parse() questionClass = getattr(testClasses, questionDict['class']) question = questionClass(questionDict, display) questionDicts[q] = questionDict # load test cases into question tests = filter(lambda t: re.match('[^#~.].*\.test\Z', t), os.listdir(subdir_path)) tests = map(lambda t: re.match('(.*)\.test\Z', t).group(1), tests) for t in sorted(tests): test_file = os.path.join(subdir_path, '%s.test' % t) solution_file = os.path.join(subdir_path, '%s.solution' % t) test_out_file = os.path.join(subdir_path, '%s.test_output' % t) testDict = testParser.TestParser(test_file).parse() if testDict.get("disabled", "false").lower() == "true": continue testDict['test_out_file'] = test_out_file testClass = getattr(projectTestClasses, testDict['class']) testCase = testClass(question, testDict) def makefun(testCase, solution_file): if generateSolutions: # write solution file to disk return lambda grades: testCase.writeSolution(moduleDict, solution_file) else: # read in solution dictionary and pass as an argument testDict = testParser.TestParser(test_file).parse() solutionDict = testParser.TestParser(solution_file).parse() if printTestCase: return lambda grades: printTest(testDict, solutionDict) or testCase.execute(grades, moduleDict, solutionDict) else: return lambda grades: testCase.execute(grades, moduleDict, solutionDict) question.addTestCase(testCase, makefun(testCase, solution_file)) # Note extra function is necessary for scoping reasons def makefun(question): return lambda grades: question.execute(grades) setattr(sys.modules[__name__], q, makefun(question)) questions.append((q, question.getMaxPoints())) grades = grading.Grades(projectParams.PROJECT_NAME, questions, gsOutput=gsOutput, edxOutput=edxOutput, muteOutput=muteOutput) if questionToGrade == None: for q in questionDicts: for prereq in questionDicts[q].get('depends', '').split(): grades.addPrereq(q, prereq) grades.grade(sys.modules[__name__], bonusPic = projectParams.BONUS_PIC) return grades.points def getDisplay(graphicsByDefault, options=None): graphics = graphicsByDefault if options is not None and options.noGraphics: graphics = False if graphics: try: import graphicsDisplay return graphicsDisplay.PacmanGraphics(1, frameTime=.05) except ImportError: pass import textDisplay return textDisplay.NullGraphics() if __name__ == '__main__': options = readCommand(sys.argv) if options.generateSolutions: confirmGenerate() codePaths = options.studentCode.split(',') # moduleCodeDict = {} # for cp in codePaths: # moduleName = re.match('.*?([^/]*)\.py', cp).group(1) # moduleCodeDict[moduleName] = readFile(cp, root=options.codeRoot) # moduleCodeDict['projectTestClasses'] = readFile(options.testCaseCode, root=options.codeRoot) # moduleDict = loadModuleDict(moduleCodeDict) moduleDict = {} for cp in codePaths: moduleName = re.match('.*?([^/]*)\.py', cp).group(1) moduleDict[moduleName] = loadModuleFile(moduleName, os.path.join(options.codeRoot, cp)) moduleName = re.match('.*?([^/]*)\.py', options.testCaseCode).group(1) moduleDict['projectTestClasses'] = loadModuleFile(moduleName, os.path.join(options.codeRoot, options.testCaseCode)) if options.runTest != None: runTest(options.runTest, moduleDict, printTestCase=options.printTestCase, display=getDisplay(True, options)) else: evaluate(options.generateSolutions, options.testRoot, moduleDict, gsOutput=options.gsOutput, edxOutput=options.edxOutput, muteOutput=options.muteOutput, printTestCase=options.printTestCase, questionToGrade=options.gradeQuestion, display=getDisplay(options.gradeQuestion!=None, options))
homework_1_search/commands.txt
python pacman.py python pacman.py --layout testMaze --pacman GoWestAgent python pacman.py --layout tinyMaze --pacman GoWestAgent python pacman.py -h python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch python pacman.py -l tinyMaze -p SearchAgent python pacman.py -l mediumMaze -p SearchAgent python pacman.py -l bigMaze -z .5 -p SearchAgent python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5 python eightpuzzle.py python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs python pacman.py -l mediumDottedMaze -p StayEastSearchAgent python pacman.py -l mediumScaryMaze -p StayWestSearchAgent python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5 python pacman.py -l testSearch -p AStarFoodSearchAgent python pacman.py -l trickySearch -p AStarFoodSearchAgent python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5
homework_1_search/eightpuzzle.py
# eightpuzzle.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). import search import random # Module Classes class EightPuzzleState: """ The Eight Puzzle is described in the course textbook on page 64. This class defines the mechanics of the puzzle itself. The task of recasting this puzzle as a search problem is left to the EightPuzzleSearchProblem class. """ def __init__( self, numbers ): """ Constructs a new eight puzzle from an ordering of numbers. numbers: a list of integers from 0 to 8 representing an instance of the eight puzzle. 0 represents the blank space. Thus, the list [1, 0, 2, 3, 4, 5, 6, 7, 8] represents the eight puzzle: ------------- | 1 | | 2 | ------------- | 3 | 4 | 5 | ------------- | 6 | 7 | 8 | ------------ The configuration of the puzzle is stored in a 2-dimensional list (a list of lists) 'cells'. """ self.cells = [] numbers = numbers[:] # Make a copy so as not to cause side-effects. numbers.reverse() for row in range( 3 ): self.cells.append( [] ) for col in range( 3 ): self.cells[row].append( numbers.pop() ) if self.cells[row][col] == 0: self.blankLocation = row, col def isGoal( self ): """ Checks to see if the puzzle is in its goal state. ------------- | | 1 | 2 | ------------- | 3 | 4 | 5 | ------------- | 6 | 7 | 8 | ------------- >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).isGoal() True >>> EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).isGoal() False """ current = 0 for row in range( 3 ): for col in range( 3 ): if current != self.cells[row][col]: return False current += 1 return True def legalMoves( self ): """ Returns a list of legal moves from the current state. Moves consist of moving the blank space up, down, left or right. These are encoded as 'up', 'down', 'left' and 'right' respectively. >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).legalMoves() ['down', 'right'] """ moves = [] row, col = self.blankLocation if(row != 0): moves.append('up') if(row != 2): moves.append('down') if(col != 0): moves.append('left') if(col != 2): moves.append('right') return moves def result(self, move): """ Returns a new eightPuzzle with the current state and blankLocation updated based on the provided move. The move should be a string drawn from a list returned by legalMoves. Illegal moves will raise an exception, which may be an array bounds exception. NOTE: This function *does not* change the current object. Instead, it returns a new object. """ row, col = self.blankLocation if(move == 'up'): newrow = row - 1 newcol = col elif(move == 'down'): newrow = row + 1 newcol = col elif(move == 'left'): newrow = row newcol = col - 1 elif(move == 'right'): newrow = row newcol = col + 1 else: raise "Illegal Move" # Create a copy of the current eightPuzzle newPuzzle = EightPuzzleState([0, 0, 0, 0, 0, 0, 0, 0, 0]) newPuzzle.cells = [values[:] for values in self.cells] # And update it to reflect the move newPuzzle.cells[row][col] = self.cells[newrow][newcol] newPuzzle.cells[newrow][newcol] = self.cells[row][col] newPuzzle.blankLocation = newrow, newcol return newPuzzle # Utilities for comparison and display def __eq__(self, other): """ Overloads '==' such that two eightPuzzles with the same configuration are equal. >>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]) == \ EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).result('left') True """ for row in range( 3 ): if self.cells[row] != other.cells[row]: return False return True def __hash__(self): return hash(str(self.cells)) def __getAsciiString(self): """ Returns a display string for the maze """ lines = [] horizontalLine = ('-' * (13)) lines.append(horizontalLine) for row in self.cells: rowLine = '|' for col in row: if col == 0: col = ' ' rowLine = rowLine + ' ' + col.__str__() + ' |' lines.append(rowLine) lines.append(horizontalLine) return '\n'.join(lines) def __str__(self): return self.__getAsciiString() # TODO: Implement The methods in this class class EightPuzzleSearchProblem(search.SearchProblem): """ Implementation of a SearchProblem for the Eight Puzzle domain Each state is represented by an instance of an eightPuzzle. """ def __init__(self,puzzle): "Creates a new EightPuzzleSearchProblem which stores search information." self.puzzle = puzzle def getStartState(self): return puzzle def isGoalState(self,state): return state.isGoal() def getSuccessors(self,state): """ Returns list of (successor, action, stepCost) pairs where each succesor is either left, right, up, or down from the original state and the cost is 1.0 for each """ succ = [] for a in state.legalMoves(): succ.append((state.result(a), a, 1)) return succ 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 """ return len(actions) EIGHT_PUZZLE_DATA = [[1, 0, 2, 3, 4, 5, 6, 7, 8], [1, 7, 8, 2, 3, 4, 5, 6, 0], [4, 3, 2, 7, 0, 5, 1, 6, 8], [5, 1, 3, 4, 0, 2, 6, 7, 8], [1, 2, 5, 7, 6, 8, 0, 4, 3], [0, 3, 1, 6, 8, 2, 7, 5, 4]] def loadEightPuzzle(puzzleNumber): """ puzzleNumber: The number of the eight puzzle to load. Returns an eight puzzle object generated from one of the provided puzzles in EIGHT_PUZZLE_DATA. puzzleNumber can range from 0 to 5. >>> print(loadEightPuzzle(0)) ------------- | 1 | | 2 | ------------- | 3 | 4 | 5 | ------------- | 6 | 7 | 8 | ------------- """ return EightPuzzleState(EIGHT_PUZZLE_DATA[puzzleNumber]) def createRandomEightPuzzle(moves=100): """ moves: number of random moves to apply Creates a random eight puzzle by applying a series of 'moves' random moves to a solved puzzle. """ puzzle = EightPuzzleState([0,1,2,3,4,5,6,7,8]) for i in range(moves): # Execute a random legal move puzzle = puzzle.result(random.sample(puzzle.legalMoves(), 1)[0]) return puzzle if __name__ == '__main__': puzzle = createRandomEightPuzzle(25) print('A random puzzle:') print(puzzle) problem = EightPuzzleSearchProblem(puzzle) path = search.breadthFirstSearch(problem) print('BFS found a path of %d moves: %s' % (len(path), str(path))) curr = puzzle i = 1 for a in path: curr = curr.result(a) print('After %d move%s: %s' % (i, ("", "s")[i>1], a)) print(curr) input("Press return for the next state...") # wait for key stroke i += 1
homework_1_search/game.py
# game.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). # game.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 ([email protected]) and Dan Klein ([email protected]). # For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html from util import * import time, os import traceback import sys ####################### # Parts worth reading # ####################### class Agent: """ An agent must define a getAction method, but may also define the following methods which will be called if they exist: def registerInitialState(self, state): # inspects the starting state """ def __init__(self, index=0): self.index = index def getAction(self, state): """ The Agent will receive a GameState (from either {pacman, capture, sonar}.py) and must return an action from Directions.{North, South, East, West, Stop} """ raiseNotDefined() class Directions: NORTH = 'North' SOUTH = 'South' EAST = 'East' WEST = 'West' STOP = 'Stop' LEFT = {NORTH: WEST, SOUTH: EAST, EAST: NORTH, WEST: SOUTH, STOP: STOP} RIGHT = dict([(y,x) for x, y in LEFT.items()]) REVERSE = {NORTH: SOUTH, SOUTH: NORTH, EAST: WEST, WEST: EAST, STOP: STOP} class Configuration: """ A Configuration holds the (x,y) coordinate of a character, along with its traveling direction. The convention for positions, like a graph, is that (0,0) is the lower left corner, x increases horizontally and y increases vertically. Therefore, north is the direction of increasing y, or (0,1). """ def __init__(self, pos, direction): self.pos = pos self.direction = direction def getPosition(self): return (self.pos) def getDirection(self): return self.direction def isInteger(self): x,y = self.pos return x == int(x) and y == int(y) def __eq__(self, other): if other == None: return False return (self.pos == other.pos and self.direction == other.direction) def __hash__(self): x = hash(self.pos) y = hash(self.direction) return hash(x + 13 * y) def __str__(self): return "(x,y)="+str(self.pos)+", "+str(self.direction) def generateSuccessor(self, vector): """ Generates a new configuration reached by translating the current configuration by the action vector. This is a low-level call and does not attempt to respect the legality of the movement. Actions are movement vectors. """ x, y= self.pos dx, dy = vector direction = Actions.vectorToDirection(vector) if direction == Directions.STOP: direction = self.direction # There is no stop direction return Configuration((x + dx, y+dy), direction) class AgentState: """ AgentStates hold the state of an agent (configuration, speed, scared, etc). """ def __init__( self, startConfiguration, isPacman ): self.start = startConfiguration self.configuration = startConfiguration self.isPacman = isPacman self.scaredTimer = 0 self.numCarrying = 0 self.numReturned = 0 def __str__( self ): if self.isPacman: return "Pacman: " + str( self.configuration ) else: return "Ghost: " + str( self.configuration ) def __eq__( self, other ): if other == None: return False return self.configuration == other.configuration and self.scaredTimer == other.scaredTimer def __hash__(self): return hash(hash(self.configuration) + 13 * hash(self.scaredTimer)) def copy( self ): state = AgentState( self.start, self.isPacman ) state.configuration = self.configuration state.scaredTimer = self.scaredTimer state.numCarrying = self.numCarrying state.numReturned = self.numReturned return state def getPosition(self): if self.configuration == None: return None return self.configuration.getPosition() def getDirection(self): return self.configuration.getDirection() class Grid: """ A 2-dimensional array of objects backed by a list of lists. Data is accessed via grid[x][y] where (x,y) are positions on a Pacman map with x horizontal, y vertical and the origin (0,0) in the bottom left corner. The __str__ method constructs an output that is oriented like a pacman board. """ def __init__(self, width, height, initialValue=False, bitRepresentation=None): if initialValue not in [False, True]: raise Exception('Grids can only contain booleans') self.CELLS_PER_INT = 30 self.width = width self.height = height self.data = [[initialValue for y in range(height)] for x in range(width)] if bitRepresentation: self._unpackBits(bitRepresentation) def __getitem__(self, i): return self.data[i] def __setitem__(self, key, item): self.data[key] = item def __str__(self): out = [[str(self.data[x][y])[0] for x in range(self.width)] for y in range(self.height)] out.reverse() return '\n'.join([''.join(x) for x in out]) def __eq__(self, other): if other == None: return False return self.data == other.data def __hash__(self): # return hash(str(self)) base = 1 h = 0 for l in self.data: for i in l: if i: h += base base *= 2 return hash(h) def copy(self): g = Grid(self.width, self.height) g.data = [x[:] for x in self.data] return g def deepCopy(self): return self.copy() def shallowCopy(self): g = Grid(self.width, self.height) g.data = self.data return g def count(self, item =True ): return sum([x.count(item) for x in self.data]) def asList(self, key = True): list = [] for x in range(self.width): for y in range(self.height): if self[x][y] == key: list.append( (x,y) ) return list def packBits(self): """ Returns an efficient int list representation (width, height, bitPackedInts...) """ bits = [self.width, self.height] currentInt = 0 for i in range(self.height * self.width): bit = self.CELLS_PER_INT - (i % self.CELLS_PER_INT) - 1 x, y = self._cellIndexToPosition(i) if self[x][y]: currentInt += 2 ** bit if (i + 1) % self.CELLS_PER_INT == 0: bits.append(currentInt) currentInt = 0 bits.append(currentInt) return tuple(bits) def _cellIndexToPosition(self, index): x = index // self.height y = index % self.height return x, y def _unpackBits(self, bits): """ Fills in data from a bit-level representation """ cell = 0 for packed in bits: for bit in self._unpackInt(packed, self.CELLS_PER_INT): if cell == self.width * self.height: break x, y = self._cellIndexToPosition(cell) self[x][y] = bit cell += 1 def _unpackInt(self, packed, size): bools = [] if packed < 0: raise ValueError("must be a positive integer") for i in range(size): n = 2 ** (self.CELLS_PER_INT - i - 1) if packed >= n: bools.append(True) packed -= n else: bools.append(False) return bools def reconstituteGrid(bitRep): if type(bitRep) is not type((1,2)): return bitRep width, height = bitRep[:2] return Grid(width, height, bitRepresentation= bitRep[2:]) #################################### # Parts you shouldn't have to read # #################################### class Actions: """ A collection of static methods for manipulating move actions. """ # Directions _directions = {Directions.NORTH: (0, 1), Directions.SOUTH: (0, -1), Directions.EAST: (1, 0), Directions.WEST: (-1, 0), Directions.STOP: (0, 0)} _directionsAsList = _directions.items() TOLERANCE = .001 def reverseDirection(action): if action == Directions.NORTH: return Directions.SOUTH if action == Directions.SOUTH: return Directions.NORTH if action == Directions.EAST: return Directions.WEST if action == Directions.WEST: return Directions.EAST return action reverseDirection = staticmethod(reverseDirection) def vectorToDirection(vector): dx, dy = vector if dy > 0: return Directions.NORTH if dy < 0: return Directions.SOUTH if dx < 0: return Directions.WEST if dx > 0: return Directions.EAST return Directions.STOP vectorToDirection = staticmethod(vectorToDirection) def directionToVector(direction, speed = 1.0): dx, dy = Actions._directions[direction] return (dx * speed, dy * speed) directionToVector = staticmethod(directionToVector) def getPossibleActions(config, walls): possible = [] x, y = config.pos x_int, y_int = int(x + 0.5), int(y + 0.5) # In between grid points, all agents must continue straight if (abs(x - x_int) + abs(y - y_int) > Actions.TOLERANCE): return [config.getDirection()] for dir, vec in Actions._directionsAsList: dx, dy = vec next_y = y_int + dy next_x = x_int + dx if not walls[next_x][next_y]: possible.append(dir) return possible getPossibleActions = staticmethod(getPossibleActions) def getLegalNeighbors(position, walls): x,y = position x_int, y_int = int(x + 0.5), int(y + 0.5) neighbors = [] for dir, vec in Actions._directionsAsList: dx, dy = vec next_x = x_int + dx if next_x < 0 or next_x == walls.width: continue next_y = y_int + dy if next_y < 0 or next_y == walls.height: continue if not walls[next_x][next_y]: neighbors.append((next_x, next_y)) return neighbors getLegalNeighbors = staticmethod(getLegalNeighbors) def getSuccessor(position, action): dx, dy = Actions.directionToVector(action) x, y = position return (x + dx, y + dy) getSuccessor = staticmethod(getSuccessor) class GameStateData: """ """ def __init__( self, prevState = None ): """ Generates a new data packet by copying information from its predecessor. """ if prevState != None: self.food = prevState.food.shallowCopy() self.capsules = prevState.capsules[:] self.agentStates = self.copyAgentStates( prevState.agentStates ) self.layout = prevState.layout self._eaten = prevState._eaten self.score = prevState.score self._foodEaten = None self._foodAdded = None self._capsuleEaten = None self._agentMoved = None self._lose = False self._win = False self.scoreChange = 0 def deepCopy( self ): state = GameStateData( self ) state.food = self.food.deepCopy() state.layout = self.layout.deepCopy() state._agentMoved = self._agentMoved state._foodEaten = self._foodEaten state._foodAdded = self._foodAdded state._capsuleEaten = self._capsuleEaten return state def copyAgentStates( self, agentStates ): copiedStates = [] for agentState in agentStates: copiedStates.append( agentState.copy() ) return copiedStates def __eq__( self, other ): """ Allows two states to be compared. """ if other == None: return False # TODO Check for type of other if not self.agentStates == other.agentStates: return False if not self.food == other.food: return False if not self.capsules == other.capsules: return False if not self.score == other.score: return False return True def __hash__( self ): """ Allows states to be keys of dictionaries. """ for i, state in enumerate( self.agentStates ): try: int(hash(state)) except TypeError as e: print(e) #hash(state) return int((hash(tuple(self.agentStates)) + 13*hash(self.food) + 113* hash(tuple(self.capsules)) + 7 * hash(self.score)) % 1048575 ) def __str__( self ): width, height = self.layout.width, self.layout.height map = Grid(width, height) if type(self.food) == type((1,2)): self.food = reconstituteGrid(self.food) for x in range(width): for y in range(height): food, walls = self.food, self.layout.walls map[x][y] = self._foodWallStr(food[x][y], walls[x][y]) for agentState in self.agentStates: if agentState == None: continue if agentState.configuration == None: continue x,y = [int( i ) for i in nearestPoint( agentState.configuration.pos )] agent_dir = agentState.configuration.direction if agentState.isPacman: map[x][y] = self._pacStr( agent_dir ) else: map[x][y] = self._ghostStr( agent_dir ) for x, y in self.capsules: map[x][y] = 'o' return str(map) + ("\nScore: %d\n" % self.score) def _foodWallStr( self, hasFood, hasWall ): if hasFood: return '.' elif hasWall: return '%' else: return ' ' def _pacStr( self, dir ): if dir == Directions.NORTH: return 'v' if dir == Directions.SOUTH: return '^' if dir == Directions.WEST: return '>' return '<' def _ghostStr( self, dir ): return 'G' if dir == Directions.NORTH: return 'M' if dir == Directions.SOUTH: return 'W' if dir == Directions.WEST: return '3' return 'E' def initialize( self, layout, numGhostAgents ): """ Creates an initial game state from a layout array (see layout.py). """ self.food = layout.food.copy() #self.capsules = [] self.capsules = layout.capsules[:] self.layout = layout self.score = 0 self.scoreChange = 0 self.agentStates = [] numGhosts = 0 for isPacman, pos in layout.agentPositions: if not isPacman: if numGhosts == numGhostAgents: continue # Max ghosts reached already else: numGhosts += 1 self.agentStates.append( AgentState( Configuration( pos, Directions.STOP), isPacman) ) self._eaten = [False for a in self.agentStates] try: import boinc _BOINC_ENABLED = True except: _BOINC_ENABLED = False class Game: """ The Game manages the control flow, soliciting actions from agents. """ def __init__( self, agents, display, rules, startingIndex=0, muteAgents=False, catchExceptions=False ): self.agentCrashed = False self.agents = agents self.display = display self.rules = rules self.startingIndex = startingIndex self.gameOver = False self.muteAgents = muteAgents self.catchExceptions = catchExceptions self.moveHistory = [] self.totalAgentTimes = [0 for agent in agents] self.totalAgentTimeWarnings = [0 for agent in agents] self.agentTimeout = False import io self.agentOutput = [io.StringIO() for agent in agents] def getProgress(self): if self.gameOver: return 1.0 else: return self.rules.getProgress(self) def _agentCrash( self, agentIndex, quiet=False): "Helper method for handling agent crashes" if not quiet: traceback.print_exc() self.gameOver = True self.agentCrashed = True self.rules.agentCrash(self, agentIndex) OLD_STDOUT = None OLD_STDERR = None def mute(self, agentIndex): if not self.muteAgents: return global OLD_STDOUT, OLD_STDERR import io OLD_STDOUT = sys.stdout OLD_STDERR = sys.stderr sys.stdout = self.agentOutput[agentIndex] sys.stderr = self.agentOutput[agentIndex] def unmute(self): if not self.muteAgents: return global OLD_STDOUT, OLD_STDERR # Revert stdout/stderr to originals sys.stdout = OLD_STDOUT sys.stderr = OLD_STDERR def run( self ): """ Main control loop for game play. """ self.display.initialize(self.state.data) self.numMoves = 0 ###self.display.initialize(self.state.makeObservation(1).data) # inform learning agents of the game start for i in range(len(self.agents)): agent = self.agents[i] if not agent: self.mute(i) # this is a null agent, meaning it failed to load # the other team wins print("Agent %d failed to load" % i, file=sys.stderr) self.unmute() self._agentCrash(i, quiet=True) return if ("registerInitialState" in dir(agent)): self.mute(i) if self.catchExceptions: try: timed_func = TimeoutFunction(agent.registerInitialState, int(self.rules.getMaxStartupTime(i))) try: start_time = time.time() timed_func(self.state.deepCopy()) time_taken = time.time() - start_time self.totalAgentTimes[i] += time_taken except TimeoutFunctionException: print("Agent %d ran out of time on startup!" % i, file=sys.stderr) self.unmute() self.agentTimeout = True self._agentCrash(i, quiet=True) return except Exception as data: self._agentCrash(i, quiet=False) self.unmute() return else: agent.registerInitialState(self.state.deepCopy()) ## TODO: could this exceed the total time self.unmute() agentIndex = self.startingIndex numAgents = len( self.agents ) while not self.gameOver: # Fetch the next agent agent = self.agents[agentIndex] move_time = 0 skip_action = False # Generate an observation of the state if 'observationFunction' in dir( agent ): self.mute(agentIndex) if self.catchExceptions: try: timed_func = TimeoutFunction(agent.observationFunction, int(self.rules.getMoveTimeout(agentIndex))) try: start_time = time.time() observation = timed_func(self.state.deepCopy()) except TimeoutFunctionException: skip_action = True move_time += time.time() - start_time self.unmute() except Exception as data: self._agentCrash(agentIndex, quiet=False) self.unmute() return else: observation = agent.observationFunction(self.state.deepCopy()) self.unmute() else: observation = self.state.deepCopy() # Solicit an action action = None self.mute(agentIndex) if self.catchExceptions: try: timed_func = TimeoutFunction(agent.getAction, int(self.rules.getMoveTimeout(agentIndex)) - int(move_time)) try: start_time = time.time() if skip_action: raise TimeoutFunctionException() action = timed_func( observation ) except TimeoutFunctionException: print("Agent %d timed out on a single move!" % agentIndex, file=sys.stderr) self.agentTimeout = True self._agentCrash(agentIndex, quiet=True) self.unmute() return move_time += time.time() - start_time if move_time > self.rules.getMoveWarningTime(agentIndex): self.totalAgentTimeWarnings[agentIndex] += 1 print("Agent %d took too long to make a move! This is warning %d" % (agentIndex, self.totalAgentTimeWarnings[agentIndex]), file=sys.stderr) if self.totalAgentTimeWarnings[agentIndex] > self.rules.getMaxTimeWarnings(agentIndex): print("Agent %d exceeded the maximum number of warnings: %d" % (agentIndex, self.totalAgentTimeWarnings[agentIndex]), file=sys.stderr) self.agentTimeout = True self._agentCrash(agentIndex, quiet=True) self.unmute() return self.totalAgentTimes[agentIndex] += move_time #print("Agent: %d, time: %f, total: %f" % (agentIndex, move_time, self.totalAgentTimes[agentIndex])) if self.totalAgentTimes[agentIndex] > self.rules.getMaxTotalTime(agentIndex): print("Agent %d ran out of time! (time: %1.2f)" % (agentIndex, self.totalAgentTimes[agentIndex]), file=sys.stderr) self.agentTimeout = True self._agentCrash(agentIndex, quiet=True) self.unmute() return self.unmute() except Exception as data: self._agentCrash(agentIndex) self.unmute() return else: action = agent.getAction(observation) self.unmute() # Execute the action self.moveHistory.append( (agentIndex, action) ) if self.catchExceptions: try: self.state = self.state.generateSuccessor( agentIndex, action ) except Exception as data: self.mute(agentIndex) self._agentCrash(agentIndex) self.unmute() return else: self.state = self.state.generateSuccessor( agentIndex, action ) # Change the display self.display.update( self.state.data ) ###idx = agentIndex - agentIndex % 2 + 1 ###self.display.update( self.state.makeObservation(idx).data ) # Allow for game specific conditions (winning, losing, etc.) self.rules.process(self.state, self) # Track progress if agentIndex == numAgents + 1: self.numMoves += 1 # Next agent agentIndex = ( agentIndex + 1 ) % numAgents if _BOINC_ENABLED: boinc.set_fraction_done(self.getProgress()) # inform a learning agent of the game result for agentIndex, agent in enumerate(self.agents): if "final" in dir( agent ) : try: self.mute(agentIndex) agent.final( self.state ) self.unmute() except Exception as data: if not self.catchExceptions: raise data self._agentCrash(agentIndex) self.unmute() return self.display.finish()
homework_1_search/ghostAgents.py
# ghostAgents.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). from game import Agent from game import Actions from game import Directions import random from util import manhattanDistance import util class GhostAgent( Agent ): def __init__( self, index ): self.index = index def getAction( self, state ): dist = self.getDistribution(state) if len(dist) == 0: return Directions.STOP else: return util.chooseFromDistribution( dist ) def getDistribution(self, state): "Returns a Counter encoding a distribution over actions from the provided state." util.raiseNotDefined() class RandomGhost( GhostAgent ): "A ghost that chooses a legal action uniformly at random." def getDistribution( self, state ): dist = util.Counter() for a in state.getLegalActions( self.index ): dist[a] = 1.0 dist.normalize() return dist class DirectionalGhost( GhostAgent ): "A ghost that prefers to rush Pacman, or flee when scared." def __init__( self, index, prob_attack=0.8, prob_scaredFlee=0.8 ): self.index = index self.prob_attack = prob_attack self.prob_scaredFlee = prob_scaredFlee def getDistribution( self, state ): # Read variables from state ghostState = state.getGhostState( self.index ) legalActions = state.getLegalActions( self.index ) pos = state.getGhostPosition( self.index ) isScared = ghostState.scaredTimer > 0 speed = 1 if isScared: speed = 0.5 actionVectors = [Actions.directionToVector( a, speed ) for a in legalActions] newPositions = [( pos[0]+a[0], pos[1]+a[1] ) for a in actionVectors] pacmanPosition = state.getPacmanPosition() # Select best actions given the state distancesToPacman = [manhattanDistance( pos, pacmanPosition ) for pos in newPositions] if isScared: bestScore = max( distancesToPacman ) bestProb = self.prob_scaredFlee else: bestScore = min( distancesToPacman ) bestProb = self.prob_attack bestActions = [action for action, distance in zip( legalActions, distancesToPacman ) if distance == bestScore] # Construct distribution dist = util.Counter() for a in bestActions: dist[a] = bestProb / len(bestActions) for a in legalActions: dist[a] += ( 1-bestProb ) / len(legalActions) dist.normalize() return dist
homework_1_search/grading.py
# grading.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). "Common code for autograders" import cgi import time import sys import json import traceback import pdb from collections import defaultdict import util class Grades: "A data structure for project grades, along with formatting code to display them" def __init__(self, projectName, questionsAndMaxesList, gsOutput=False, edxOutput=False, muteOutput=False): """ Defines the grading scheme for a project projectName: project name questionsAndMaxesDict: a list of (question name, max points per question) """ self.questions = [el[0] for el in questionsAndMaxesList] self.maxes = dict(questionsAndMaxesList) self.points = Counter() self.messages = dict([(q, []) for q in self.questions]) self.project = projectName self.start = time.localtime()[1:6] self.sane = True # Sanity checks self.currentQuestion = None # Which question we're grading self.edxOutput = edxOutput self.gsOutput = gsOutput # GradeScope output self.mute = muteOutput self.prereqs = defaultdict(set) #print('Autograder transcript for %s' % self.project) print('Starting on %d-%d at %d:%02d:%02d' % self.start) def addPrereq(self, question, prereq): self.prereqs[question].add(prereq) def grade(self, gradingModule, exceptionMap = {}, bonusPic = False): """ Grades each question gradingModule: the module with all the grading functions (pass in with sys.modules[__name__]) """ completedQuestions = set([]) for q in self.questions: print('\nQuestion %s' % q) print('=' * (9 + len(q))) print self.currentQuestion = q incompleted = self.prereqs[q].difference(completedQuestions) if len(incompleted) > 0: prereq = incompleted.pop() print( """*** NOTE: Make sure to complete Question %s before working on Question %s, *** because Question %s builds upon your answer for Question %s. """ % (prereq, q, q, prereq)) continue if self.mute: util.mutePrint() try: util.TimeoutFunction(getattr(gradingModule, q),1800)(self) # Call the question's function #TimeoutFunction(getattr(gradingModule, q),1200)(self) # Call the question's function except Exception as inst: self.addExceptionMessage(q, inst, traceback) self.addErrorHints(exceptionMap, inst, q[1]) except: self.fail('FAIL: Terminated with a string exception.') finally: if self.mute: util.unmutePrint() if self.points[q] >= self.maxes[q]: completedQuestions.add(q) print('\n### Question %s: %d/%d ###\n' % (q, self.points[q], self.maxes[q])) print('\nFinished at %d:%02d:%02d' % time.localtime()[3:6]) print("\nProvisional grades\n==================") for q in self.questions: print('Question %s: %d/%d' % (q, self.points[q], self.maxes[q])) print('------------------') print('Total: %d/%d' % (self.points.totalCount(), sum(self.maxes.values()))) if bonusPic and self.points.totalCount() == 25: print(""" ALL HAIL GRANDPAC. LONG LIVE THE GHOSTBUSTING KING. --- ---- --- | \ / + \ / | | + \--/ \--/ + | | + + | | + + + | @@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ \ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ \ / @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ V \ @@@@@@@@@@@@@@@@@@@@@@@@@@@@ \ / @@@@@@@@@@@@@@@@@@@@@@@@@@ V @@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@ /\ @@@@@@@@@@@@@@@@@@@@@@ / \ @@@@@@@@@@@@@@@@@@@@@@@@@ /\ / @@@@@@@@@@@@@@@@@@@@@@@@@@@ / \ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ / @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@ """) print(""" Your grades are NOT yet registered. To register your grades, make sure to follow your instructor's guidelines to receive credit on your project. """) if self.edxOutput: self.produceOutput() if self.gsOutput: self.produceGradeScopeOutput() def addExceptionMessage(self, q, inst, traceback): """ Method to format the exception message, this is more complicated because we need to cgi.escape the traceback but wrap the exception in a <pre> tag """ self.fail('FAIL: Exception raised: %s' % inst) self.addMessage('') for line in traceback.format_exc().split('\n'): self.addMessage(line) def addErrorHints(self, exceptionMap, errorInstance, questionNum): typeOf = str(type(errorInstance)) questionName = 'q' + questionNum errorHint = '' # question specific error hints if exceptionMap.get(questionName): questionMap = exceptionMap.get(questionName) if (questionMap.get(typeOf)): errorHint = questionMap.get(typeOf) # fall back to general error messages if a question specific # one does not exist if (exceptionMap.get(typeOf)): errorHint = exceptionMap.get(typeOf) # dont include the HTML if we have no error hint if not errorHint: return '' for line in errorHint.split('\n'): self.addMessage(line) def produceGradeScopeOutput(self): out_dct = {} # total of entire submission total_possible = sum(self.maxes.values()) total_score = sum(self.points.values()) out_dct['score'] = total_score out_dct['max_score'] = total_possible out_dct['output'] = "Total score (%d / %d)" % (total_score, total_possible) # individual tests tests_out = [] for name in self.questions: test_out = {} # test name test_out['name'] = name # test score test_out['score'] = self.points[name] test_out['max_score'] = self.maxes[name] # others is_correct = self.points[name] >= self.maxes[name] test_out['output'] = " Question {num} ({points}/{max}) {correct}".format( num=(name[1] if len(name) == 2 else name), points=test_out['score'], max=test_out['max_score'], correct=('X' if not is_correct else ''), ) test_out['tags'] = [] tests_out.append(test_out) out_dct['tests'] = tests_out # file output with open('gradescope_response.json', 'w') as outfile: json.dump(out_dct, outfile) return def produceOutput(self): edxOutput = open('edx_response.html', 'w') edxOutput.write("<div>") # first sum total_possible = sum(self.maxes.values()) total_score = sum(self.points.values()) checkOrX = '<span class="incorrect"/>' if (total_score >= total_possible): checkOrX = '<span class="correct"/>' header = """ <h3> Total score ({total_score} / {total_possible}) </h3> """.format(total_score = total_score, total_possible = total_possible, checkOrX = checkOrX ) edxOutput.write(header) for q in self.questions: if len(q) == 2: name = q[1] else: name = q checkOrX = '<span class="incorrect"/>' if (self.points[q] >= self.maxes[q]): checkOrX = '<span class="correct"/>' #messages = '\n<br/>\n'.join(self.messages[q]) messages = "<pre>%s</pre>" % '\n'.join(self.messages[q]) output = """ <div class="test"> <section> <div class="shortform"> Question {q} ({points}/{max}) {checkOrX} </div> <div class="longform"> {messages} </div> </section> </div> """.format(q = name, max = self.maxes[q], messages = messages, checkOrX = checkOrX, points = self.points[q] ) # print("*** output for Question %s " % q[1]) # print(output) edxOutput.write(output) edxOutput.write("</div>") edxOutput.close() edxOutput = open('edx_grade', 'w') edxOutput.write(str(self.points.totalCount())) edxOutput.close() def fail(self, message, raw=False): "Sets sanity check bit to false and outputs a message" self.sane = False self.assignZeroCredit() self.addMessage(message, raw) def assignZeroCredit(self): self.points[self.currentQuestion] = 0 def addPoints(self, amt): self.points[self.currentQuestion] += amt def deductPoints(self, amt): self.points[self.currentQuestion] -= amt def assignFullCredit(self, message="", raw=False): self.points[self.currentQuestion] = self.maxes[self.currentQuestion] if message != "": self.addMessage(message, raw) def addMessage(self, message, raw=False): if not raw: # We assume raw messages, formatted for HTML, are printed separately if self.mute: util.unmutePrint() print('*** ' + message) if self.mute: util.mutePrint() message = cgi.escape(message) self.messages[self.currentQuestion].append(message) def addMessageToEmail(self, message): print("WARNING**** addMessageToEmail is deprecated %s" % message) for line in message.split('\n'): pass #print('%%% ' + line + ' %%%') #self.messages[self.currentQuestion].append(line) class Counter(dict): """ Dict with default 0 """ def __getitem__(self, idx): try: return dict.__getitem__(self, idx) except KeyError: return 0 def totalCount(self): """ Returns the sum of counts for all keys. """ return sum(self.values())
homework_1_search/graphicsDisplay.py
# graphicsDisplay.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). from graphicsUtils import * import math, time from game import Directions ########################### # GRAPHICS DISPLAY CODE # ########################### # Most code by Dan Klein and John Denero written or rewritten for cs188, UC Berkeley. # Some code from a Pacman implementation by LiveWires, and used / modified with permission. DEFAULT_GRID_SIZE = 30.0 INFO_PANE_HEIGHT = 35 BACKGROUND_COLOR = formatColor(0,0,0) WALL_COLOR = formatColor(0.0/255.0, 51.0/255.0, 255.0/255.0) INFO_PANE_COLOR = formatColor(.4,.4,0) SCORE_COLOR = formatColor(.9, .9, .9) PACMAN_OUTLINE_WIDTH = 2 PACMAN_CAPTURE_OUTLINE_WIDTH = 4 GHOST_COLORS = [] GHOST_COLORS.append(formatColor(.9,0,0)) # Red GHOST_COLORS.append(formatColor(0,.3,.9)) # Blue GHOST_COLORS.append(formatColor(.98,.41,.07)) # Orange GHOST_COLORS.append(formatColor(.1,.75,.7)) # Green GHOST_COLORS.append(formatColor(1.0,0.6,0.0)) # Yellow GHOST_COLORS.append(formatColor(.4,0.13,0.91)) # Purple TEAM_COLORS = GHOST_COLORS[:2] GHOST_SHAPE = [ ( 0, 0.3 ), ( 0.25, 0.75 ), ( 0.5, 0.3 ), ( 0.75, 0.75 ), ( 0.75, -0.5 ), ( 0.5, -0.75 ), (-0.5, -0.75 ), (-0.75, -0.5 ), (-0.75, 0.75 ), (-0.5, 0.3 ), (-0.25, 0.75 ) ] GHOST_SIZE = 0.65 SCARED_COLOR = formatColor(1,1,1) GHOST_VEC_COLORS = [colorToVector(c) for c in GHOST_COLORS] PACMAN_COLOR = formatColor(255.0/255.0,255.0/255.0,61.0/255) PACMAN_SCALE = 0.5 #pacman_speed = 0.25 # Food FOOD_COLOR = formatColor(1,1,1) FOOD_SIZE = 0.1 # Laser LASER_COLOR = formatColor(1,0,0) LASER_SIZE = 0.02 # Capsule graphics CAPSULE_COLOR = formatColor(1,1,1) CAPSULE_SIZE = 0.25 # Drawing walls WALL_RADIUS = 0.15 class InfoPane: def __init__(self, layout, gridSize): self.gridSize = gridSize self.width = (layout.width) * gridSize self.base = (layout.height + 1) * gridSize self.height = INFO_PANE_HEIGHT self.fontSize = 24 self.textColor = PACMAN_COLOR self.drawPane() def toScreen(self, pos, y = None): """ Translates a point relative from the bottom left of the info pane. """ if y == None: x,y = pos else: x = pos x = self.gridSize + x # Margin y = self.base + y return x,y def drawPane(self): self.scoreText = text( self.toScreen(0, 0 ), self.textColor, "SCORE: 0", "Times", self.fontSize, "bold") def initializeGhostDistances(self, distances): self.ghostDistanceText = [] size = 20 if self.width < 240: size = 12 if self.width < 160: size = 10 for i, d in enumerate(distances): t = text( self.toScreen(self.width//2 + self.width//8 * i, 0), GHOST_COLORS[i+1], d, "Times", size, "bold") self.ghostDistanceText.append(t) def updateScore(self, score): changeText(self.scoreText, "SCORE: % 4d" % score) def setTeam(self, isBlue): text = "RED TEAM" if isBlue: text = "BLUE TEAM" self.teamText = text( self.toScreen(300, 0 ), self.textColor, text, "Times", self.fontSize, "bold") def updateGhostDistances(self, distances): if len(distances) == 0: return if 'ghostDistanceText' not in dir(self): self.initializeGhostDistances(distances) else: for i, d in enumerate(distances): changeText(self.ghostDistanceText[i], d) def drawGhost(self): pass def drawPacman(self): pass def drawWarning(self): pass def clearIcon(self): pass def updateMessage(self, message): pass def clearMessage(self): pass class PacmanGraphics: def __init__(self, zoom=1.0, frameTime=0.0, capture=False): self.have_window = 0 self.currentGhostImages = {} self.pacmanImage = None self.zoom = zoom self.gridSize = DEFAULT_GRID_SIZE * zoom self.capture = capture self.frameTime = frameTime def checkNullDisplay(self): return False def initialize(self, state, isBlue = False): self.isBlue = isBlue self.startGraphics(state) # self.drawDistributions(state) self.distributionImages = None # Initialized lazily self.drawStaticObjects(state) self.drawAgentObjects(state) # Information self.previousState = state def startGraphics(self, state): self.layout = state.layout layout = self.layout self.width = layout.width self.height = layout.height self.make_window(self.width, self.height) self.infoPane = InfoPane(layout, self.gridSize) self.currentState = layout def drawDistributions(self, state): walls = state.layout.walls dist = [] for x in range(walls.width): distx = [] dist.append(distx) for y in range(walls.height): ( screen_x, screen_y ) = self.to_screen( (x, y) ) block = square( (screen_x, screen_y), 0.5 * self.gridSize, color = BACKGROUND_COLOR, filled = 1, behind=2) distx.append(block) self.distributionImages = dist def drawStaticObjects(self, state): layout = self.layout self.drawWalls(layout.walls) self.food = self.drawFood(layout.food) self.capsules = self.drawCapsules(layout.capsules) refresh() def drawAgentObjects(self, state): self.agentImages = [] # (agentState, image) for index, agent in enumerate(state.agentStates): if agent.isPacman: image = self.drawPacman(agent, index) self.agentImages.append( (agent, image) ) else: image = self.drawGhost(agent, index) self.agentImages.append( (agent, image) ) refresh() def swapImages(self, agentIndex, newState): """ Changes an image from a ghost to a pacman or vis versa (for capture) """ prevState, prevImage = self.agentImages[agentIndex] for item in prevImage: remove_from_screen(item) if newState.isPacman: image = self.drawPacman(newState, agentIndex) self.agentImages[agentIndex] = (newState, image ) else: image = self.drawGhost(newState, agentIndex) self.agentImages[agentIndex] = (newState, image ) refresh() def update(self, newState): agentIndex = newState._agentMoved agentState = newState.agentStates[agentIndex] if self.agentImages[agentIndex][0].isPacman != agentState.isPacman: self.swapImages(agentIndex, agentState) prevState, prevImage = self.agentImages[agentIndex] if agentState.isPacman: self.animatePacman(agentState, prevState, prevImage) else: self.moveGhost(agentState, agentIndex, prevState, prevImage) self.agentImages[agentIndex] = (agentState, prevImage) if newState._foodEaten != None: self.removeFood(newState._foodEaten, self.food) if newState._capsuleEaten != None: self.removeCapsule(newState._capsuleEaten, self.capsules) self.infoPane.updateScore(newState.score) if 'ghostDistances' in dir(newState): self.infoPane.updateGhostDistances(newState.ghostDistances) def make_window(self, width, height): grid_width = (width-1) * self.gridSize grid_height = (height-1) * self.gridSize screen_width = 2*self.gridSize + grid_width screen_height = 2*self.gridSize + grid_height + INFO_PANE_HEIGHT begin_graphics(screen_width, screen_height, BACKGROUND_COLOR, "CS188 Pacman") def drawPacman(self, pacman, index): position = self.getPosition(pacman) screen_point = self.to_screen(position) endpoints = self.getEndpoints(self.getDirection(pacman)) width = PACMAN_OUTLINE_WIDTH outlineColor = PACMAN_COLOR fillColor = PACMAN_COLOR if self.capture: outlineColor = TEAM_COLORS[index % 2] fillColor = GHOST_COLORS[index] width = PACMAN_CAPTURE_OUTLINE_WIDTH return [circle(screen_point, PACMAN_SCALE * self.gridSize, fillColor = fillColor, outlineColor = outlineColor, endpoints = endpoints, width = width)] def getEndpoints(self, direction, position=(0,0)): x, y = position pos = x - int(x) + y - int(y) width = 30 + 80 * math.sin(math.pi* pos) delta = width / 2 if (direction == 'West'): endpoints = (180+delta, 180-delta) elif (direction == 'North'): endpoints = (90+delta, 90-delta) elif (direction == 'South'): endpoints = (270+delta, 270-delta) else: endpoints = (0+delta, 0-delta) return endpoints def movePacman(self, position, direction, image): screenPosition = self.to_screen(position) endpoints = self.getEndpoints( direction, position ) r = PACMAN_SCALE * self.gridSize moveCircle(image[0], screenPosition, r, endpoints) refresh() def animatePacman(self, pacman, prevPacman, image): if self.frameTime < 0: print('Press any key to step forward, "q" to play') keys = wait_for_keys() if 'q' in keys: self.frameTime = 0.1 if self.frameTime > 0.01 or self.frameTime < 0: start = time.time() fx, fy = self.getPosition(prevPacman) px, py = self.getPosition(pacman) frames = 4.0 for i in range(1,int(frames) + 1): pos = px*i/frames + fx*(frames-i)/frames, py*i/frames + fy*(frames-i)/frames self.movePacman(pos, self.getDirection(pacman), image) refresh() sleep(abs(self.frameTime) / frames) else: self.movePacman(self.getPosition(pacman), self.getDirection(pacman), image) refresh() def getGhostColor(self, ghost, ghostIndex): if ghost.scaredTimer > 0: return SCARED_COLOR else: return GHOST_COLORS[ghostIndex] def drawGhost(self, ghost, agentIndex): pos = self.getPosition(ghost) dir = self.getDirection(ghost) (screen_x, screen_y) = (self.to_screen(pos) ) coords = [] for (x, y) in GHOST_SHAPE: coords.append((x*self.gridSize*GHOST_SIZE + screen_x, y*self.gridSize*GHOST_SIZE + screen_y)) colour = self.getGhostColor(ghost, agentIndex) body = polygon(coords, colour, filled = 1) WHITE = formatColor(1.0, 1.0, 1.0) BLACK = formatColor(0.0, 0.0, 0.0) dx = 0 dy = 0 if dir == 'North': dy = -0.2 if dir == 'South': dy = 0.2 if dir == 'East': dx = 0.2 if dir == 'West': dx = -0.2 leftEye = circle((screen_x+self.gridSize*GHOST_SIZE*(-0.3+dx/1.5), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy/1.5)), self.gridSize*GHOST_SIZE*0.2, WHITE, WHITE) rightEye = circle((screen_x+self.gridSize*GHOST_SIZE*(0.3+dx/1.5), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy/1.5)), self.gridSize*GHOST_SIZE*0.2, WHITE, WHITE) leftPupil = circle((screen_x+self.gridSize*GHOST_SIZE*(-0.3+dx), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy)), self.gridSize*GHOST_SIZE*0.08, BLACK, BLACK) rightPupil = circle((screen_x+self.gridSize*GHOST_SIZE*(0.3+dx), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy)), self.gridSize*GHOST_SIZE*0.08, BLACK, BLACK) ghostImageParts = [] ghostImageParts.append(body) ghostImageParts.append(leftEye) ghostImageParts.append(rightEye) ghostImageParts.append(leftPupil) ghostImageParts.append(rightPupil) return ghostImageParts def moveEyes(self, pos, dir, eyes): (screen_x, screen_y) = (self.to_screen(pos) ) dx = 0 dy = 0 if dir == 'North': dy = -0.2 if dir == 'South': dy = 0.2 if dir == 'East': dx = 0.2 if dir == 'West': dx = -0.2 moveCircle(eyes[0],(screen_x+self.gridSize*GHOST_SIZE*(-0.3+dx/1.5), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy/1.5)), self.gridSize*GHOST_SIZE*0.2) moveCircle(eyes[1],(screen_x+self.gridSize*GHOST_SIZE*(0.3+dx/1.5), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy/1.5)), self.gridSize*GHOST_SIZE*0.2) moveCircle(eyes[2],(screen_x+self.gridSize*GHOST_SIZE*(-0.3+dx), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy)), self.gridSize*GHOST_SIZE*0.08) moveCircle(eyes[3],(screen_x+self.gridSize*GHOST_SIZE*(0.3+dx), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy)), self.gridSize*GHOST_SIZE*0.08) def moveGhost(self, ghost, ghostIndex, prevGhost, ghostImageParts): old_x, old_y = self.to_screen(self.getPosition(prevGhost)) new_x, new_y = self.to_screen(self.getPosition(ghost)) delta = new_x - old_x, new_y - old_y for ghostImagePart in ghostImageParts: move_by(ghostImagePart, delta) refresh() if ghost.scaredTimer > 0: color = SCARED_COLOR else: color = GHOST_COLORS[ghostIndex] edit(ghostImageParts[0], ('fill', color), ('outline', color)) self.moveEyes(self.getPosition(ghost), self.getDirection(ghost), ghostImageParts[-4:]) refresh() def getPosition(self, agentState): if agentState.configuration == None: return (-1000, -1000) return agentState.getPosition() def getDirection(self, agentState): if agentState.configuration == None: return Directions.STOP return agentState.configuration.getDirection() def finish(self): end_graphics() def to_screen(self, point): ( x, y ) = point #y = self.height - y x = (x + 1)*self.gridSize y = (self.height - y)*self.gridSize return ( x, y ) # Fixes some TK issue with off-center circles def to_screen2(self, point): ( x, y ) = point #y = self.height - y x = (x + 1)*self.gridSize y = (self.height - y)*self.gridSize return ( x, y ) def drawWalls(self, wallMatrix): wallColor = WALL_COLOR for xNum, x in enumerate(wallMatrix): if self.capture and (xNum * 2) < wallMatrix.width: wallColor = TEAM_COLORS[0] if self.capture and (xNum * 2) >= wallMatrix.width: wallColor = TEAM_COLORS[1] for yNum, cell in enumerate(x): if cell: # There's a wall here pos = (xNum, yNum) screen = self.to_screen(pos) screen2 = self.to_screen2(pos) # draw each quadrant of the square based on adjacent walls wIsWall = self.isWall(xNum-1, yNum, wallMatrix) eIsWall = self.isWall(xNum+1, yNum, wallMatrix) nIsWall = self.isWall(xNum, yNum+1, wallMatrix) sIsWall = self.isWall(xNum, yNum-1, wallMatrix) nwIsWall = self.isWall(xNum-1, yNum+1, wallMatrix) swIsWall = self.isWall(xNum-1, yNum-1, wallMatrix) neIsWall = self.isWall(xNum+1, yNum+1, wallMatrix) seIsWall = self.isWall(xNum+1, yNum-1, wallMatrix) # NE quadrant if (not nIsWall) and (not eIsWall): # inner circle circle(screen2, WALL_RADIUS * self.gridSize, wallColor, wallColor, (0,91), 'arc') if (nIsWall) and (not eIsWall): # vertical line line(add(screen, (self.gridSize*WALL_RADIUS, 0)), add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(-0.5)-1)), wallColor) if (not nIsWall) and (eIsWall): # horizontal line line(add(screen, (0, self.gridSize*(-1)*WALL_RADIUS)), add(screen, (self.gridSize*0.5+1, self.gridSize*(-1)*WALL_RADIUS)), wallColor) if (nIsWall) and (eIsWall) and (not neIsWall): # outer circle circle(add(screen2, (self.gridSize*2*WALL_RADIUS, self.gridSize*(-2)*WALL_RADIUS)), WALL_RADIUS * self.gridSize-1, wallColor, wallColor, (180,271), 'arc') line(add(screen, (self.gridSize*2*WALL_RADIUS-1, self.gridSize*(-1)*WALL_RADIUS)), add(screen, (self.gridSize*0.5+1, self.gridSize*(-1)*WALL_RADIUS)), wallColor) line(add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(-2)*WALL_RADIUS+1)), add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(-0.5))), wallColor) # NW quadrant if (not nIsWall) and (not wIsWall): # inner circle circle(screen2, WALL_RADIUS * self.gridSize, wallColor, wallColor, (90,181), 'arc') if (nIsWall) and (not wIsWall): # vertical line line(add(screen, (self.gridSize*(-1)*WALL_RADIUS, 0)), add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(-0.5)-1)), wallColor) if (not nIsWall) and (wIsWall): # horizontal line line(add(screen, (0, self.gridSize*(-1)*WALL_RADIUS)), add(screen, (self.gridSize*(-0.5)-1, self.gridSize*(-1)*WALL_RADIUS)), wallColor) if (nIsWall) and (wIsWall) and (not nwIsWall): # outer circle circle(add(screen2, (self.gridSize*(-2)*WALL_RADIUS, self.gridSize*(-2)*WALL_RADIUS)), WALL_RADIUS * self.gridSize-1, wallColor, wallColor, (270,361), 'arc') line(add(screen, (self.gridSize*(-2)*WALL_RADIUS+1, self.gridSize*(-1)*WALL_RADIUS)), add(screen, (self.gridSize*(-0.5), self.gridSize*(-1)*WALL_RADIUS)), wallColor) line(add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(-2)*WALL_RADIUS+1)), add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(-0.5))), wallColor) # SE quadrant if (not sIsWall) and (not eIsWall): # inner circle circle(screen2, WALL_RADIUS * self.gridSize, wallColor, wallColor, (270,361), 'arc') if (sIsWall) and (not eIsWall): # vertical line line(add(screen, (self.gridSize*WALL_RADIUS, 0)), add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(0.5)+1)), wallColor) if (not sIsWall) and (eIsWall): # horizontal line line(add(screen, (0, self.gridSize*(1)*WALL_RADIUS)), add(screen, (self.gridSize*0.5+1, self.gridSize*(1)*WALL_RADIUS)), wallColor) if (sIsWall) and (eIsWall) and (not seIsWall): # outer circle circle(add(screen2, (self.gridSize*2*WALL_RADIUS, self.gridSize*(2)*WALL_RADIUS)), WALL_RADIUS * self.gridSize-1, wallColor, wallColor, (90,181), 'arc') line(add(screen, (self.gridSize*2*WALL_RADIUS-1, self.gridSize*(1)*WALL_RADIUS)), add(screen, (self.gridSize*0.5, self.gridSize*(1)*WALL_RADIUS)), wallColor) line(add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(2)*WALL_RADIUS-1)), add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(0.5))), wallColor) # SW quadrant if (not sIsWall) and (not wIsWall): # inner circle circle(screen2, WALL_RADIUS * self.gridSize, wallColor, wallColor, (180,271), 'arc') if (sIsWall) and (not wIsWall): # vertical line line(add(screen, (self.gridSize*(-1)*WALL_RADIUS, 0)), add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(0.5)+1)), wallColor) if (not sIsWall) and (wIsWall): # horizontal line line(add(screen, (0, self.gridSize*(1)*WALL_RADIUS)), add(screen, (self.gridSize*(-0.5)-1, self.gridSize*(1)*WALL_RADIUS)), wallColor) if (sIsWall) and (wIsWall) and (not swIsWall): # outer circle circle(add(screen2, (self.gridSize*(-2)*WALL_RADIUS, self.gridSize*(2)*WALL_RADIUS)), WALL_RADIUS * self.gridSize-1, wallColor, wallColor, (0,91), 'arc') line(add(screen, (self.gridSize*(-2)*WALL_RADIUS+1, self.gridSize*(1)*WALL_RADIUS)), add(screen, (self.gridSize*(-0.5), self.gridSize*(1)*WALL_RADIUS)), wallColor) line(add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(2)*WALL_RADIUS-1)), add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(0.5))), wallColor) def isWall(self, x, y, walls): if x < 0 or y < 0: return False if x >= walls.width or y >= walls.height: return False return walls[x][y] def drawFood(self, foodMatrix ): foodImages = [] color = FOOD_COLOR for xNum, x in enumerate(foodMatrix): if self.capture and (xNum * 2) <= foodMatrix.width: color = TEAM_COLORS[0] if self.capture and (xNum * 2) > foodMatrix.width: color = TEAM_COLORS[1] imageRow = [] foodImages.append(imageRow) for yNum, cell in enumerate(x): if cell: # There's food here screen = self.to_screen((xNum, yNum )) dot = circle( screen, FOOD_SIZE * self.gridSize, outlineColor = color, fillColor = color, width = 1) imageRow.append(dot) else: imageRow.append(None) return foodImages def drawCapsules(self, capsules ): capsuleImages = {} for capsule in capsules: ( screen_x, screen_y ) = self.to_screen(capsule) dot = circle( (screen_x, screen_y), CAPSULE_SIZE * self.gridSize, outlineColor = CAPSULE_COLOR, fillColor = CAPSULE_COLOR, width = 1) capsuleImages[capsule] = dot return capsuleImages def removeFood(self, cell, foodImages ): x, y = cell remove_from_screen(foodImages[x][y]) def removeCapsule(self, cell, capsuleImages ): x, y = cell remove_from_screen(capsuleImages[(x, y)]) def drawExpandedCells(self, cells): """ Draws an overlay of expanded grid positions for search agents """ n = float(len(cells)) baseColor = [1.0, 0.0, 0.0] self.clearExpandedCells() self.expandedCells = [] for k, cell in enumerate(cells): screenPos = self.to_screen( cell) cellColor = formatColor(*[(n-k) * c * .5 / n + .25 for c in baseColor]) block = square(screenPos, 0.5 * self.gridSize, color = cellColor, filled = 1, behind=2) self.expandedCells.append(block) if self.frameTime < 0: refresh() def clearExpandedCells(self): if 'expandedCells' in dir(self) and len(self.expandedCells) > 0: for cell in self.expandedCells: remove_from_screen(cell) def updateDistributions(self, distributions): "Draws an agent's belief distributions" # copy all distributions so we don't change their state distributions = map(lambda x: x.copy(), distributions) if self.distributionImages == None: self.drawDistributions(self.previousState) for x in range(len(self.distributionImages)): for y in range(len(self.distributionImages[0])): image = self.distributionImages[x][y] weights = [dist[ (x,y) ] for dist in distributions] if sum(weights) != 0: pass # Fog of war color = [0.0,0.0,0.0] colors = GHOST_VEC_COLORS[1:] # With Pacman if self.capture: colors = GHOST_VEC_COLORS for weight, gcolor in zip(weights, colors): color = [min(1.0, c + 0.95 * g * weight ** .3) for c,g in zip(color, gcolor)] changeColor(image, formatColor(*color)) refresh() class FirstPersonPacmanGraphics(PacmanGraphics): def __init__(self, zoom = 1.0, showGhosts = True, capture = False, frameTime=0): PacmanGraphics.__init__(self, zoom, frameTime=frameTime) self.showGhosts = showGhosts self.capture = capture def initialize(self, state, isBlue = False): self.isBlue = isBlue PacmanGraphics.startGraphics(self, state) # Initialize distribution images walls = state.layout.walls dist = [] self.layout = state.layout # Draw the rest self.distributionImages = None # initialize lazily self.drawStaticObjects(state) self.drawAgentObjects(state) # Information self.previousState = state def lookAhead(self, config, state): if config.getDirection() == 'Stop': return else: pass # Draw relevant ghosts allGhosts = state.getGhostStates() visibleGhosts = state.getVisibleGhosts() for i, ghost in enumerate(allGhosts): if ghost in visibleGhosts: self.drawGhost(ghost, i) else: self.currentGhostImages[i] = None def getGhostColor(self, ghost, ghostIndex): return GHOST_COLORS[ghostIndex] def getPosition(self, ghostState): if not self.showGhosts and not ghostState.isPacman and ghostState.getPosition()[1] > 1: return (-1000, -1000) else: return PacmanGraphics.getPosition(self, ghostState) def add(x, y): return (x[0] + y[0], x[1] + y[1]) # Saving graphical output # ----------------------- # Note: to make an animated gif from this postscript output, try the command: # convert -delay 7 -loop 1 -compress lzw -layers optimize frame* out.gif # convert is part of imagemagick (freeware) SAVE_POSTSCRIPT = False POSTSCRIPT_OUTPUT_DIR = 'frames' FRAME_NUMBER = 0 import os def saveFrame(): "Saves the current graphical output as a postscript file" global SAVE_POSTSCRIPT, FRAME_NUMBER, POSTSCRIPT_OUTPUT_DIR if not SAVE_POSTSCRIPT: return if not os.path.exists(POSTSCRIPT_OUTPUT_DIR): os.mkdir(POSTSCRIPT_OUTPUT_DIR) name = os.path.join(POSTSCRIPT_OUTPUT_DIR, 'frame_%08d.ps' % FRAME_NUMBER) FRAME_NUMBER += 1 writePostscript(name) # writes the current canvas
homework_1_search/graphicsUtils.py
# graphicsUtils.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). import sys import math import random import string import time import types import tkinter import os.path _Windows = sys.platform == 'win32' # True if on Win95/98/NT _root_window = None # The root window for graphics output _canvas = None # The canvas which holds graphics _canvas_xs = None # Size of canvas object _canvas_ys = None _canvas_x = None # Current position on canvas _canvas_y = None _canvas_col = None # Current colour (set to black below) _canvas_tsize = 12 _canvas_tserifs = 0 def formatColor(r, g, b): return '#%02x%02x%02x' % (int(r * 255), int(g * 255), int(b * 255)) def colorToVector(color): return list(map(lambda x: int(x, 16) / 256.0, [color[1:3], color[3:5], color[5:7]])) if _Windows: _canvas_tfonts = ['times new roman', 'lucida console'] else: _canvas_tfonts = ['times', 'lucidasans-24'] pass # XXX need defaults here def sleep(secs): global _root_window if _root_window == None: time.sleep(secs) else: _root_window.update_idletasks() _root_window.after(int(1000 * secs), _root_window.quit) _root_window.mainloop() def begin_graphics(width=640, height=480, color=formatColor(0, 0, 0), title=None): global _root_window, _canvas, _canvas_x, _canvas_y, _canvas_xs, _canvas_ys, _bg_color # Check for duplicate call if _root_window is not None: # Lose the window. _root_window.destroy() # Save the canvas size parameters _canvas_xs, _canvas_ys = width - 1, height - 1 _canvas_x, _canvas_y = 0, _canvas_ys _bg_color = color # Create the root window _root_window = tkinter.Tk() _root_window.protocol('WM_DELETE_WINDOW', _destroy_window) _root_window.title(title or 'Graphics Window') _root_window.resizable(0, 0) # Create the canvas object try: _canvas = tkinter.Canvas(_root_window, width=width, height=height) _canvas.pack() draw_background() _canvas.update() except: _root_window = None raise # Bind to key-down and key-up events _root_window.bind( "<KeyPress>", _keypress ) _root_window.bind( "<KeyRelease>", _keyrelease ) _root_window.bind( "<FocusIn>", _clear_keys ) _root_window.bind( "<FocusOut>", _clear_keys ) _root_window.bind( "<Button-1>", _leftclick ) _root_window.bind( "<Button-2>", _rightclick ) _root_window.bind( "<Button-3>", _rightclick ) _root_window.bind( "<Control-Button-1>", _ctrl_leftclick) _clear_keys() _leftclick_loc = None _rightclick_loc = None _ctrl_leftclick_loc = None def _leftclick(event): global _leftclick_loc _leftclick_loc = (event.x, event.y) def _rightclick(event): global _rightclick_loc _rightclick_loc = (event.x, event.y) def _ctrl_leftclick(event): global _ctrl_leftclick_loc _ctrl_leftclick_loc = (event.x, event.y) def wait_for_click(): while True: global _leftclick_loc global _rightclick_loc global _ctrl_leftclick_loc if _leftclick_loc != None: val = _leftclick_loc _leftclick_loc = None return val, 'left' if _rightclick_loc != None: val = _rightclick_loc _rightclick_loc = None return val, 'right' if _ctrl_leftclick_loc != None: val = _ctrl_leftclick_loc _ctrl_leftclick_loc = None return val, 'ctrl_left' sleep(0.05) def draw_background(): corners = [(0,0), (0, _canvas_ys), (_canvas_xs, _canvas_ys), (_canvas_xs, 0)] polygon(corners, _bg_color, fillColor=_bg_color, filled=True, smoothed=False) def _destroy_window(event=None): sys.exit(0) # global _root_window # _root_window.destroy() # _root_window = None #print("DESTROY") def end_graphics(): global _root_window, _canvas, _mouse_enabled try: try: sleep(1) if _root_window != None: _root_window.destroy() except SystemExit as e: print('Ending graphics raised an exception:', e) finally: _root_window = None _canvas = None _mouse_enabled = 0 _clear_keys() def clear_screen(background=None): global _canvas_x, _canvas_y _canvas.delete('all') draw_background() _canvas_x, _canvas_y = 0, _canvas_ys def polygon(coords, outlineColor, fillColor=None, filled=1, smoothed=1, behind=0, width=1): c = [] for coord in coords: c.append(coord[0]) c.append(coord[1]) if fillColor == None: fillColor = outlineColor if filled == 0: fillColor = "" poly = _canvas.create_polygon(c, outline=outlineColor, fill=fillColor, smooth=smoothed, width=width) if behind > 0: _canvas.tag_lower(poly, behind) # Higher should be more visible return poly def square(pos, r, color, filled=1, behind=0): x, y = pos coords = [(x - r, y - r), (x + r, y - r), (x + r, y + r), (x - r, y + r)] return polygon(coords, color, color, filled, 0, behind=behind) def circle(pos, r, outlineColor, fillColor=None, endpoints=None, style='pieslice', width=2): x, y = pos x0, x1 = x - r - 1, x + r y0, y1 = y - r - 1, y + r if endpoints == None: e = [0, 359] else: e = list(endpoints) while e[0] > e[1]: e[1] = e[1] + 360 return _canvas.create_arc(x0, y0, x1, y1, outline=outlineColor, fill=fillColor or outlineColor, extent=e[1] - e[0], start=e[0], style=style, width=width) def image(pos, file="../../blueghost.gif"): x, y = pos # img = PhotoImage(file=file) return _canvas.create_image(x, y, image = tkinter.PhotoImage(file=file), anchor = tkinter.NW) def refresh(): _canvas.update_idletasks() def moveCircle(id, pos, r, endpoints=None): global _canvas_x, _canvas_y x, y = pos # x0, x1 = x - r, x + r + 1 # y0, y1 = y - r, y + r + 1 x0, x1 = x - r - 1, x + r y0, y1 = y - r - 1, y + r if endpoints == None: e = [0, 359] else: e = list(endpoints) while e[0] > e[1]: e[1] = e[1] + 360 if os.path.isfile('flag'): edit(id, ('extent', e[1] - e[0])) else: edit(id, ('start', e[0]), ('extent', e[1] - e[0])) move_to(id, x0, y0) def edit(id, *args): _canvas.itemconfigure(id, **dict(args)) def text(pos, color, contents, font='Helvetica', size=12, style='normal', anchor="nw"): global _canvas_x, _canvas_y x, y = pos font = (font, str(size), style) return _canvas.create_text(x, y, fill=color, text=contents, font=font, anchor=anchor) def changeText(id, newText, font=None, size=12, style='normal'): _canvas.itemconfigure(id, text=newText) if font != None: _canvas.itemconfigure(id, font=(font, '-%d' % size, style)) def changeColor(id, newColor): _canvas.itemconfigure(id, fill=newColor) def line(here, there, color=formatColor(0, 0, 0), width=2): x0, y0 = here[0], here[1] x1, y1 = there[0], there[1] return _canvas.create_line(x0, y0, x1, y1, fill=color, width=width) ############################################################################## ### Keypress handling ######################################################## ############################################################################## # We bind to key-down and key-up events. _keysdown = {} _keyswaiting = {} # This holds an unprocessed key release. We delay key releases by up to # one call to keys_pressed() to get round a problem with auto repeat. _got_release = None def _keypress(event): global _got_release #remap_arrows(event) _keysdown[event.keysym] = 1 _keyswaiting[event.keysym] = 1 # print(event.char, event.keycode) _got_release = None def _keyrelease(event): global _got_release #remap_arrows(event) try: del _keysdown[event.keysym] except: pass _got_release = 1 def remap_arrows(event): # TURN ARROW PRESSES INTO LETTERS (SHOULD BE IN KEYBOARD AGENT) if event.char in ['a', 's', 'd', 'w']: return if event.keycode in [37, 101]: # LEFT ARROW (win / x) event.char = 'a' if event.keycode in [38, 99]: # UP ARROW event.char = 'w' if event.keycode in [39, 102]: # RIGHT ARROW event.char = 'd' if event.keycode in [40, 104]: # DOWN ARROW event.char = 's' def _clear_keys(event=None): global _keysdown, _got_release, _keyswaiting _keysdown = {} _keyswaiting = {} _got_release = None def keys_pressed(d_o_e=lambda arg: _root_window.dooneevent(arg), d_w=tkinter._tkinter.DONT_WAIT): d_o_e(d_w) if _got_release: d_o_e(d_w) return _keysdown.keys() def keys_waiting(): global _keyswaiting keys = _keyswaiting.keys() _keyswaiting = {} return keys # Block for a list of keys... def wait_for_keys(): keys = [] while keys == []: keys = keys_pressed() sleep(0.05) return keys def remove_from_screen(x, d_o_e=lambda arg: _root_window.dooneevent(arg), d_w=tkinter._tkinter.DONT_WAIT): _canvas.delete(x) d_o_e(d_w) def _adjust_coords(coord_list, x, y): for i in range(0, len(coord_list), 2): coord_list[i] = coord_list[i] + x coord_list[i + 1] = coord_list[i + 1] + y return coord_list def move_to(object, x, y=None, d_o_e=lambda arg: _root_window.dooneevent(arg), d_w=tkinter._tkinter.DONT_WAIT): if y is None: try: x, y = x except: raise 'incomprehensible coordinates' horiz = True newCoords = [] current_x, current_y = _canvas.coords(object)[0:2] # first point for coord in _canvas.coords(object): if horiz: inc = x - current_x else: inc = y - current_y horiz = not horiz newCoords.append(coord + inc) _canvas.coords(object, *newCoords) d_o_e(d_w) def move_by(object, x, y=None, d_o_e=lambda arg: _root_window.dooneevent(arg), d_w=tkinter._tkinter.DONT_WAIT, lift=False): if y is None: try: x, y = x except: raise Exception('incomprehensible coordinates') horiz = True newCoords = [] for coord in _canvas.coords(object): if horiz: inc = x else: inc = y horiz = not horiz newCoords.append(coord + inc) _canvas.coords(object, *newCoords) d_o_e(d_w) if lift: _canvas.tag_raise(object) def writePostscript(filename): "Writes the current canvas to a postscript file." psfile = open(filename, 'w') psfile.write(_canvas.postscript(pageanchor='sw', y='0.c', x='0.c')) psfile.close() ghost_shape = [ (0, - 0.5), (0.25, - 0.75), (0.5, - 0.5), (0.75, - 0.75), (0.75, 0.5), (0.5, 0.75), (- 0.5, 0.75), (- 0.75, 0.5), (- 0.75, - 0.75), (- 0.5, - 0.5), (- 0.25, - 0.75) ] if __name__ == '__main__': begin_graphics() clear_screen() ghost_shape = [(x * 10 + 20, y * 10 + 20) for x, y in ghost_shape] g = polygon(ghost_shape, formatColor(1, 1, 1)) move_to(g, (50, 50)) circle((150, 150), 20, formatColor(0.7, 0.3, 0.0), endpoints=[15, - 15]) sleep(2)
homework_1_search/keyboardAgents.py
# keyboardAgents.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). from game import Agent from game import Directions import random class KeyboardAgent(Agent): """ An agent controlled by the keyboard. """ # NOTE: Arrow keys also work. WEST_KEY = 'a' EAST_KEY = 'd' NORTH_KEY = 'w' SOUTH_KEY = 's' STOP_KEY = 'q' def __init__( self, index = 0 ): self.lastMove = Directions.STOP self.index = index self.keys = [] def getAction( self, state): from graphicsUtils import keys_waiting from graphicsUtils import keys_pressed keys = list(keys_waiting()) + list(keys_pressed()) if keys != []: self.keys = keys legal = state.getLegalActions(self.index) move = self.getMove(legal) if move == Directions.STOP: # Try to move in the same direction as before if self.lastMove in legal: move = self.lastMove if (self.STOP_KEY in self.keys) and Directions.STOP in legal: move = Directions.STOP if move not in legal: move = random.choice(legal) self.lastMove = move return move def getMove(self, legal): move = Directions.STOP if (self.WEST_KEY in self.keys or 'Left' in self.keys) and Directions.WEST in legal: move = Directions.WEST if (self.EAST_KEY in self.keys or 'Right' in self.keys) and Directions.EAST in legal: move = Directions.EAST if (self.NORTH_KEY in self.keys or 'Up' in self.keys) and Directions.NORTH in legal: move = Directions.NORTH if (self.SOUTH_KEY in self.keys or 'Down' in self.keys) and Directions.SOUTH in legal: move = Directions.SOUTH return move class KeyboardAgent2(KeyboardAgent): """ A second agent controlled by the keyboard. """ # NOTE: Arrow keys also work. WEST_KEY = 'j' EAST_KEY = "l" NORTH_KEY = 'i' SOUTH_KEY = 'k' STOP_KEY = 'u' def getMove(self, legal): move = Directions.STOP if (self.WEST_KEY in self.keys) and Directions.WEST in legal: move = Directions.WEST if (self.EAST_KEY in self.keys) and Directions.EAST in legal: move = Directions.EAST if (self.NORTH_KEY in self.keys) and Directions.NORTH in legal: move = Directions.NORTH if (self.SOUTH_KEY in self.keys) and Directions.SOUTH in legal: move = Directions.SOUTH return move
homework_1_search/layout.py
# layout.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). from util import manhattanDistance from game import Grid import os import random from functools import reduce VISIBILITY_MATRIX_CACHE = {} class Layout: """ A Layout manages the static information about the game board. """ def __init__(self, layoutText): self.width = len(layoutText[0]) self.height= len(layoutText) self.walls = Grid(self.width, self.height, False) self.food = Grid(self.width, self.height, False) self.capsules = [] self.agentPositions = [] self.numGhosts = 0 self.processLayoutText(layoutText) self.layoutText = layoutText self.totalFood = len(self.food.asList()) # self.initializeVisibilityMatrix() def getNumGhosts(self): return self.numGhosts def initializeVisibilityMatrix(self): global VISIBILITY_MATRIX_CACHE if reduce(str.__add__, self.layoutText) not in VISIBILITY_MATRIX_CACHE: from game import Directions vecs = [(-0.5,0), (0.5,0),(0,-0.5),(0,0.5)] dirs = [Directions.NORTH, Directions.SOUTH, Directions.WEST, Directions.EAST] vis = Grid(self.width, self.height, {Directions.NORTH:set(), Directions.SOUTH:set(), Directions.EAST:set(), Directions.WEST:set(), Directions.STOP:set()}) for x in range(self.width): for y in range(self.height): if self.walls[x][y] == False: for vec, direction in zip(vecs, dirs): dx, dy = vec nextx, nexty = x + dx, y + dy while (nextx + nexty) != int(nextx) + int(nexty) or not self.walls[int(nextx)][int(nexty)] : vis[x][y][direction].add((nextx, nexty)) nextx, nexty = x + dx, y + dy self.visibility = vis VISIBILITY_MATRIX_CACHE[reduce(str.__add__, self.layoutText)] = vis else: self.visibility = VISIBILITY_MATRIX_CACHE[reduce(str.__add__, self.layoutText)] def isWall(self, pos): x, col = pos return self.walls[x][col] def getRandomLegalPosition(self): x = random.choice(range(self.width)) y = random.choice(range(self.height)) while self.isWall( (x, y) ): x = random.choice(range(self.width)) y = random.choice(range(self.height)) return (x,y) def getRandomCorner(self): poses = [(1,1), (1, self.height - 2), (self.width - 2, 1), (self.width - 2, self.height - 2)] return random.choice(poses) def getFurthestCorner(self, pacPos): poses = [(1,1), (1, self.height - 2), (self.width - 2, 1), (self.width - 2, self.height - 2)] dist, pos = max([(manhattanDistance(p, pacPos), p) for p in poses]) return pos def isVisibleFrom(self, ghostPos, pacPos, pacDirection): row, col = [int(x) for x in pacPos] return ghostPos in self.visibility[row][col][pacDirection] def __str__(self): return "\n".join(self.layoutText) def deepCopy(self): return Layout(self.layoutText[:]) def processLayoutText(self, layoutText): """ Coordinates are flipped from the input format to the (x,y) convention here The shape of the maze. Each character represents a different type of object. % - Wall . - Food o - Capsule G - Ghost P - Pacman Other characters are ignored. """ maxY = self.height - 1 for y in range(self.height): for x in range(self.width): layoutChar = layoutText[maxY - y][x] self.processLayoutChar(x, y, layoutChar) self.agentPositions.sort() self.agentPositions = [ ( i == 0, pos) for i, pos in self.agentPositions] def processLayoutChar(self, x, y, layoutChar): if layoutChar == '%': self.walls[x][y] = True elif layoutChar == '.': self.food[x][y] = True elif layoutChar == 'o': self.capsules.append((x, y)) elif layoutChar == 'P': self.agentPositions.append( (0, (x, y) ) ) elif layoutChar in ['G']: self.agentPositions.append( (1, (x, y) ) ) self.numGhosts += 1 elif layoutChar in ['1', '2', '3', '4']: self.agentPositions.append( (int(layoutChar), (x,y))) self.numGhosts += 1 def getLayout(name, back = 2): if name.endswith('.lay'): layout = tryToLoad('layouts/' + name) if layout == None: layout = tryToLoad(name) else: layout = tryToLoad('layouts/' + name + '.lay') if layout == None: layout = tryToLoad(name + '.lay') if layout == None and back >= 0: curdir = os.path.abspath('.') os.chdir('..') layout = getLayout(name, back -1) os.chdir(curdir) return layout def tryToLoad(fullname): if(not os.path.exists(fullname)): return None f = open(fullname) try: return Layout([line.strip() for line in f]) finally: f.close()
homework_1_search/layouts/bigCorners.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %. % %.% % %%%%% % %%% %%% %%%%%%% % % % % % % % % % % %%%%% %%%%% %%% % % % %%% %%%%% % %%% % % % % % % % % % % % % % % %%% % % % %%% %%%%% %%% % %%% %%% % % % % % % % % % % %%% %%%%%%%%% %%%%%%% %%% %%% % % % % % % % % % % % % % %%%%% % %%% % % %%% % %%% %%% % % % % % % % % % % % % % % % % % % % %%%%%%% % %%%%%%%%% %%% % %%% % % % % % % % % % % % %%% %%% % %%%%% %%%%% %%% %%% %%%%% % % % % % % % % % % % % % % % % %%% %%% %%% % % % % % % % % % % % %% % % % % % % % % % % % %%%%% % %%% %%% % %%% %%% %%%%% % % % % % % % % % % % % %%% % % % %%% %%% %%%%%%%%% % %%% % % % % % % % % %%% %%%%%%%%%%%%%%%%%%%%% % % %%% % % % % % % % % %%%%% %%% % % % % %%%%%%%%%%%%% % % % % % % % % % % % % % % %%% %%% % % % %%%%%%%%% %%% % % % % % % % % % %P % % % % % % % %%% %%% %%% % %%% % % %%%%% % %%%%% % % % % % % % % %%% % %%%%% %%%%% %%% %%% % %%% % %%% % % % % % % % % % % % % % % % % % %%% % % % % %%%%%%%%% % % % % % % % % % % % % % %%% %%% %%%%%%% %%% %%% %%% % %.% % % % % .% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/bigMaze.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % % % %%%%%%% % %%% % %%% %%% %%%%%%% % % % % % % % % % % %%%%% %%%%% %%% % % % %%% %%%%% % %%% % % % % % % % % % % % % % % % %%% % % % %%% %%%%% %%% % %%% %%% % % % % % % % % % % %%% %%%%%%%%% %%%%%%% %%% %%% % % % % % % % % % % % % % %%%%% % %%% % % %%% % %%% %%% % % % % % % % % % % % % % % % % % % % %%%%%%% % %%%%%%%%% %%% % %%% % % % % % % % % % % % %%% %%% % %%%%% %%%%% %%% %%% %%%%% % % % % % % % % % % % % % % % % % % %%% %%% %%% %%% % % % % % % % % % % % % % % % %%% %%%%%%% % % %%%%% %%% % %%% %%%%% % % % % % % % % % % %%%%% % % %%%%%%%%% %%%%%%%%%%% % %%% % % % % % % % % % % %%% %%%%% %%%%%%%%% %%%%% % % %%% % % % % % % % % % % % %%%%% %%% % % % % %%%%%%%%%%%%% % % % % % % % % % % % % % % %%% %%% % % % %%%%%%%%% %%% % % % % % % % % % % % % % % % % % %%% %%% %%%%% %%% % % %%%%% % %%%%% % % % % % % % % % %%% % %%%%% %%%%% %%% %%% % %%% % %%% % % % % % % % % % % % % % % % % % %%% % % % % %%%%%%%%% % % % % % % % % % % % % % % % % %%% %%% %%%%%%% %%% %%% %%% % %.% % % % % % % % P% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/bigSafeSearch.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %.%.........%% G % o%%%%.....% %.%.%%%%%%%.%%%%%% %%%%%%%.%%.% %............%...%............% %%%%%...%%%.. ..%.%...%.%%% %o%%%.%%%%%.%%%%%%%.%%%.%.%%%%% % ..........Po...%...%. o% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/bigSearch.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %.....%.................%.....% %.%%%.%.%%%.%%%%%%%.%%%.%.....% %.%...%.%......%......%.%.....% %...%%%.%.%%%%.%.%%%%...%%%...% %%%.%.%.%.%......%..%.%...%.%%% %...%.%%%.%.%%% %%%.%.%%%.%...% %.%%%.......% %.......%%%.% %...%.%%%%%.%%%%%%%.%.%%%.%...% %%%.%...%.%....%....%.%...%.%%% %...%%%.%.%%%%.%.%%%%.%.%%%...% %.......%......%......%.....%.% %.....%.%%%.%%%%%%%.%%%.%.%%%.% %.....%........P....%...%.....% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/boxSearch.lay
%%%%%%%%%%%%%% %. . . . . % % % % % %. . . . . %G% % % % %. . . . . % % % % % %. . . . . % % % P %G% %. . . . . % % % % % %. . . . . % % % % % %%%%%%%%%%%%%%
homework_1_search/layouts/capsuleClassic.lay
%%%%%%%%%%%%%%%%%%% %G. G ....% %.% % %%%%%% %.%%.% %.%o% % o% %.o%.% %.%%%.% %%% %..%.% %..... P %..%G% %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/contestClassic.lay
%%%%%%%%%%%%%%%%%%%% %o...%........%...o% %.%%.%.%%..%%.%.%%.% %...... G GG%......% %.%.%%.%% %%%.%%.%.% %.%....% ooo%.%..%.% %.%.%%.% %% %.%.%%.% %o%......P....%....% %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/contoursMaze.lay
%%%%%%%%%%%%%%%%%%%%% % % % % % % % % % P % % % % % % % %. % %%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/greedySearch.lay
%%%%%% %....% % %%.% % %%.% %.P .% %.%%%% %....% %%%%%%
homework_1_search/layouts/mediumClassic.lay
%%%%%%%%%%%%%%%%%%%% %o...%........%....% %.%%.%.%%%%%%.%.%%.% %.%..............%.% %.%.%%.%% %%.%%.%.% %......%G G%......% %.%.%%.%%%%%%.%%.%.% %.%..............%.% %.%%.%.%%%%%%.%.%%.% %....%...P....%...o% %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumCorners.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %. % % % %.% % % % %%%%%% %%%%%%% % % % % % % % % %%%%% %%%%% %%% %% %%%%% % %%% % % % % % % % % % % %%% % % % %%%%%%%% %%% %%% % % % %% % % % % %%% % %%%%%%% %%%% %%% % % % % % % %% % % % % % %%%%% % %%%% % %%% %%% % % % % % % % % %%% % %. %P%%%%% % %%% % .% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumDottedMaze.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%% %%% %%%%%%%% % % %% % % %%% %%% %% ... % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % % %% %% %% ... % % %% % % % % % %%%% %%% %%%%%% % % % % % % % %% %%%%%%%% ... % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% ... % % %%%%%% %%%%%%% %% %%%%%% % %%%%%% % %%%% %% % ... % % %%%%%% %%%%% % %% %% %%%%% % %%%%%% % %%%%% %% % % %%%%%% %%%%%%%%%%% %% %% % %%%%%%%%%% %%%%%% % %. %%%%%%%%%%%%%%%% ...... % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumMaze.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % % %% % % %%%%%%% %% % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % %% %% % % %% % % % % % %%%% %%% %%%%%% % % % % % % % %% %%%%%%%% % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% % % %%%%%% %%%%%%% %% %%%%%% % %%%%%% % %%%% %% % % % %%%%%% %%%%% % %% %% %%%%% % %%%%%% % %%%%% %% % % %%%%%% %%%%%%%%%%% %% %% % %%%%%%%%%% %%%%%% % %. %%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumSafeSearch.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %.% ....%% G %%%%%% o%%.% %.%o%%%%%%%.%%%%%%% %%%%%.% % %%%.%%%%%.%%%%%%%.%%%.%.%%%.% % ..........Po...%.........% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumScaryMaze.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%% %%% %%%%%%%% % % %% % % %%% %%% %%GG % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % % %%GG %% % % %% % % % % % %%%%% %%% %%%%%% % % %% % % % % %% %%%%%%%%% % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% % % %%% %% %%%%%%% %% %%%%%% % %%%%%% % % %% %% % % %%%%%% %% %% %% %% %%%%% % %%%%%% % %%%%% %% % % %%%% %%%%% %%%%%% % %%%%%%%% % %%%%%% % %. %%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumSearch.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %............%%%%%............% %%%.%...%%%.........%.%...%.%%% %...%%%.%.%%%%.%.%%%%%%.%%%...% %.%.....%......%......%.....%.% %.%%%.%%%%%.%%%%%%%.%%%.%.%%%%% %.....%........P....%...%.....% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/minimaxClassic.lay
%%%%%%%%% %.P G% % %.%G%%% %G %%% %%%%%%%%%
homework_1_search/layouts/oddSearch.lay
%%%%%%%%%%%%%%%%%%%% %...%.........%%...% %.%.%.%%%%%%%%%%.%.% %..................% %%%%%%%%.%.%%%%%%%P% %%%%%%%%....... % %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/openClassic.lay
%%%%%%%%%%%%%%%%%%%%%%%%% %.. P .... .... % %.. ... ... ... ... % %.. ... ... ... ... % %.. .... .... G % %.. ... ... ... ... % %.. ... ... ... ... % %.. .... .... o% %%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/openMaze.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %%%%%%%%%%%%%% %%%%%%%%%%%%%%%%% % % % % % % % % % % % % % % % %. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/openSearch.lay
%%%%%%%%%%%%%%%%%%%% %..................% %..................% %........P.........% %..................% %..................% %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/originalClassic.lay
%%%%%%%%%%%%%%%%%%%%%%%%%%%% %............%%............% %.%%%%.%%%%%.%%.%%%%%.%%%%.% %o%%%%.%%%%%.%%.%%%%%.%%%%o% %.%%%%.%%%%%.%%.%%%%%.%%%%.% %..........................% %.%%%%.%%.%%%%%%%%.%%.%%%%.% %.%%%%.%%.%%%%%%%%.%%.%%%%.% %......%%....%%....%%......% %%%%%%.%%%%% %% %%%%%.%%%%%% %%%%%%.%%%%% %% %%%%%.%%%%%% %%%%%%.% %.%%%%%% %%%%%%.% %%%% %%%% %.%%%%%% % . %G GG G% . % %%%%%%.% %%%%%%%%%% %.%%%%%% %%%%%%.% %.%%%%%% %%%%%%.% %%%%%%%%%% %.%%%%%% %............%%............% %.%%%%.%%%%%.%%.%%%%%.%%%%.% %.%%%%.%%%%%.%%.%%%%%.%%%%.% %o..%%....... .......%%..o% %%%.%%.%%.%%%%%%%%.%%.%%.%%% %%%.%%.%%.%%%%%%%%.%%.%%.%%% %......%%....%%....%%......% %.%%%%%%%%%%.%%.%%%%%%%%%%.% %.............P............% %%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/powerClassic.lay
%%%%%%%%%%%%%%%%%%%% %o....o%GGGG%o....o% %..%...%% %%...%..% %.%o.%........%.o%.% %.o%.%.%%%%%%.%.%o.% %........P.........% %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/smallClassic.lay
%%%%%%%%%%%%%%%%%%%% %......%G G%......% %.%%...%% %%...%%.% %.%o.%........%.o%.% %.%%.%.%%%%%%.%.%%.% %........P.........% %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/smallMaze.lay
%%%%%%%%%%%%%%%%%%%%%% % %% % % % % %%%%%% % %%%%%% % %%%%%% P % % % % %%%%%% %% %%%%% % %%%% % % % % %%% %%% % % %%%%%%%%%% %%%%%% % %. %% % %%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/smallSafeSearch.lay
%%%%%%%%% %.. % G % %%% %%%%% % % %%%%%%% % % % % %%%%% % % % % %%%%% % % % %o% % %%%%%%% % .% %%%%%%%.% %Po .% %%%%%%%%%
homework_1_search/layouts/smallSearch.lay
%%%%%%%%%%%%%%%%%%%% %. ...P .% %.%%.%%.%%.%%.%% %.% % %% %..... %.% %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/testClassic.lay
%%%%% % . % %.G.% % . % %. .% % % % .% % % %P .% %%%%%
homework_1_search/layouts/testMaze.lay
%%%%%%%%%% %. P% %%%%%%%%%%
homework_1_search/layouts/testSearch.lay
%%%%% %.P % %%% % %. % %%%%%
homework_1_search/layouts/tinyCorners.lay
%%%%%%%% %. .% % P % % %%%% % % % % % % %%%% %.% .% %%%%%%%%
homework_1_search/layouts/tinyMaze.lay
%%%%%%% % P% % %%% % % % % %% %% %. %%%% %%%%%%%
homework_1_search/layouts/tinySafeSearch.lay
%%%%%%%%% % G %...% %%%%%%% % %Po % %.%%.%%.% %.%%....% %%%%%%%%%
homework_1_search/layouts/tinySearch.lay
%%%%%%%%% %.. ..% %%%%.%% % % P % %.%% %%.% %.%. .% %%%%%%%%%
homework_1_search/layouts/trappedClassic.lay
%%%%%%%% % P G% %G%%%%%% %.... % %%%%%%%%
homework_1_search/layouts/trickyClassic.lay
%%%%%%%%%%%%%%%%%%%% %o...%........%...o% %.%%.%.%%..%%.%.%%.% %.%.....%..%.....%.% %.%.%%.%% %%.%%.%.% %...... GGGG%.%....% %.%....%%%%%%.%..%.% %.%....% oo%.%..%.% %.%....% %%%%.%..%.% %.%...........%..%.% %.%%.%.%%%%%%.%.%%.% %o...%...P....%...o% %%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/trickySearch.lay
%%%%%%%%%%%%%%%%%%%% %. ..% % %.%%.%%.%%.%%.%% % % % P % % %%%%%%%%%%%%%%%%%% % %..... % %%%%%%%%%%%%%%%%%%%%
homework_1_search/pacman.py
# pacman.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). """ Pacman.py holds the logic for the classic pacman game along with the main code to run a game. This file is divided into three sections: (i) Your interface to the pacman world: Pacman is a complex environment. You probably don't want to read through all of the code we wrote to make the game runs correctly. This section contains the parts of the code that you will need to understand in order to complete the project. There is also some code in game.py that you should understand. (ii) The hidden secrets of pacman: This section contains all of the logic code that the pacman environment uses to decide who can move where, who dies when things collide, etc. You shouldn't need to read this section of code, but you can if you want. (iii) Framework to start a game: The final section contains the code for reading the command you use to set up the game, then starting up a new game, along with linking in all the external parts (agent functions, graphics). Check this section out to see all the options available to you. To play your first game, type 'python pacman.py' from the command line. The keys are 'a', 's', 'd', and 'w' to move (or arrow keys). Have fun! """ from game import GameStateData from game import Game from game import Directions from game import Actions from util import nearestPoint from util import manhattanDistance import util, layout import sys, types, time, random, os ################################################### # YOUR INTERFACE TO THE PACMAN WORLD: A GameState # ################################################### class GameState: """ A GameState specifies the full game state, including the food, capsules, agent configurations and score changes. GameStates are used by the Game object to capture the actual state of the game and can be used by agents to reason about the game. Much of the information in a GameState is stored in a GameStateData object. We strongly suggest that you access that data via the accessor methods below rather than referring to the GameStateData object directly. Note that in classic Pacman, Pacman is always agent 0. """ #################################################### # Accessor methods: use these to access state data # #################################################### # static variable keeps track of which states have had getLegalActions called explored = set() def getAndResetExplored(): tmp = GameState.explored.copy() GameState.explored = set() return tmp getAndResetExplored = staticmethod(getAndResetExplored) def getLegalActions( self, agentIndex=0 ): """ Returns the legal actions for the agent specified. """ # GameState.explored.add(self) if self.isWin() or self.isLose(): return [] if agentIndex == 0: # Pacman is moving return PacmanRules.getLegalActions( self ) else: return GhostRules.getLegalActions( self, agentIndex ) def generateSuccessor( self, agentIndex, action): """ Returns the successor state after the specified agent takes the action. """ # Check that successors exist if self.isWin() or self.isLose(): raise Exception('Can\'t generate a successor of a terminal state.') # Copy current state state = GameState(self) # Let agent's logic deal with its action's effects on the board if agentIndex == 0: # Pacman is moving state.data._eaten = [False for i in range(state.getNumAgents())] PacmanRules.applyAction( state, action ) else: # A ghost is moving GhostRules.applyAction( state, action, agentIndex ) # Time passes if agentIndex == 0: state.data.scoreChange += -TIME_PENALTY # Penalty for waiting around else: GhostRules.decrementTimer( state.data.agentStates[agentIndex] ) # Resolve multi-agent effects GhostRules.checkDeath( state, agentIndex ) # Book keeping state.data._agentMoved = agentIndex state.data.score += state.data.scoreChange GameState.explored.add(self) GameState.explored.add(state) return state def getLegalPacmanActions( self ): return self.getLegalActions( 0 ) def generatePacmanSuccessor( self, action ): """ Generates the successor state after the specified pacman move """ return self.generateSuccessor( 0, action ) def getPacmanState( self ): """ Returns an AgentState object for pacman (in game.py) state.pos gives the current position state.direction gives the travel vector """ return self.data.agentStates[0].copy() def getPacmanPosition( self ): return self.data.agentStates[0].getPosition() def getGhostStates( self ): return self.data.agentStates[1:] def getGhostState( self, agentIndex ): if agentIndex == 0 or agentIndex >= self.getNumAgents(): raise Exception("Invalid index passed to getGhostState") return self.data.agentStates[agentIndex] def getGhostPosition( self, agentIndex ): if agentIndex == 0: raise Exception("Pacman's index passed to getGhostPosition") return self.data.agentStates[agentIndex].getPosition() def getGhostPositions(self): return [s.getPosition() for s in self.getGhostStates()] def getNumAgents( self ): return len( self.data.agentStates ) def getScore( self ): return float(self.data.score) def getCapsules(self): """ Returns a list of positions (x,y) of the remaining capsules. """ return self.data.capsules def getNumFood( self ): return self.data.food.count() def getFood(self): """ Returns a Grid of boolean food indicator variables. Grids can be accessed via list notation, so to check if there is food at (x,y), just call currentFood = state.getFood() if currentFood[x][y] == True: ... """ return self.data.food def getWalls(self): """ Returns a Grid of boolean wall indicator variables. Grids can be accessed via list notation, so to check if there is a wall at (x,y), just call walls = state.getWalls() if walls[x][y] == True: ... """ return self.data.layout.walls def hasFood(self, x, y): return self.data.food[x][y] def hasWall(self, x, y): return self.data.layout.walls[x][y] def isLose( self ): return self.data._lose def isWin( self ): return self.data._win ############################################# # Helper methods: # # You shouldn't need to call these directly # ############################################# def __init__( self, prevState = None ): """ Generates a new state by copying information from its predecessor. """ if prevState != None: # Initial state self.data = GameStateData(prevState.data) else: self.data = GameStateData() def deepCopy( self ): state = GameState( self ) state.data = self.data.deepCopy() return state def __eq__( self, other ): """ Allows two states to be compared. """ return hasattr(other, 'data') and self.data == other.data def __hash__( self ): """ Allows states to be keys of dictionaries. """ return hash( self.data ) def __str__( self ): return str(self.data) def initialize( self, layout, numGhostAgents=1000 ): """ Creates an initial game state from a layout array (see layout.py). """ self.data.initialize(layout, numGhostAgents) ############################################################################ # THE HIDDEN SECRETS OF PACMAN # # # # You shouldn't need to look through the code in this section of the file. # ############################################################################ SCARED_TIME = 40 # Moves ghosts are scared COLLISION_TOLERANCE = 0.7 # How close ghosts must be to Pacman to kill TIME_PENALTY = 1 # Number of points lost each round class ClassicGameRules: """ These game rules manage the control flow of a game, deciding when and how the game starts and ends. """ def __init__(self, timeout=30): self.timeout = timeout def newGame( self, layout, pacmanAgent, ghostAgents, display, quiet = False, catchExceptions=False): agents = [pacmanAgent] + ghostAgents[:layout.getNumGhosts()] initState = GameState() initState.initialize( layout, len(ghostAgents) ) game = Game(agents, display, self, catchExceptions=catchExceptions) game.state = initState self.initialState = initState.deepCopy() self.quiet = quiet return game def process(self, state, game): """ Checks to see whether it is time to end the game. """ if state.isWin(): self.win(state, game) if state.isLose(): self.lose(state, game) def win( self, state, game ): if not self.quiet: print("Pacman emerges victorious! Score: %d" % state.data.score) game.gameOver = True def lose( self, state, game ): if not self.quiet: print("Pacman died! Score: %d" % state.data.score) game.gameOver = True def getProgress(self, game): return float(game.state.getNumFood()) / self.initialState.getNumFood() def agentCrash(self, game, agentIndex): if agentIndex == 0: print("Pacman crashed") else: print("A ghost crashed") def getMaxTotalTime(self, agentIndex): return self.timeout def getMaxStartupTime(self, agentIndex): return self.timeout def getMoveWarningTime(self, agentIndex): return self.timeout def getMoveTimeout(self, agentIndex): return self.timeout def getMaxTimeWarnings(self, agentIndex): return 0 class PacmanRules: """ These functions govern how pacman interacts with his environment under the classic game rules. """ PACMAN_SPEED=1 def getLegalActions( state ): """ Returns a list of possible actions. """ return Actions.getPossibleActions( state.getPacmanState().configuration, state.data.layout.walls ) getLegalActions = staticmethod( getLegalActions ) def applyAction( state, action ): """ Edits the state to reflect the results of the action. """ legal = PacmanRules.getLegalActions( state ) if action not in legal: raise Exception("Illegal action " + str(action)) pacmanState = state.data.agentStates[0] # Update Configuration vector = Actions.directionToVector( action, PacmanRules.PACMAN_SPEED ) pacmanState.configuration = pacmanState.configuration.generateSuccessor( vector ) # Eat next = pacmanState.configuration.getPosition() nearest = nearestPoint( next ) if manhattanDistance( nearest, next ) <= 0.5 : # Remove food PacmanRules.consume( nearest, state ) applyAction = staticmethod( applyAction ) def consume( position, state ): x,y = position # Eat food if state.data.food[x][y]: state.data.scoreChange += 10 state.data.food = state.data.food.copy() state.data.food[x][y] = False state.data._foodEaten = position # TODO: cache numFood? numFood = state.getNumFood() if numFood == 0 and not state.data._lose: state.data.scoreChange += 500 state.data._win = True # Eat capsule if( position in state.getCapsules() ): state.data.capsules.remove( position ) state.data._capsuleEaten = position # Reset all ghosts' scared timers for index in range( 1, len( state.data.agentStates ) ): state.data.agentStates[index].scaredTimer = SCARED_TIME consume = staticmethod( consume ) class GhostRules: """ These functions dictate how ghosts interact with their environment. """ GHOST_SPEED=1.0 def getLegalActions( state, ghostIndex ): """ Ghosts cannot stop, and cannot turn around unless they reach a dead end, but can turn 90 degrees at intersections. """ conf = state.getGhostState( ghostIndex ).configuration possibleActions = Actions.getPossibleActions( conf, state.data.layout.walls ) reverse = Actions.reverseDirection( conf.direction ) if Directions.STOP in possibleActions: possibleActions.remove( Directions.STOP ) if reverse in possibleActions and len( possibleActions ) > 1: possibleActions.remove( reverse ) return possibleActions getLegalActions = staticmethod( getLegalActions ) def applyAction( state, action, ghostIndex): legal = GhostRules.getLegalActions( state, ghostIndex ) if action not in legal: raise Exception("Illegal ghost action " + str(action)) ghostState = state.data.agentStates[ghostIndex] speed = GhostRules.GHOST_SPEED if ghostState.scaredTimer > 0: speed /= 2.0 vector = Actions.directionToVector( action, speed ) ghostState.configuration = ghostState.configuration.generateSuccessor( vector ) applyAction = staticmethod( applyAction ) def decrementTimer( ghostState): timer = ghostState.scaredTimer if timer == 1: ghostState.configuration.pos = nearestPoint( ghostState.configuration.pos ) ghostState.scaredTimer = max( 0, timer - 1 ) decrementTimer = staticmethod( decrementTimer ) def checkDeath( state, agentIndex): pacmanPosition = state.getPacmanPosition() if agentIndex == 0: # Pacman just moved; Anyone can kill him for index in range( 1, len( state.data.agentStates ) ): ghostState = state.data.agentStates[index] ghostPosition = ghostState.configuration.getPosition() if GhostRules.canKill( pacmanPosition, ghostPosition ): GhostRules.collide( state, ghostState, index ) else: ghostState = state.data.agentStates[agentIndex] ghostPosition = ghostState.configuration.getPosition() if GhostRules.canKill( pacmanPosition, ghostPosition ): GhostRules.collide( state, ghostState, agentIndex ) checkDeath = staticmethod( checkDeath ) def collide( state, ghostState, agentIndex): if ghostState.scaredTimer > 0: state.data.scoreChange += 200 GhostRules.placeGhost(state, ghostState) ghostState.scaredTimer = 0 # Added for first-person state.data._eaten[agentIndex] = True else: if not state.data._win: state.data.scoreChange -= 500 state.data._lose = True collide = staticmethod( collide ) def canKill( pacmanPosition, ghostPosition ): return manhattanDistance( ghostPosition, pacmanPosition ) <= COLLISION_TOLERANCE canKill = staticmethod( canKill ) def placeGhost(state, ghostState): ghostState.configuration = ghostState.start placeGhost = staticmethod( placeGhost ) ############################# # FRAMEWORK TO START A GAME # ############################# def default(str): return str + ' [Default: %default]' def parseAgentArgs(str): if str == None: return {} pieces = str.split(',') opts = {} for p in pieces: if '=' in p: key, val = p.split('=') else: key,val = p, 1 opts[key] = val return opts def readCommand( argv ): """ Processes the command used to run pacman from the command line. """ from optparse import OptionParser usageStr = """ USAGE: python pacman.py <options> EXAMPLES: (1) python pacman.py - starts an interactive game (2) python pacman.py --layout smallClassic --zoom 2 OR python pacman.py -l smallClassic -z 2 - starts an interactive game on a smaller board, zoomed in """ parser = OptionParser(usageStr) parser.add_option('-n', '--numGames', dest='numGames', type='int', help=default('the number of GAMES to play'), metavar='GAMES', default=1) parser.add_option('-l', '--layout', dest='layout', help=default('the LAYOUT_FILE from which to load the map layout'), metavar='LAYOUT_FILE', default='mediumClassic') parser.add_option('-p', '--pacman', dest='pacman', help=default('the agent TYPE in the pacmanAgents module to use'), metavar='TYPE', default='KeyboardAgent') parser.add_option('-t', '--textGraphics', action='store_true', dest='textGraphics', help='Display output as text only', default=False) parser.add_option('-q', '--quietTextGraphics', action='store_true', dest='quietGraphics', help='Generate minimal output and no graphics', default=False) parser.add_option('-g', '--ghosts', dest='ghost', help=default('the ghost agent TYPE in the ghostAgents module to use'), metavar = 'TYPE', default='RandomGhost') parser.add_option('-k', '--numghosts', type='int', dest='numGhosts', help=default('The maximum number of ghosts to use'), default=4) parser.add_option('-z', '--zoom', type='float', dest='zoom', help=default('Zoom the size of the graphics window'), default=1.0) parser.add_option('-f', '--fixRandomSeed', action='store_true', dest='fixRandomSeed', help='Fixes the random seed to always play the same game', default=False) parser.add_option('-r', '--recordActions', action='store_true', dest='record', help='Writes game histories to a file (named by the time they were played)', default=False) parser.add_option('--replay', dest='gameToReplay', help='A recorded game file (pickle) to replay', default=None) parser.add_option('-a','--agentArgs',dest='agentArgs', help='Comma separated values sent to agent. e.g. "opt1=val1,opt2,opt3=val3"') parser.add_option('-x', '--numTraining', dest='numTraining', type='int', help=default('How many episodes are training (suppresses output)'), default=0) parser.add_option('--frameTime', dest='frameTime', type='float', help=default('Time to delay between frames; <0 means keyboard'), default=0.1) parser.add_option('-c', '--catchExceptions', action='store_true', dest='catchExceptions', help='Turns on exception handling and timeouts during games', default=False) parser.add_option('--timeout', dest='timeout', type='int', help=default('Maximum length of time an agent can spend computing in a single game'), default=30) options, otherjunk = parser.parse_args(argv) if len(otherjunk) != 0: raise Exception('Command line input not understood: ' + str(otherjunk)) args = dict() # Fix the random seed if options.fixRandomSeed: random.seed('cs188') # Choose a layout args['layout'] = layout.getLayout( options.layout ) if args['layout'] == None: raise Exception("The layout " + options.layout + " cannot be found") # Choose a Pacman agent noKeyboard = options.gameToReplay == None and (options.textGraphics or options.quietGraphics) pacmanType = loadAgent(options.pacman, noKeyboard) agentOpts = parseAgentArgs(options.agentArgs) if options.numTraining > 0: args['numTraining'] = options.numTraining if 'numTraining' not in agentOpts: agentOpts['numTraining'] = options.numTraining pacman = pacmanType(**agentOpts) # Instantiate Pacman with agentArgs args['pacman'] = pacman # Don't display training games if 'numTrain' in agentOpts: options.numQuiet = int(agentOpts['numTrain']) options.numIgnore = int(agentOpts['numTrain']) # Choose a ghost agent ghostType = loadAgent(options.ghost, noKeyboard) args['ghosts'] = [ghostType( i+1 ) for i in range( options.numGhosts )] # Choose a display format if options.quietGraphics: import textDisplay args['display'] = textDisplay.NullGraphics() elif options.textGraphics: import textDisplay textDisplay.SLEEP_TIME = options.frameTime args['display'] = textDisplay.PacmanGraphics() else: import graphicsDisplay args['display'] = graphicsDisplay.PacmanGraphics(options.zoom, frameTime = options.frameTime) args['numGames'] = options.numGames args['record'] = options.record args['catchExceptions'] = options.catchExceptions args['timeout'] = options.timeout # Special case: recorded games don't use the runGames method or args structure if options.gameToReplay != None: print('Replaying recorded game %s.' % options.gameToReplay) import pickle f = open(options.gameToReplay, 'rb') try: recorded = pickle.load(f) finally: f.close() recorded['display'] = args['display'] replayGame(**recorded) sys.exit(0) return args def loadAgent(pacman, nographics): # Looks through all pythonPath Directories for the right module, pythonPathStr = os.path.expandvars("$PYTHONPATH") if pythonPathStr.find(';') == -1: pythonPathDirs = pythonPathStr.split(':') else: pythonPathDirs = pythonPathStr.split(';') pythonPathDirs.append('.') for moduleDir in pythonPathDirs: if not os.path.isdir(moduleDir): continue moduleNames = [f for f in os.listdir(moduleDir) if f.endswith('gents.py')] for modulename in moduleNames: try: module = __import__(modulename[:-3]) except ImportError: continue if pacman in dir(module): if nographics and modulename == 'keyboardAgents.py': raise Exception('Using the keyboard requires graphics (not text display)') return getattr(module, pacman) raise Exception('The agent ' + pacman + ' is not specified in any *Agents.py.') def replayGame( layout, actions, display ): import pacmanAgents, ghostAgents rules = ClassicGameRules() agents = [pacmanAgents.GreedyAgent()] + [ghostAgents.RandomGhost(i+1) for i in range(layout.getNumGhosts())] game = rules.newGame( layout, agents[0], agents[1:], display ) state = game.state display.initialize(state.data) for action in actions: # Execute the action state = state.generateSuccessor( *action ) # Change the display display.update( state.data ) # Allow for game specific conditions (winning, losing, etc.) rules.process(state, game) display.finish() def runGames( layout, pacman, ghosts, display, numGames, record, numTraining = 0, catchExceptions=False, timeout=30 ): import __main__ __main__.__dict__['_display'] = display rules = ClassicGameRules(timeout) games = [] for i in range( numGames ): beQuiet = i < numTraining if beQuiet: # Suppress output and graphics import textDisplay gameDisplay = textDisplay.NullGraphics() rules.quiet = True else: gameDisplay = display rules.quiet = False game = rules.newGame( layout, pacman, ghosts, gameDisplay, beQuiet, catchExceptions) game.run() if not beQuiet: games.append(game) if record: import time, pickle fname = ('recorded-game-%d' % (i + 1)) + '-'.join([str(t) for t in time.localtime()[1:6]]) f = open(fname, 'wb') components = {'layout': layout, 'actions': game.moveHistory} pickle.dump(components, f) f.close() if (numGames-numTraining) > 0: scores = [game.state.getScore() for game in games] wins = [game.state.isWin() for game in games] winRate = wins.count(True)/ float(len(wins)) print('Average Score:', sum(scores) / float(len(scores))) print('Scores: ', ', '.join([str(score) for score in scores])) print('Win Rate: %d/%d (%.2f)' % (wins.count(True), len(wins), winRate)) print('Record: ', ', '.join([ ['Loss', 'Win'][int(w)] for w in wins])) return games if __name__ == '__main__': """ The main function called when pacman.py is run from the command line: > python pacman.py See the usage string for more details. > python pacman.py --help """ args = readCommand( sys.argv[1:] ) # Get game components based on input runGames( **args ) # import cProfile # cProfile.run("runGames( **args )") pass
homework_1_search/pacmanAgents.py
# pacmanAgents.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). from pacman import Directions from game import Agent import random import game import util class LeftTurnAgent(game.Agent): "An agent that turns left at every opportunity" def getAction(self, state): legal = state.getLegalPacmanActions() current = state.getPacmanState().configuration.direction if current == Directions.STOP: current = Directions.NORTH left = Directions.LEFT[current] if left in legal: return left if current in legal: return current if Directions.RIGHT[current] in legal: return Directions.RIGHT[current] if Directions.LEFT[left] in legal: return Directions.LEFT[left] return Directions.STOP class GreedyAgent(Agent): def __init__(self, evalFn="scoreEvaluation"): self.evaluationFunction = util.lookup(evalFn, globals()) assert self.evaluationFunction != None def getAction(self, state): # Generate candidate actions legal = state.getLegalPacmanActions() if Directions.STOP in legal: legal.remove(Directions.STOP) successors = [(state.generateSuccessor(0, action), action) for action in legal] scored = [(self.evaluationFunction(state), action) for state, action in successors] bestScore = max(scored)[0] bestActions = [pair[1] for pair in scored if pair[0] == bestScore] return random.choice(bestActions) def scoreEvaluation(state): return state.getScore()
homework_1_search/projectParams.py
# projectParams.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). STUDENT_CODE_DEFAULT = 'searchAgents.py,search.py' PROJECT_TEST_CLASSES = 'searchTestClasses.py' PROJECT_NAME = 'Project 1: Search' BONUS_PIC = False
homework_1_search/search.py
# search.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). """ 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. Your search algorithm needs to return a list of actions that reaches the goal. Make sure to implement a graph search algorithm. 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() def breadthFirstSearch(problem): """Search the shallowest nodes in the search tree first.""" "*** YOUR CODE HERE ***" util.raiseNotDefined() def uniformCostSearch(problem): """Search the node of least total cost first. Important functions to implement 1 - PriorityQueue 2 - problem.getStartState() 3 - problem.isGoalState(xy) 4 - problem.getSuccessors(xy) 5 - problem.getCostOfActions(new_path) """ "*** 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): """Search the node that has the lowest combined cost and heuristic first.""" "*** YOUR CODE HERE ***" # Abbreviations bfs = breadthFirstSearch dfs = depthFirstSearch astar = aStarSearch ucs = uniformCostSearch
homework_1_search/searchAgents.py
# 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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). """ 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 import util 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]: x,y = state dx, dy = Actions.directionToVector(action) nextx, nexty = int(x + dx), int(y + dy) if not self.walls[nextx][nexty]: nextState = (nextx, nexty) cost = self.costFn(nextState) successors.append( ( nextState, action, cost) ) # Bookkeeping for display purposes self._expanded += 1 # DO NOT CHANGE if state not in self._visited: self._visited[state] = True self._visitedlist.append(state) return successors def getCostOfActions(self, actions): """ Returns the cost of a particular sequence of actions. If those actions include an illegal move, return 999999. """ if actions == None: return 999999 x,y= self.getStartState() cost = 0 for action in actions: # Check figure out the next state and see whether its' legal dx, dy = Actions.directionToVector(action) x, y = int(x + dx), int(y + dy) if self.walls[x][y]: return 999999 cost += self.costFn((x,y)) return cost class StayEastSearchAgent(SearchAgent): """ An agent for position search with a cost function that penalizes being in positions on the West side of the board. The cost function for stepping into a position (x,y) is 1/2^x. """ def __init__(self): self.searchFunction = search.uniformCostSearch costFn = lambda pos: .5 ** pos[0] self.searchType = lambda state: PositionSearchProblem(state, costFn, (1, 1), None, False) class StayWestSearchAgent(SearchAgent): """ An agent for position search with a cost function that penalizes being in positions on the East side of the board. The cost function for stepping into a position (x,y) is 2^x. """ def __init__(self): self.searchFunction = search.uniformCostSearch costFn = lambda pos: 2 ** pos[0] self.searchType = lambda state: PositionSearchProblem(state, costFn) def manhattanHeuristic(position, problem, info={}): "The Manhattan distance heuristic for a PositionSearchProblem" xy1 = position xy2 = problem.goal return abs(xy1[0] - xy2[0]) + abs(xy1[1] - xy2[1]) def euclideanHeuristic(position, problem, info={}): "The Euclidean distance heuristic for a PositionSearchProblem" xy1 = position xy2 = problem.goal return ( (xy1[0] - xy2[0]) ** 2 + (xy1[1] - xy2[1]) ** 2 ) ** 0.5 ##################################################### # This portion is incomplete. Time to write code! # ##################################################### class CornersProblem(search.SearchProblem): """ This search problem finds paths through all four corners of a layout. state is represented by a tuple (pos,visited), where pos is the position of pacman and visited is a tuple where vistied[i] = 0 means i^th corner is not yet visited. You can change state space and successor function if required """ def __init__(self, startingGameState): """ Stores the walls, pacman's starting position and corners. """ self.walls = startingGameState.getWalls() self.startingPosition = startingGameState.getPacmanPosition() top, right = self.walls.height-2, self.walls.width-2 self.corners = ((1,1), (1,top), (right, 1), (right, top)) for corner in self.corners: if not startingGameState.hasFood(*corner): print('Warning: no food in corner ' + str(corner)) self._expanded = 0 # DO NOT CHANGE; Number of search nodes expanded # Please add any code here which you would like to use # in initializing the problem def getStartState(self): """ Returns the start state (in your state space, not the full Pacman state space) """ pos = self.startingPosition visited = [0,0,0,0] for i in range(len(self.corners)): if(self.corners[i] == pos): visited[i] = 1 visited = tuple(visited) startState = (pos,visited) return startState def isGoalState(self, state): """ Returns whether this search state is a goal state of the problem. """ if(0 in state[1]): return False; return True; 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]: # Add a successor state to the successor list if the action is legal # Here's a code snippet for figuring out whether a new position hits a wall: x = state[0][0] y = state[0][1] dx, dy = Actions.directionToVector(action) nextx, nexty = int(x + dx), int(y + dy) hitsWall = self.walls[nextx][nexty] if(not hitsWall): next_pos = (nextx,nexty) next_visited = list(state[1]) for i in range(len(self.corners)): if(self.corners[i] == next_pos): next_visited[i] = 1 next_visited = tuple(next_visited) nextState = (next_pos,next_visited) cost = 1 successors.append( ( nextState, action, cost) ) self._expanded += 1 # DO NOT CHANGE return successors def getCostOfActions(self, actions): """ Returns the cost of a particular sequence of actions. If those actions include an illegal move, return 999999. This is implemented for you. """ if actions == None: return 999999 x,y= self.startingPosition for action in actions: dx, dy = Actions.directionToVector(action) x, y = int(x + dx), int(y + dy) if self.walls[x][y]: return 999999 return len(actions) def cornersHeuristic(state, problem): """ A heuristic for the CornersProblem that you defined. state: The current search state (a data structure you chose in your search problem) problem: The CornersProblem instance for this layout. This function should always return a number that is a lower bound on the shortest path from the state to a goal of the problem; i.e. it should be admissible (as well as consistent). """ corners = problem.corners # These are the corner coordinates walls = problem.walls # These are the walls of the maze, as a Grid (game.py) "*** YOUR CODE HERE ***" from util import manhattanDistance # Goal state # if problem.isGoalState(state): return 0 else: distancesFromGoals = [] # Calculate all distances from goals(not visited corners) for index,item in enumerate(state[1]): if item == 0: # Not visited corner # Use manhattan method # distancesFromGoals.append(manhattanDistance(state[0],corners[index])) # Worst case. This guess should be higher than real. Pick higher distance # return max(distancesFromGoals) class AStarCornersAgent(SearchAgent): "A SearchAgent for FoodSearchProblem using A* and your foodHeuristic" def __init__(self): self.searchFunction = lambda prob: search.aStarSearch(prob, cornersHeuristic) self.searchType = CornersProblem class FoodSearchProblem: """ A search problem associated with finding the a path that collects all of the food (dots) in a Pacman game. A search state in this problem is a tuple ( pacmanPosition, foodGrid ) where pacmanPosition: a tuple (x,y) of integers specifying Pacman's position foodGrid: a Grid (see game.py) of either True or False, specifying remaining food """ def __init__(self, startingGameState): self.start = (startingGameState.getPacmanPosition(), startingGameState.getFood()) self.walls = startingGameState.getWalls() self.startingGameState = startingGameState self._expanded = 0 # DO NOT CHANGE self.heuristicInfo = {} # A dictionary for the heuristic to store information def getStartState(self): return self.start def isGoalState(self, state): return state[1].count() == 0 def getSuccessors(self, state): "Returns successor states, the actions they require, and a cost of 1." successors = [] self._expanded += 1 # DO NOT CHANGE for direction in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: x,y = state[0] dx, dy = Actions.directionToVector(direction) nextx, nexty = int(x + dx), int(y + dy) if not self.walls[nextx][nexty]: nextFood = state[1].copy() nextFood[nextx][nexty] = False successors.append( ( ((nextx, nexty), nextFood), direction, 1) ) return successors def getCostOfActions(self, actions): """Returns the cost of a particular sequence of actions. If those actions include an illegal move, return 999999""" x,y= self.getStartState()[0] cost = 0 for action in actions: # figure out the next state and see whether it's legal dx, dy = Actions.directionToVector(action) x, y = int(x + dx), int(y + dy) if self.walls[x][y]: return 999999 cost += 1 return cost class AStarFoodSearchAgent(SearchAgent): "A SearchAgent for FoodSearchProblem using A* and your foodHeuristic" def __init__(self): self.searchFunction = lambda prob: search.aStarSearch(prob, foodHeuristic) self.searchType = FoodSearchProblem def foodHeuristic(state, problem): """ Your heuristic for the FoodSearchProblem goes here. This heuristic must be consistent to ensure correctness. First, try to come up with an admissible heuristic; almost all admissible heuristics will be consistent as well. If using A* ever finds a solution that is worse uniform cost search finds, your heuristic is *not* consistent, and probably not admissible! On the other hand, inadmissible or inconsistent heuristics may find optimal solutions, so be careful. The state is a tuple ( pacmanPosition, foodGrid ) where foodGrid is a Grid (see game.py) of either True or False. You can call foodGrid.asList() to get a list of food coordinates instead. If you want access to info like walls, capsules, etc., you can query the problem. For example, problem.walls gives you a Grid of where the walls are. If you want to *store* information to be reused in other calls to the heuristic, there is a dictionary called problem.heuristicInfo that you can use. For example, if you only want to count the walls once and store that value, try: problem.heuristicInfo['wallCount'] = problem.walls.count() Subsequent calls to this heuristic can access problem.heuristicInfo['wallCount'] """ position, foodGrid = state "*** YOUR CODE HERE ***" return 0 class ClosestDotSearchAgent(SearchAgent): "Search for all food using a sequence of searches" def registerInitialState(self, state): self.actions = [] currentState = state while(currentState.getFood().count() > 0): nextPathSegment = self.findPathToClosestDot(currentState) # The missing piece self.actions += nextPathSegment for action in nextPathSegment: legal = currentState.getLegalActions() if action not in legal: t = (str(action), str(currentState)) raise Exception('findPathToClosestDot returned an illegal move: %s!\n%s' % t) currentState = currentState.generateSuccessor(0, action) self.actionIndex = 0 print('Path found with cost %d.' % len(self.actions)) def findPathToClosestDot(self, gameState): """ Returns a path (a list of actions) to the closest dot, starting from gameState. """ # Here are some useful elements of the startState startPosition = gameState.getPacmanPosition() food = gameState.getFood() walls = gameState.getWalls() problem = AnyFoodSearchProblem(gameState) "*** YOUR CODE HERE ***" util.raiseNotDefined() class AnyFoodSearchProblem(PositionSearchProblem): """ A search problem for finding a path to any food. This search problem is just like the PositionSearchProblem, but has a different goal test, which you need to fill in below. The state space and successor function do not need to be changed. The class definition above, AnyFoodSearchProblem(PositionSearchProblem), inherits the methods of the PositionSearchProblem. You can use this search problem to help you fill in the findPathToClosestDot method. """ def __init__(self, gameState): "Stores information from the gameState. You don't need to change this." # Store the food for later reference self.food = gameState.getFood() # Store info for the PositionSearchProblem (no need to change this) self.walls = gameState.getWalls() self.startState = gameState.getPacmanPosition() self.costFn = lambda x: 1 self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE def isGoalState(self, state): """ The state is Pacman's position. Fill this in with a goal test that will complete the problem definition. """ x,y = state "*** YOUR CODE HERE ***" util.raiseNotDefined() def mazeDistance(point1, point2, gameState): """ Returns the maze distance between any two points, using the search functions you have already built. The gameState can be any game state -- Pacman's position in that state is ignored. Example usage: mazeDistance( (2,4), (5,6), gameState) This might be a useful helper function for your ApproximateSearchAgent. """ x1, y1 = point1 x2, y2 = point2 walls = gameState.getWalls() assert not walls[x1][y1], 'point1 is a wall: ' + str(point1) assert not walls[x2][y2], 'point2 is a wall: ' + str(point2) prob = PositionSearchProblem(gameState, start=point1, goal=point2, warn=False, visualize=False) return len(search.bfs(prob))
homework_1_search/searchTestClasses.py
# searchTestClasses.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). import sys import re import testClasses import textwrap # import project specific code import layout import pacman from search import SearchProblem # helper function for printing solutions in solution files def wrap_solution(solution): if type(solution) == type([]): return '\n'.join(textwrap.wrap(' '.join(solution))) else: return str(solution) def followAction(state, action, problem): for successor1, action1, cost1 in problem.getSuccessors(state): if action == action1: return successor1 return None def followPath(path, problem): state = problem.getStartState() states = [state] for action in path: state = followAction(state, action, problem) states.append(state) return states def checkSolution(problem, path): state = problem.getStartState() for action in path: state = followAction(state, action, problem) return problem.isGoalState(state) # Search problem on a plain graph class GraphSearch(SearchProblem): # Read in the state graph; define start/end states, edges and costs def __init__(self, graph_text): self.expanded_states = [] lines = graph_text.split('\n') r = re.match('start_state:(.*)', lines[0]) if r == None: print("Broken graph:") print('"""%s"""' % graph_text) raise Exception("GraphSearch graph specification start_state not found or incorrect on line 0") self.start_state = r.group(1).strip() r = re.match('goal_states:(.*)', lines[1]) if r == None: print("Broken graph:") print('"""%s"""' % graph_text) raise Exception("GraphSearch graph specification goal_states not found or incorrect on line 1") goals = r.group(1).split() self.goals = [str.strip(g) for g in goals] self.successors = {} all_states = set() self.orderedSuccessorTuples = [] for l in lines[2:]: if len(l.split()) == 3: start, action, next_state = l.split() cost = 1 elif len(l.split()) == 4: start, action, next_state, cost = l.split() else: print("Broken graph:") print('"""%s"""' % graph_text) raise Exception("Invalid line in GraphSearch graph specification on line:" + l) cost = float(cost) self.orderedSuccessorTuples.append((start, action, next_state, cost)) all_states.add(start) all_states.add(next_state) if start not in self.successors: self.successors[start] = [] self.successors[start].append((next_state, action, cost)) for s in all_states: if s not in self.successors: self.successors[s] = [] # Get start state def getStartState(self): return self.start_state # Check if a state is a goal state def isGoalState(self, state): return state in self.goals # Get all successors of a state def getSuccessors(self, state): self.expanded_states.append(state) return list(self.successors[state]) # Calculate total cost of a sequence of actions def getCostOfActions(self, actions): total_cost = 0 state = self.start_state for a in actions: successors = self.successors[state] match = False for (next_state, action, cost) in successors: if a == action: state = next_state total_cost += cost match = True if not match: print('invalid action sequence') sys.exit(1) return total_cost # Return a list of all states on which 'getSuccessors' was called def getExpandedStates(self): return self.expanded_states def __str__(self): print(self.successors) edges = ["%s %s %s %s" % t for t in self.orderedSuccessorTuples] return \ """start_state: %s goal_states: %s %s""" % (self.start_state, " ".join(self.goals), "\n".join(edges)) def parseHeuristic(heuristicText): heuristic = {} for line in heuristicText.split('\n'): tokens = line.split() if len(tokens) != 2: print("Broken heuristic:") print('"""%s"""' % heuristicText) raise Exception("GraphSearch heuristic specification broken at tokens:" + str(tokens)) state, h = tokens heuristic[state] = float(h) def graphHeuristic(state, problem=None): if state in heuristic: return heuristic[state] else: import pprint pp = pprint.PrettyPrinter(indent=4) print("Heuristic:") pp.pprint(heuristic) raise Exception("Graph heuristic called with invalid state: " + str(state)) return graphHeuristic class GraphSearchTest(testClasses.TestCase): def __init__(self, question, testDict): super(GraphSearchTest, self).__init__(question, testDict) self.graph_text = testDict['graph'] self.alg = testDict['algorithm'] self.diagram = testDict['diagram'] self.exactExpansionOrder = testDict.get('exactExpansionOrder', 'True').lower() == "true" if 'heuristic' in testDict: self.heuristic = parseHeuristic(testDict['heuristic']) else: self.heuristic = None # Note that the return type of this function is a tripple: # (solution, expanded states, error message) def getSolInfo(self, search): alg = getattr(search, self.alg) problem = GraphSearch(self.graph_text) if self.heuristic != None: solution = alg(problem, self.heuristic) else: solution = alg(problem) if type(solution) != type([]): return None, None, 'The result of %s must be a list. (Instead, it is %s)' % (self.alg, type(solution)) return solution, problem.getExpandedStates(), None # Run student code. If an error message is returned, print error and return false. # If a good solution is returned, printn the solution and return true; otherwise, # print both the correct and student's solution and return false. def execute(self, grades, moduleDict, solutionDict): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] gold_solution = [str.split(solutionDict['solution']), str.split(solutionDict['rev_solution'])] gold_expanded_states = [str.split(solutionDict['expanded_states']), str.split(solutionDict['rev_expanded_states'])] solution, expanded_states, error = self.getSolInfo(search) if error != None: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('\t%s' % error) return False if solution in gold_solution and (not self.exactExpansionOrder or expanded_states in gold_expanded_states): grades.addMessage('PASS: %s' % self.path) grades.addMessage('\tsolution:\t\t%s' % solution) grades.addMessage('\texpanded_states:\t%s' % expanded_states) return True else: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('\tgraph:') for line in self.diagram.split('\n'): grades.addMessage('\t %s' % (line,)) grades.addMessage('\tstudent solution:\t\t%s' % solution) grades.addMessage('\tstudent expanded_states:\t%s' % expanded_states) grades.addMessage('') grades.addMessage('\tcorrect solution:\t\t%s' % gold_solution[0]) grades.addMessage('\tcorrect expanded_states:\t%s' % gold_expanded_states[0]) grades.addMessage('\tcorrect rev_solution:\t\t%s' % gold_solution[1]) grades.addMessage('\tcorrect rev_expanded_states:\t%s' % gold_expanded_states[1]) return False def writeSolution(self, moduleDict, filePath): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] # open file and write comments handle = open(filePath, 'w') handle.write('# This is the solution file for %s.\n' % self.path) handle.write('# This solution is designed to support both right-to-left\n') handle.write('# and left-to-right implementations.\n') # write forward solution solution, expanded_states, error = self.getSolInfo(search) if error != None: raise Exception("Error in solution code: %s" % error) handle.write('solution: "%s"\n' % ' '.join(solution)) handle.write('expanded_states: "%s"\n' % ' '.join(expanded_states)) # reverse and write backwards solution search.REVERSE_PUSH = not search.REVERSE_PUSH solution, expanded_states, error = self.getSolInfo(search) if error != None: raise Exception("Error in solution code: %s" % error) handle.write('rev_solution: "%s"\n' % ' '.join(solution)) handle.write('rev_expanded_states: "%s"\n' % ' '.join(expanded_states)) # clean up search.REVERSE_PUSH = not search.REVERSE_PUSH handle.close() return True class PacmanSearchTest(testClasses.TestCase): def __init__(self, question, testDict): super(PacmanSearchTest, self).__init__(question, testDict) self.layout_text = testDict['layout'] self.alg = testDict['algorithm'] self.layoutName = testDict['layoutName'] # TODO: sensible to have defaults like this? self.leewayFactor = float(testDict.get('leewayFactor', '1')) self.costFn = eval(testDict.get('costFn', 'None')) self.searchProblemClassName = testDict.get('searchProblemClass', 'PositionSearchProblem') self.heuristicName = testDict.get('heuristic', None) def getSolInfo(self, search, searchAgents): alg = getattr(search, self.alg) lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')]) start_state = pacman.GameState() start_state.initialize(lay, 0) problemClass = getattr(searchAgents, self.searchProblemClassName) problemOptions = {} if self.costFn != None: problemOptions['costFn'] = self.costFn problem = problemClass(start_state, **problemOptions) heuristic = getattr(searchAgents, self.heuristicName) if self.heuristicName != None else None if heuristic != None: solution = alg(problem, heuristic) else: solution = alg(problem) if type(solution) != type([]): return None, None, 'The result of %s must be a list. (Instead, it is %s)' % (self.alg, type(solution)) from game import Directions dirs = Directions.LEFT.keys() if [el in dirs for el in solution].count(False) != 0: return None, None, 'Output of %s must be a list of actions from game.Directions' % self.alg expanded = problem._expanded return solution, expanded, None def execute(self, grades, moduleDict, solutionDict): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] gold_solution = [str.split(solutionDict['solution']), str.split(solutionDict['rev_solution'])] gold_expanded = max(int(solutionDict['expanded_nodes']), int(solutionDict['rev_expanded_nodes'])) solution, expanded, error = self.getSolInfo(search, searchAgents) if error != None: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('%s' % error) return False # FIXME: do we want to standardize test output format? if solution not in gold_solution: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('Solution not correct.') grades.addMessage('\tstudent solution length: %s' % len(solution)) grades.addMessage('\tstudent solution:\n%s' % wrap_solution(solution)) grades.addMessage('') grades.addMessage('\tcorrect solution length: %s' % len(gold_solution[0])) grades.addMessage('\tcorrect (reversed) solution length: %s' % len(gold_solution[1])) grades.addMessage('\tcorrect solution:\n%s' % wrap_solution(gold_solution[0])) grades.addMessage('\tcorrect (reversed) solution:\n%s' % wrap_solution(gold_solution[1])) return False if expanded > self.leewayFactor * gold_expanded and expanded > gold_expanded + 1: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('Too many node expanded; are you expanding nodes twice?') grades.addMessage('\tstudent nodes expanded: %s' % expanded) grades.addMessage('') grades.addMessage('\tcorrect nodes expanded: %s (leewayFactor %s)' % (gold_expanded, self.leewayFactor)) return False grades.addMessage('PASS: %s' % self.path) grades.addMessage('\tpacman layout:\t\t%s' % self.layoutName) grades.addMessage('\tsolution length: %s' % len(solution)) grades.addMessage('\tnodes expanded:\t\t%s' % expanded) return True def writeSolution(self, moduleDict, filePath): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] # open file and write comments handle = open(filePath, 'w') handle.write('# This is the solution file for %s.\n' % self.path) handle.write('# This solution is designed to support both right-to-left\n') handle.write('# and left-to-right implementations.\n') handle.write('# Number of nodes expanded must be with a factor of %s of the numbers below.\n' % self.leewayFactor) # write forward solution solution, expanded, error = self.getSolInfo(search, searchAgents) if error != None: raise Exception("Error in solution code: %s" % error) handle.write('solution: """\n%s\n"""\n' % wrap_solution(solution)) handle.write('expanded_nodes: "%s"\n' % expanded) # write backward solution search.REVERSE_PUSH = not search.REVERSE_PUSH solution, expanded, error = self.getSolInfo(search, searchAgents) if error != None: raise Exception("Error in solution code: %s" % error) handle.write('rev_solution: """\n%s\n"""\n' % wrap_solution(solution)) handle.write('rev_expanded_nodes: "%s"\n' % expanded) # clean up search.REVERSE_PUSH = not search.REVERSE_PUSH handle.close() return True from game import Actions def getStatesFromPath(start, path): "Returns the list of states visited along the path" vis = [start] curr = start for a in path: x,y = curr dx, dy = Actions.directionToVector(a) curr = (int(x + dx), int(y + dy)) vis.append(curr) return vis class CornerProblemTest(testClasses.TestCase): def __init__(self, question, testDict): super(CornerProblemTest, self).__init__(question, testDict) self.layoutText = testDict['layout'] self.layoutName = testDict['layoutName'] def solution(self, search, searchAgents): lay = layout.Layout([l.strip() for l in self.layoutText.split('\n')]) gameState = pacman.GameState() gameState.initialize(lay, 0) problem = searchAgents.CornersProblem(gameState) path = search.bfs(problem) gameState = pacman.GameState() gameState.initialize(lay, 0) visited = getStatesFromPath(gameState.getPacmanPosition(), path) top, right = gameState.getWalls().height-2, gameState.getWalls().width-2 missedCorners = [p for p in ((1,1), (1,top), (right, 1), (right, top)) if p not in visited] return path, missedCorners def execute(self, grades, moduleDict, solutionDict): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] gold_length = int(solutionDict['solution_length']) solution, missedCorners = self.solution(search, searchAgents) if type(solution) != type([]): grades.addMessage('FAIL: %s' % self.path) grades.addMessage('The result must be a list. (Instead, it is %s)' % type(solution)) return False if len(missedCorners) != 0: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('Corners missed: %s' % missedCorners) return False if len(solution) != gold_length: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('Optimal solution not found.') grades.addMessage('\tstudent solution length:\n%s' % len(solution)) grades.addMessage('') grades.addMessage('\tcorrect solution length:\n%s' % gold_length) return False grades.addMessage('PASS: %s' % self.path) grades.addMessage('\tpacman layout:\t\t%s' % self.layoutName) grades.addMessage('\tsolution length:\t\t%s' % len(solution)) return True def writeSolution(self, moduleDict, filePath): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] # open file and write comments handle = open(filePath, 'w') handle.write('# This is the solution file for %s.\n' % self.path) print("Solving problem", self.layoutName) print(self.layoutText) path, _ = self.solution(search, searchAgents) length = len(path) print("Problem solved") handle.write('solution_length: "%s"\n' % length) handle.close() # template = """class: "HeuristicTest" # # heuristic: "foodHeuristic" # searchProblemClass: "FoodSearchProblem" # layoutName: "Test %s" # layout: \"\"\" # %s # \"\"\" # """ # # for i, (_, _, l) in enumerate(doneTests + foodTests): # f = open("food_heuristic_%s.test" % (i+1), "w") # f.write(template % (i+1, "\n".join(l))) # f.close() class HeuristicTest(testClasses.TestCase): def __init__(self, question, testDict): super(HeuristicTest, self).__init__(question, testDict) self.layoutText = testDict['layout'] self.layoutName = testDict['layoutName'] self.searchProblemClassName = testDict['searchProblemClass'] self.heuristicName = testDict['heuristic'] def setupProblem(self, searchAgents): lay = layout.Layout([l.strip() for l in self.layoutText.split('\n')]) gameState = pacman.GameState() gameState.initialize(lay, 0) problemClass = getattr(searchAgents, self.searchProblemClassName) problem = problemClass(gameState) state = problem.getStartState() heuristic = getattr(searchAgents, self.heuristicName) return problem, state, heuristic def checkHeuristic(self, heuristic, problem, state, solutionCost): h0 = heuristic(state, problem) if solutionCost == 0: if h0 == 0: return True, '' else: return False, 'Heuristic failed H(goal) == 0 test' if h0 < 0: return False, 'Heuristic failed H >= 0 test' if not h0 > 0: return False, 'Heuristic failed non-triviality test' if not h0 <= solutionCost: return False, 'Heuristic failed admissibility test' for succ, action, stepCost in problem.getSuccessors(state): h1 = heuristic(succ, problem) if h1 < 0: return False, 'Heuristic failed H >= 0 test' if h0 - h1 > stepCost: return False, 'Heuristic failed consistency test' return True, '' def execute(self, grades, moduleDict, solutionDict): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] solutionCost = int(solutionDict['solution_cost']) problem, state, heuristic = self.setupProblem(searchAgents) passed, message = self.checkHeuristic(heuristic, problem, state, solutionCost) if not passed: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('%s' % message) return False else: grades.addMessage('PASS: %s' % self.path) return True def writeSolution(self, moduleDict, filePath): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] # open file and write comments handle = open(filePath, 'w') handle.write('# This is the solution file for %s.\n' % self.path) print("Solving problem", self.layoutName, self.heuristicName) print(self.layoutText) problem, _, heuristic = self.setupProblem(searchAgents) path = search.astar(problem, heuristic) cost = problem.getCostOfActions(path) print("Problem solved") handle.write('solution_cost: "%s"\n' % cost) handle.close() return True class HeuristicGrade(testClasses.TestCase): def __init__(self, question, testDict): super(HeuristicGrade, self).__init__(question, testDict) self.layoutText = testDict['layout'] self.layoutName = testDict['layoutName'] self.searchProblemClassName = testDict['searchProblemClass'] self.heuristicName = testDict['heuristic'] self.basePoints = int(testDict['basePoints']) self.thresholds = [int(t) for t in testDict['gradingThresholds'].split()] def setupProblem(self, searchAgents): lay = layout.Layout([l.strip() for l in self.layoutText.split('\n')]) gameState = pacman.GameState() gameState.initialize(lay, 0) problemClass = getattr(searchAgents, self.searchProblemClassName) problem = problemClass(gameState) state = problem.getStartState() heuristic = getattr(searchAgents, self.heuristicName) return problem, state, heuristic def execute(self, grades, moduleDict, solutionDict): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] problem, _, heuristic = self.setupProblem(searchAgents) path = search.astar(problem, heuristic) expanded = problem._expanded if not checkSolution(problem, path): grades.addMessage('FAIL: %s' % self.path) grades.addMessage('\tReturned path is not a solution.') grades.addMessage('\tpath returned by astar: %s' % expanded) return False grades.addPoints(self.basePoints) points = 0 for threshold in self.thresholds: if expanded <= threshold: points += 1 grades.addPoints(points) if points >= len(self.thresholds): grades.addMessage('PASS: %s' % self.path) else: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('\texpanded nodes: %s' % expanded) grades.addMessage('\tthresholds: %s' % self.thresholds) return True def writeSolution(self, moduleDict, filePath): handle = open(filePath, 'w') handle.write('# This is the solution file for %s.\n' % self.path) handle.write('# File intentionally blank.\n') handle.close() return True # template = """class: "ClosestDotTest" # # layoutName: "Test %s" # layout: \"\"\" # %s # \"\"\" # """ # # for i, (_, _, l) in enumerate(foodTests): # f = open("closest_dot_%s.test" % (i+1), "w") # f.write(template % (i+1, "\n".join(l))) # f.close() class ClosestDotTest(testClasses.TestCase): def __init__(self, question, testDict): super(ClosestDotTest, self).__init__(question, testDict) self.layoutText = testDict['layout'] self.layoutName = testDict['layoutName'] def solution(self, searchAgents): lay = layout.Layout([l.strip() for l in self.layoutText.split('\n')]) gameState = pacman.GameState() gameState.initialize(lay, 0) path = searchAgents.ClosestDotSearchAgent().findPathToClosestDot(gameState) return path def execute(self, grades, moduleDict, solutionDict): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] gold_length = int(solutionDict['solution_length']) solution = self.solution(searchAgents) if type(solution) != type([]): grades.addMessage('FAIL: %s' % self.path) grades.addMessage('\tThe result must be a list. (Instead, it is %s)' % type(solution)) return False if len(solution) != gold_length: grades.addMessage('FAIL: %s' % self.path) grades.addMessage('Closest dot not found.') grades.addMessage('\tstudent solution length:\n%s' % len(solution)) grades.addMessage('') grades.addMessage('\tcorrect solution length:\n%s' % gold_length) return False grades.addMessage('PASS: %s' % self.path) grades.addMessage('\tpacman layout:\t\t%s' % self.layoutName) grades.addMessage('\tsolution length:\t\t%s' % len(solution)) return True def writeSolution(self, moduleDict, filePath): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] # open file and write comments handle = open(filePath, 'w') handle.write('# This is the solution file for %s.\n' % self.path) print("Solving problem", self.layoutName) print(self.layoutText) length = len(self.solution(searchAgents)) print("Problem solved") handle.write('solution_length: "%s"\n' % length) handle.close() return True class CornerHeuristicSanity(testClasses.TestCase): def __init__(self, question, testDict): super(CornerHeuristicSanity, self).__init__(question, testDict) self.layout_text = testDict['layout'] def execute(self, grades, moduleDict, solutionDict): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] game_state = pacman.GameState() lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')]) game_state.initialize(lay, 0) problem = searchAgents.CornersProblem(game_state) start_state = problem.getStartState() h0 = searchAgents.cornersHeuristic(start_state, problem) succs = problem.getSuccessors(start_state) # cornerConsistencyA for succ in succs: h1 = searchAgents.cornersHeuristic(succ[0], problem) if h0 - h1 > 1: grades.addMessage('FAIL: inconsistent heuristic') return False heuristic_cost = searchAgents.cornersHeuristic(start_state, problem) true_cost = float(solutionDict['cost']) # cornerNontrivial if heuristic_cost == 0: grades.addMessage('FAIL: must use non-trivial heuristic') return False # cornerAdmissible if heuristic_cost > true_cost: grades.addMessage('FAIL: Inadmissible heuristic') return False path = solutionDict['path'].split() states = followPath(path, problem) heuristics = [] for state in states: heuristics.append(searchAgents.cornersHeuristic(state, problem)) for i in range(0, len(heuristics) - 1): h0 = heuristics[i] h1 = heuristics[i+1] # cornerConsistencyB if h0 - h1 > 1: grades.addMessage('FAIL: inconsistent heuristic') return False # cornerPosH if h0 < 0 or h1 <0: grades.addMessage('FAIL: non-positive heuristic') return False # cornerGoalH if heuristics[len(heuristics) - 1] != 0: grades.addMessage('FAIL: heuristic non-zero at goal') return False grades.addMessage('PASS: heuristic value less than true cost at start state') return True def writeSolution(self, moduleDict, filePath): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] # write comment handle = open(filePath, 'w') handle.write('# In order for a heuristic to be admissible, the value\n') handle.write('# of the heuristic must be less at each state than the\n') handle.write('# true cost of the optimal path from that state to a goal.\n') # solve problem and write solution lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')]) start_state = pacman.GameState() start_state.initialize(lay, 0) problem = searchAgents.CornersProblem(start_state) solution = search.astar(problem, searchAgents.cornersHeuristic) handle.write('cost: "%d"\n' % len(solution)) handle.write('path: """\n%s\n"""\n' % wrap_solution(solution)) handle.close() return True class CornerHeuristicPacman(testClasses.TestCase): def __init__(self, question, testDict): super(CornerHeuristicPacman, self).__init__(question, testDict) self.layout_text = testDict['layout'] def execute(self, grades, moduleDict, solutionDict): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] total = 0 true_cost = float(solutionDict['cost']) thresholds = [int(x) for x in solutionDict['thresholds'].split()] game_state = pacman.GameState() lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')]) game_state.initialize(lay, 0) problem = searchAgents.CornersProblem(game_state) start_state = problem.getStartState() if searchAgents.cornersHeuristic(start_state, problem) > true_cost: grades.addMessage('FAIL: Inadmissible heuristic') return False path = search.astar(problem, searchAgents.cornersHeuristic) print("path:", path) print("path length:", len(path)) cost = problem.getCostOfActions(path) if cost > true_cost: grades.addMessage('FAIL: Inconsistent heuristic') return False expanded = problem._expanded points = 0 for threshold in thresholds: if expanded <= threshold: points += 1 grades.addPoints(points) if points >= len(thresholds): grades.addMessage('PASS: Heuristic resulted in expansion of %d nodes' % expanded) else: grades.addMessage('FAIL: Heuristic resulted in expansion of %d nodes' % expanded) return True def writeSolution(self, moduleDict, filePath): search = moduleDict['search'] searchAgents = moduleDict['searchAgents'] # write comment handle = open(filePath, 'w') handle.write('# This solution file specifies the length of the optimal path\n') handle.write('# as well as the thresholds on number of nodes expanded to be\n') handle.write('# used in scoring.\n') # solve problem and write solution lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')]) start_state = pacman.GameState() start_state.initialize(lay, 0) problem = searchAgents.CornersProblem(start_state) solution = search.astar(problem, searchAgents.cornersHeuristic) handle.write('cost: "%d"\n' % len(solution)) handle.write('path: """\n%s\n"""\n' % wrap_solution(solution)) handle.write('thresholds: "2000 1600 1200"\n') handle.close() return True
homework_1_search/testClasses.py
# testClasses.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). # import modules from python standard library import inspect import re import sys # Class which models a question in a project. Note that questions have a # maximum number of points they are worth, and are composed of a series of # test cases class Question(object): def raiseNotDefined(self): print('Method not implemented: %s' % inspect.stack()[1][3]) sys.exit(1) def __init__(self, questionDict, display): self.maxPoints = int(questionDict['max_points']) self.testCases = [] self.display = display def getDisplay(self): return self.display def getMaxPoints(self): return self.maxPoints # Note that 'thunk' must be a function which accepts a single argument, # namely a 'grading' object def addTestCase(self, testCase, thunk): self.testCases.append((testCase, thunk)) def execute(self, grades): self.raiseNotDefined() # Question in which all test cases must be passed in order to receive credit class PassAllTestsQuestion(Question): def execute(self, grades): # TODO: is this the right way to use grades? The autograder doesn't seem to use it. testsFailed = False grades.assignZeroCredit() for _, f in self.testCases: if not f(grades): testsFailed = True if testsFailed: grades.fail("Tests failed.") else: grades.assignFullCredit() class ExtraCreditPassAllTestsQuestion(Question): def __init__(self, questionDict, display): Question.__init__(self, questionDict, display) self.extraPoints = int(questionDict['extra_points']) def execute(self, grades): # TODO: is this the right way to use grades? The autograder doesn't seem to use it. testsFailed = False grades.assignZeroCredit() for _, f in self.testCases: if not f(grades): testsFailed = True if testsFailed: grades.fail("Tests failed.") else: grades.assignFullCredit() grades.addPoints(self.extraPoints) # Question in which predict credit is given for test cases with a ``points'' property. # All other tests are mandatory and must be passed. class HackedPartialCreditQuestion(Question): def execute(self, grades): # TODO: is this the right way to use grades? The autograder doesn't seem to use it. grades.assignZeroCredit() points = 0 passed = True for testCase, f in self.testCases: testResult = f(grades) if "points" in testCase.testDict: if testResult: points += float(testCase.testDict["points"]) else: passed = passed and testResult ## FIXME: Below terrible hack to match q3's logic if int(points) == self.maxPoints and not passed: grades.assignZeroCredit() else: grades.addPoints(int(points)) class Q6PartialCreditQuestion(Question): """Fails any test which returns False, otherwise doesn't effect the grades object. Partial credit tests will add the required points.""" def execute(self, grades): grades.assignZeroCredit() results = [] for _, f in self.testCases: results.append(f(grades)) if False in results: grades.assignZeroCredit() class PartialCreditQuestion(Question): """Fails any test which returns False, otherwise doesn't effect the grades object. Partial credit tests will add the required points.""" def execute(self, grades): grades.assignZeroCredit() for _, f in self.testCases: if not f(grades): grades.assignZeroCredit() grades.fail("Tests failed.") return False class NumberPassedQuestion(Question): """Grade is the number of test cases passed.""" def execute(self, grades): grades.addPoints([f(grades) for _, f in self.testCases].count(True)) # Template modeling a generic test case class TestCase(object): def raiseNotDefined(self): print('Method not implemented: %s' % inspect.stack()[1][3]) sys.exit(1) def getPath(self): return self.path def __init__(self, question, testDict): self.question = question self.testDict = testDict self.path = testDict['path'] self.messages = [] def __str__(self): self.raiseNotDefined() def execute(self, grades, moduleDict, solutionDict): self.raiseNotDefined() def writeSolution(self, moduleDict, filePath): self.raiseNotDefined() return True # Tests should call the following messages for grading # to ensure a uniform format for test output. # # TODO: this is hairy, but we need to fix grading.py's interface # to get a nice hierarchical project - question - test structure, # then these should be moved into Question proper. def testPass(self, grades): grades.addMessage('PASS: %s' % (self.path,)) for line in self.messages: grades.addMessage(' %s' % (line,)) return True def testFail(self, grades): grades.addMessage('FAIL: %s' % (self.path,)) for line in self.messages: grades.addMessage(' %s' % (line,)) return False # This should really be question level? # def testPartial(self, grades, points, maxPoints): grades.addPoints(points) extraCredit = max(0, points - maxPoints) regularCredit = points - extraCredit grades.addMessage('%s: %s (%s of %s points)' % ("PASS" if points >= maxPoints else "FAIL", self.path, regularCredit, maxPoints)) if extraCredit > 0: grades.addMessage('EXTRA CREDIT: %s points' % (extraCredit,)) for line in self.messages: grades.addMessage(' %s' % (line,)) return True def addMessage(self, message): self.messages.extend(message.split('\n'))
homework_1_search/testParser.py
# testParser.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). import re import sys class TestParser(object): def __init__(self, path): # save the path to the test file self.path = path def removeComments(self, rawlines): # remove any portion of a line following a '#' symbol fixed_lines = [] for l in rawlines: idx = l.find('#') if idx == -1: fixed_lines.append(l) else: fixed_lines.append(l[0:idx]) return '\n'.join(fixed_lines) def parse(self): # read in the test case and remove comments test = {} with open(self.path) as handle: raw_lines = handle.read().split('\n') test_text = self.removeComments(raw_lines) test['__raw_lines__'] = raw_lines test['path'] = self.path test['__emit__'] = [] lines = test_text.split('\n') i = 0 # read a property in each loop cycle while(i < len(lines)): # skip blank lines if re.match('\A\s*\Z', lines[i]): test['__emit__'].append(("raw", raw_lines[i])) i += 1 continue m = re.match('\A([^"]*?):\s*"([^"]*)"\s*\Z', lines[i]) if m: test[m.group(1)] = m.group(2) test['__emit__'].append(("oneline", m.group(1))) i += 1 continue m = re.match('\A([^"]*?):\s*"""\s*\Z', lines[i]) if m: msg = [] i += 1 while(not re.match('\A\s*"""\s*\Z', lines[i])): msg.append(raw_lines[i]) i += 1 test[m.group(1)] = '\n'.join(msg) test['__emit__'].append(("multiline", m.group(1))) i += 1 continue print('error parsing test file: %s' % self.path) sys.exit(1) return test def emitTestDict(testDict, handle): for kind, data in testDict['__emit__']: if kind == "raw": handle.write(data + "\n") elif kind == "oneline": handle.write('%s: "%s"\n' % (data, testDict[data])) elif kind == "multiline": handle.write('%s: """\n%s\n"""\n' % (data, testDict[data])) else: raise Exception("Bad __emit__")
homework_1_search/test_cases/CONFIG
order: "q1 q2 q3 q4 q5 q6 q7 q8"
homework_1_search/test_cases/q1/CONFIG
max_points: "3" class: "PassAllTestsQuestion"
homework_1_search/test_cases/q1/graph_backtrack.solution
# This is the solution file for test_cases/q1/graph_backtrack.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->C 0:C->G" expanded_states: "A D C" rev_solution: "1:A->C 0:C->G" rev_expanded_states: "A B C"
homework_1_search/test_cases/q1/graph_backtrack.test
class: "GraphSearchTest" algorithm: "depthFirstSearch" diagram: """ B ^ | *A --> C --> G | V D A is the start state, G is the goal. Arrows mark possible state transitions. This tests whether you extract the sequence of actions correctly even if your search backtracks. If you fail this, your nodes are not correctly tracking the sequences of actions required to reach them. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 A 1:A->C C 2.0 A 2:A->D D 4.0 C 0:C->G G 8.0 """
homework_1_search/test_cases/q1/graph_bfs_vs_dfs.solution
# This is the solution file for test_cases/q1/graph_bfs_vs_dfs.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "2:A->D 0:D->G" expanded_states: "A D" rev_solution: "0:A->B 0:B->D 0:D->G" rev_expanded_states: "A B D"
homework_1_search/test_cases/q1/graph_bfs_vs_dfs.test
# Graph where BFS finds the optimal solution but DFS does not class: "GraphSearchTest" algorithm: "depthFirstSearch" diagram: """ /-- B | ^ | | | *A -->[G] | | ^ | V | \-->D ----/ A is the start state, G is the goal. Arrows mark possible transitions """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 A 1:A->G G 2.0 A 2:A->D D 4.0 B 0:B->D D 8.0 D 0:D->G G 16.0 """
homework_1_search/test_cases/q1/graph_infinite.solution
# This is the solution file for test_cases/q1/graph_infinite.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "0:A->B 1:B->C 1:C->G" expanded_states: "A B C" rev_solution: "0:A->B 1:B->C 1:C->G" rev_expanded_states: "A B C"
homework_1_search/test_cases/q1/graph_infinite.test
# Graph where natural action choice leads to an infinite loop class: "GraphSearchTest" algorithm: "depthFirstSearch" diagram: """ B <--> C ^ /| | / | V / V *A<-/ [G] A is the start state, G is the goal. Arrows mark possible state transitions. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 B 0:B->A A 2.0 B 1:B->C C 4.0 C 0:C->A A 8.0 C 1:C->G G 16.0 C 2:C->B B 32.0 """
homework_1_search/test_cases/q1/graph_manypaths.solution
# This is the solution file for test_cases/q1/graph_manypaths.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "2:A->B2 0:B2->C 0:C->D 2:D->E2 0:E2->F 0:F->G" expanded_states: "A B2 C D E2 F" rev_solution: "0:A->B1 0:B1->C 0:C->D 0:D->E1 0:E1->F 0:F->G" rev_expanded_states: "A B1 C D E1 F"
homework_1_search/test_cases/q1/graph_manypaths.test
class: "GraphSearchTest" algorithm: "depthFirstSearch" diagram: """ B1 E1 ^ \ ^ \ / V / V *A --> C --> D --> F --> [G] \ ^ \ ^ V / V / B2 E2 A is the start state, G is the goal. Arrows mark possible state transitions. This graph has multiple paths to the goal, where nodes with the same state are added to the fringe multiple times before they are expanded. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B1 B1 1.0 A 1:A->C C 2.0 A 2:A->B2 B2 4.0 B1 0:B1->C C 8.0 B2 0:B2->C C 16.0 C 0:C->D D 32.0 D 0:D->E1 E1 64.0 D 1:D->F F 128.0 D 2:D->E2 E2 256.0 E1 0:E1->F F 512.0 E2 0:E2->F F 1024.0 F 0:F->G G 2048.0 """
homework_1_search/test_cases/q1/pacman_1.solution
# This is the solution file for test_cases/q1/pacman_1.test. # This solution is designed to support both right-to-left # and left-to-right implementations. # Number of nodes expanded must be with a factor of 1.0 of the numbers below. solution: """ West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West South South South South South South South South South East East East North North North North North North North East East South South South South South South East East North North North North North North East East South South South South East East North North East East East East East East East East South South South East East East East East East East South South South South South South South West West West West West West West West West West West West West West West West West South West West West West West West West West West """ expanded_nodes: "146" rev_solution: """ South South West West West West South South East East East East South South West West West West South South East East East East South South West West West West South South South East North East East East South South South West West West West West West West North North North North North North North North West West West West West West West North North North East East East East South East East East North North North West West North North West West West West West West West West West West West West West West West West West West West West West West West West South South South South South South South South South East East East North North North North North North North East East South South South South South South East East North North North North North North East East South South South South East East North North North North East East East East East South South West West West South South East East East South South West West West West West West South South West West West West West South West West West West West South South East East East East East East East North East East East East East North North East East East East East East North East East East East East South South West West West South West West West West West West South South West West West West West South West West West West West West West West West """ rev_expanded_nodes: "269"
homework_1_search/test_cases/q1/pacman_1.test
# This is a basic depth first search test class: "PacmanSearchTest" algorithm: "depthFirstSearch" # The following specifies the layout to be used layoutName: "mediumMaze" layout: """ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % % %% % % %%%%%%% %% % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % %% %% % % %% % % % % % %%%% %%% %%%%%% % % % % % % % %% %%%%%%%% % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% % % %%%%%% %%%%%%% %% %%%%%% % %%%%%% % %%%% %% % % % %%%%%% %%%%% % %% %% %%%%% % %%%%%% % %%%%% %% % % %%%%%% %%%%%%%%%%% %% %% % %%%%%%%%%% %%%%%% % %. %%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% """
homework_1_search/test_cases/q2/CONFIG
max_points: "3" class: "PassAllTestsQuestion"
homework_1_search/test_cases/q2/graph_backtrack.solution
# This is the solution file for test_cases/q2/graph_backtrack.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->C 0:C->G" expanded_states: "A B C D" rev_solution: "1:A->C 0:C->G" rev_expanded_states: "A D C B"
homework_1_search/test_cases/q2/graph_backtrack.test
class: "GraphSearchTest" algorithm: "breadthFirstSearch" diagram: """ B ^ | *A --> C --> G | V D A is the start state, G is the goal. Arrows mark possible state transitions. This tests whether you extract the sequence of actions correctly even if your search backtracks. If you fail this, your nodes are not correctly tracking the sequences of actions required to reach them. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 A 1:A->C C 2.0 A 2:A->D D 4.0 C 0:C->G G 8.0 """
homework_1_search/test_cases/q2/graph_bfs_vs_dfs.solution
# This is the solution file for test_cases/q2/graph_bfs_vs_dfs.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->G" expanded_states: "A B" rev_solution: "1:A->G" rev_expanded_states: "A D"
homework_1_search/test_cases/q2/graph_bfs_vs_dfs.test
# Graph where BFS finds the optimal solution but DFS does not class: "GraphSearchTest" algorithm: "breadthFirstSearch" diagram: """ /-- B | ^ | | | *A -->[G] | | ^ | V | \-->D ----/ A is the start state, G is the goal. Arrows mark possible transitions """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 A 1:A->G G 2.0 A 2:A->D D 4.0 B 0:B->D D 8.0 D 0:D->G G 16.0 """
homework_1_search/test_cases/q2/graph_infinite.solution
# This is the solution file for test_cases/q2/graph_infinite.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "0:A->B 1:B->C 1:C->G" expanded_states: "A B C" rev_solution: "0:A->B 1:B->C 1:C->G" rev_expanded_states: "A B C"
homework_1_search/test_cases/q2/graph_infinite.test
# Graph where natural action choice leads to an infinite loop class: "GraphSearchTest" algorithm: "breadthFirstSearch" diagram: """ B <--> C ^ /| | / | V / V *A<-/ [G] A is the start state, G is the goal. Arrows mark possible state transitions. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 B 0:B->A A 2.0 B 1:B->C C 4.0 C 0:C->A A 8.0 C 1:C->G G 16.0 C 2:C->B B 32.0 """
homework_1_search/test_cases/q2/graph_manypaths.solution
# This is the solution file for test_cases/q2/graph_manypaths.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->C 0:C->D 1:D->F 0:F->G" expanded_states: "A B1 C B2 D E1 F E2" rev_solution: "1:A->C 0:C->D 1:D->F 0:F->G" rev_expanded_states: "A B2 C B1 D E2 F E1"
homework_1_search/test_cases/q2/graph_manypaths.test
class: "GraphSearchTest" algorithm: "breadthFirstSearch" diagram: """ B1 E1 ^ \ ^ \ / V / V *A --> C --> D --> F --> [G] \ ^ \ ^ V / V / B2 E2 A is the start state, G is the goal. Arrows mark possible state transitions. This graph has multiple paths to the goal, where nodes with the same state are added to the fringe multiple times before they are expanded. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B1 B1 1.0 A 1:A->C C 2.0 A 2:A->B2 B2 4.0 B1 0:B1->C C 8.0 B2 0:B2->C C 16.0 C 0:C->D D 32.0 D 0:D->E1 E1 64.0 D 1:D->F F 128.0 D 2:D->E2 E2 256.0 E1 0:E1->F F 512.0 E2 0:E2->F F 1024.0 F 0:F->G G 2048.0 """
homework_1_search/test_cases/q2/pacman_1.solution
# This is the solution file for test_cases/q2/pacman_1.test. # This solution is designed to support both right-to-left # and left-to-right implementations. # Number of nodes expanded must be with a factor of 1.0 of the numbers below. solution: """ West West West West West West West West West South South East East South South South West West West North West West West West South South South East East East East East East East South South South South South South South West West West West West West West West West West West West West West West West West South West West West West West West West West West """ expanded_nodes: "269" rev_solution: """ West West West West West West West West West South South East East South South South West West West North West West West West South South South East East East East East East East South South South South South South South West West West West West West West West West West West West West West West West West South West West West West West West West West West """ rev_expanded_nodes: "269"
homework_1_search/test_cases/q2/pacman_1.test
# This is a basic breadth first search test class: "PacmanSearchTest" algorithm: "breadthFirstSearch" # The following specifies the layout to be used layoutName: "mediumMaze" layout: """ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % % %% % % %%%%%%% %% % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % %% %% % % %% % % % % % %%%% %%% %%%%%% % % % % % % % %% %%%%%%%% % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% % % %%%%%% %%%%%%% %% %%%%%% % %%%%%% % %%%% %% % % % %%%%%% %%%%% % %% %% %%%%% % %%%%%% % %%%%% %% % % %%%%%% %%%%%%%%%%% %% %% % %%%%%%%%%% %%%%%% % %. %%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% """
homework_1_search/test_cases/q3/CONFIG
class: "PassAllTestsQuestion" max_points: "3"
homework_1_search/test_cases/q3/graph_backtrack.solution
# This is the solution file for test_cases/q3/graph_backtrack.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->C 0:C->G" expanded_states: "A B C D" rev_solution: "1:A->C 0:C->G" rev_expanded_states: "A B C D"
homework_1_search/test_cases/q3/graph_backtrack.test
class: "GraphSearchTest" algorithm: "uniformCostSearch" diagram: """ B ^ | *A --> C --> G | V D A is the start state, G is the goal. Arrows mark possible state transitions. This tests whether you extract the sequence of actions correctly even if your search backtracks. If you fail this, your nodes are not correctly tracking the sequences of actions required to reach them. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 A 1:A->C C 2.0 A 2:A->D D 4.0 C 0:C->G G 8.0 """
homework_1_search/test_cases/q3/graph_bfs_vs_dfs.solution
# This is the solution file for test_cases/q3/graph_bfs_vs_dfs.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->G" expanded_states: "A B" rev_solution: "1:A->G" rev_expanded_states: "A B"
homework_1_search/test_cases/q3/graph_bfs_vs_dfs.test
# Graph where BFS finds the optimal solution but DFS does not class: "GraphSearchTest" algorithm: "uniformCostSearch" diagram: """ /-- B | ^ | | | *A -->[G] | | ^ | V | \-->D ----/ A is the start state, G is the goal. Arrows mark possible transitions """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 A 1:A->G G 2.0 A 2:A->D D 4.0 B 0:B->D D 8.0 D 0:D->G G 16.0 """
homework_1_search/test_cases/q3/graph_infinite.solution
# This is the solution file for test_cases/q3/graph_infinite.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "0:A->B 1:B->C 1:C->G" expanded_states: "A B C" rev_solution: "0:A->B 1:B->C 1:C->G" rev_expanded_states: "A B C"
homework_1_search/test_cases/q3/graph_infinite.test
# Graph where natural action choice leads to an infinite loop class: "GraphSearchTest" algorithm: "uniformCostSearch" diagram: """ B <--> C ^ /| | / | V / V *A<-/ [G] A is the start state, G is the goal. Arrows mark possible state transitions. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 B 0:B->A A 2.0 B 1:B->C C 4.0 C 0:C->A A 8.0 C 1:C->G G 16.0 C 2:C->B B 32.0 """
homework_1_search/test_cases/q3/graph_manypaths.solution
# This is the solution file for test_cases/q3/graph_manypaths.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->C 0:C->D 1:D->F 0:F->G" expanded_states: "A B1 C B2 D E1 F E2" rev_solution: "1:A->C 0:C->D 1:D->F 0:F->G" rev_expanded_states: "A B1 C B2 D E1 F E2"
homework_1_search/test_cases/q3/graph_manypaths.test
class: "GraphSearchTest" algorithm: "uniformCostSearch" diagram: """ B1 E1 ^ \ ^ \ / V / V *A --> C --> D --> F --> [G] \ ^ \ ^ V / V / B2 E2 A is the start state, G is the goal. Arrows mark possible state transitions. This graph has multiple paths to the goal, where nodes with the same state are added to the fringe multiple times before they are expanded. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B1 B1 1.0 A 1:A->C C 2.0 A 2:A->B2 B2 4.0 B1 0:B1->C C 8.0 B2 0:B2->C C 16.0 C 0:C->D D 32.0 D 0:D->E1 E1 64.0 D 1:D->F F 128.0 D 2:D->E2 E2 256.0 E1 0:E1->F F 512.0 E2 0:E2->F F 1024.0 F 0:F->G G 2048.0 """
homework_1_search/test_cases/q3/ucs_0_graph.solution
# This is the solution file for test_cases/q3/ucs_0_graph.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "Right Down Down" expanded_states: "A B D C G" rev_solution: "Right Down Down" rev_expanded_states: "A B D C G"
homework_1_search/test_cases/q3/ucs_0_graph.test
class: "GraphSearchTest" algorithm: "uniformCostSearch" diagram: """ C ^ | 2 2 V 4 *A <----> B -----> [H] |1 1.5 V 2.5 G <----- D -----> E | 2 | V [F] A is the start state, F and H is the goal. Arrows mark possible state transitions. The number next to the arrow is the cost of that transition. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: H F A Right B 2.0 B Right H 4.0 B Down D 1.0 B Up C 2.0 B Left A 2.0 C Down B 2.0 D Right E 2.5 D Down F 2.0 D Left G 1.5 """
homework_1_search/test_cases/q3/ucs_1_problemC.solution
# This is the solution file for test_cases/q3/ucs_1_problemC.test. # This solution is designed to support both right-to-left # and left-to-right implementations. # Number of nodes expanded must be with a factor of 1.1 of the numbers below. solution: """ West West West West West West West West West South South East East South South South West West West North West West West West South South South East East East East East East East South South South South South South South West West West West West West West West West West West West West West West West West South West West West West West West West West West """ expanded_nodes: "269" rev_solution: """ West West West West West West West West West South South East East South South South West West West North West West West West South South South East East East East East East East South South South South South South South West West West West West West West West West West West West West West West West West South West West West West West West West West West """ rev_expanded_nodes: "269"
homework_1_search/test_cases/q3/ucs_1_problemC.test
class: "PacmanSearchTest" algorithm: "uniformCostSearch" points: "0.5" # The following specifies the layout to be used layoutName: "mediumMaze" layout: """ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % % %% % % %%%%%%% %% % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % %% %% % % %% % % % % % %%%% %%% %%%%%% % % % % % % % %% %%%%%%%% % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% % % %%%%%% %%%%%%% %% %%%%%% % %%%%%% % %%%% %% % % % %%%%%% %%%%% % %% %% %%%%% % %%%%%% % %%%%% %% % % %%%%%% %%%%%%%%%%% %% %% % %%%%%%%%%% %%%%%% % %. %%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% """ leewayFactor: "1.1" #costFn: "lambda pos: 1"
homework_1_search/test_cases/q3/ucs_2_problemE.solution
# This is the solution file for test_cases/q3/ucs_2_problemE.test. # This solution is designed to support both right-to-left # and left-to-right implementations. # Number of nodes expanded must be with a factor of 1.1 of the numbers below. solution: """ South South West West West West South South East East East East South South West West West West South South East East East East South South West West West West South South East East East East South South South West West West West West West West North West West West West West West West West West West West West West West West West West South West West West West West West West West West """ expanded_nodes: "260" rev_solution: """ South South West West West West South South East East East East South South West West West West South South East East East East South South West West West West South South East East East East South South South West West West West West West West North West West West West West West West West West West West West West West West West West South West West West West West West West West West """ rev_expanded_nodes: "260"
homework_1_search/test_cases/q3/ucs_2_problemE.test
class: "PacmanSearchTest" algorithm: "uniformCostSearch" points: "0.5" # The following specifies the layout to be used layoutName: "mediumMaze" layout: """ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % % %% % % %%%%%%% %% % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % %% %% % % %% % % % % % %%%% %%% %%%%%% % % % % % % % %% %%%%%%%% % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% % % %%%%%% %%%%%%% %% %%%%%% % %%%%%% % %%%% %% % % % %%%%%% %%%%% % %% %% %%%%% % %%%%%% % %%%%% %% % % %%%%%% %%%%%%%%%%% %% %% % %%%%%%%%%% %%%%%% % %. %%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% """ leewayFactor: "1.1" costFn: "lambda pos: .5 ** pos[0]"
homework_1_search/test_cases/q3/ucs_3_problemW.solution
# This is the solution file for test_cases/q3/ucs_3_problemW.test. # This solution is designed to support both right-to-left # and left-to-right implementations. # Number of nodes expanded must be with a factor of 1.1 of the numbers below. solution: """ West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West South South South South South South South South South East East East North North North North North North North East East South South South South South South East East North North North North North North East East South South South South East East North North East East South South East East East South South West West West West West West South South West West West West West South West West West West West South South East East East East East East East North East East East East East North North East East East East East East South South West West West West South South West West West West West South West West West West West West West West West """ expanded_nodes: "173" rev_solution: """ West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West West South South South South South South South South South East East East North North North North North North North East East South South South South South South East East North North North North North North East East South South South South East East North North East East South South East East East South South West West West West West West South South West West West West West South West West West West West South South East East East East East East East North East East East East East North North East East East East East East South South West West West West South South West West West West West South West West West West West West West West West """ rev_expanded_nodes: "173"
homework_1_search/test_cases/q3/ucs_3_problemW.test
class: "PacmanSearchTest" algorithm: "uniformCostSearch" points: "0.5" # The following specifies the layout to be used layoutName: "mediumMaze" layout: """ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % % %% % % %%%%%%% %% % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % %% %% % % %% % % % % % %%%% %%% %%%%%% % % % % % % % %% %%%%%%%% % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% % % %%%%%% %%%%%%% %% %%%%%% % %%%%%% % %%%% %% % % % %%%%%% %%%%% % %% %% %%%%% % %%%%%% % %%%%% %% % % %%%%%% %%%%%%%%%%% %% %% % %%%%%%%%%% %%%%%% % %. %%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% """ leewayFactor: "1.1" costFn: "lambda pos: 2 ** pos[0]"
homework_1_search/test_cases/q3/ucs_4_testSearch.solution
# This is the solution file for test_cases/q3/ucs_4_testSearch.test. # This solution is designed to support both right-to-left # and left-to-right implementations. # Number of nodes expanded must be with a factor of 2.0 of the numbers below. solution: """ West East East South South West West """ expanded_nodes: "14" rev_solution: """ West East East South South West West """ rev_expanded_nodes: "13"
homework_1_search/test_cases/q3/ucs_4_testSearch.test
class: "PacmanSearchTest" algorithm: "uniformCostSearch" points: "0.5" # The following specifies the layout to be used layoutName: "testSearch" layout: """ %%%%% %.P % %%% % %. % %%%%% """ searchProblemClass: "FoodSearchProblem" leewayFactor: "2"
homework_1_search/test_cases/q3/ucs_5_goalAtDequeue.solution
# This is the solution file for test_cases/q3/ucs_5_goalAtDequeue.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->B 0:B->C 0:C->G" expanded_states: "A B C" rev_solution: "1:A->B 0:B->C 0:C->G" rev_expanded_states: "A B C"
homework_1_search/test_cases/q3/ucs_5_goalAtDequeue.test
class: "GraphSearchTest" algorithm: "uniformCostSearch" diagram: """ 1 1 1 *A ---> B ---> C ---> [G] | ^ | 10 | \---------------------/ A is the start state, G is the goal. Arrows mark possible state transitions. The number next to the arrow is the cost of that transition. If you fail this test case, you may be incorrectly testing if a node is a goal before adding it into the queue, instead of testing when you remove the node from the queue. See the algorithm pseudocode in lecture. """ graph: """ start_state: A goal_states: G A 0:A->G G 10.0 A 1:A->B B 1.0 B 0:B->C C 1.0 C 0:C->G G 1.0 """ # We only care about the solution, not the expansion order. exactExpansionOrder: "False"
homework_1_search/test_cases/q4/astar_0.solution
# This is the solution file for test_cases/q4/astar_0.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "Right Down Down" expanded_states: "A B D C G" rev_solution: "Right Down Down" rev_expanded_states: "A B D C G"
homework_1_search/test_cases/q4/astar_0.test
class: "GraphSearchTest" algorithm: "aStarSearch" diagram: """ C ^ | 2 2 V 4 *A <----> B -----> [H] | 1.5 V 2.5 G <----- D -----> E | 2 | V [F] A is the start state, F and H is the goal. Arrows mark possible state transitions. The number next to the arrow is the cost of that transition. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: H F A Right B 2.0 B Right H 4.0 B Down D 1.0 B Up C 2.0 B Left A 2.0 C Down B 2.0 D Right E 2.5 D Down F 2.0 D Left G 1.5 """
homework_1_search/test_cases/q4/astar_1_graph_heuristic.solution
# This is the solution file for test_cases/q4/astar_1_graph_heuristic.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "0 0 2" expanded_states: "S A D C" rev_solution: "0 0 2" rev_expanded_states: "S A D C"
homework_1_search/test_cases/q4/astar_1_graph_heuristic.test
class: "GraphSearchTest" algorithm: "aStarSearch" diagram: """ 2 3 2 S --- A --- C ---> G | \ / ^ 3 | \ 5 / 1 / | \ / / B --- D -------/ 4 5 S is the start state, G is the goal. Arrows mark possible state transitions. The number next to the arrow is the cost of that transition. The heuristic value of each state is: S 6.0 A 2.5 B 5.25 C 1.125 D 1.0625 G 0 """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: S goal_states: G S 0 A 2.0 S 1 B 3.0 S 2 D 5.0 A 0 C 3.0 A 1 S 2.0 B 0 D 4.0 B 1 S 3.0 C 0 A 3.0 C 1 D 1.0 C 2 G 2.0 D 0 B 4.0 D 1 C 1.0 D 2 G 5.0 D 3 S 5.0 """ heuristic: """ S 6.0 A 2.5 B 5.25 C 1.125 D 1.0625 G 0 """
homework_1_search/test_cases/q4/astar_2_manhattan.solution
# This is the solution file for test_cases/q4/astar_2_manhattan.test. # This solution is designed to support both right-to-left # and left-to-right implementations. # Number of nodes expanded must be with a factor of 1.1 of the numbers below. solution: """ West West West West West West West West West South South East East South South South West West West North West West West West South South South East East East East East East East South South South South South South South West West West West West West West West West West West West West West West West West South West West West West West West West West West """ expanded_nodes: "221" rev_solution: """ West West West West West West West West West South South East East South South South West West West North West West West West South South South East East East East East East East South South South South South South South West West West West West West West West West West West West West West West West West South West West West West West West West West West """ rev_expanded_nodes: "221"
homework_1_search/test_cases/q4/astar_2_manhattan.test
class: "PacmanSearchTest" algorithm: "aStarSearch" # The following specifies the layout to be used layoutName: "mediumMaze" layout: """ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % P% % %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % % %% % % %%%%%%% %% % % %% % % % % %%%% %%%%%%%%% %% %%%%% % %% % % % % %% %% % % %% % % % % % %%%% %%% %%%%%% % % % % % % % %% %%%%%%%% % % %% % % %%%%%%%% %% %% %%%%% % %% % %% %%%%%%%%% %% % % %%%%%% %%%%%%% %% %%%%%% % %%%%%% % %%%% %% % % % %%%%%% %%%%% % %% %% %%%%% % %%%%%% % %%%%% %% % % %%%%%% %%%%%%%%%%% %% %% % %%%%%%%%%% %%%%%% % %. %%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% """ leewayFactor: "1.1" heuristic: "manhattanHeuristic"
homework_1_search/test_cases/q4/astar_3_goalAtDequeue.solution
# This is the solution file for test_cases/q4/astar_3_goalAtDequeue.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->B 0:B->C 0:C->G" expanded_states: "A B C" rev_solution: "1:A->B 0:B->C 0:C->G" rev_expanded_states: "A B C"
homework_1_search/test_cases/q4/astar_3_goalAtDequeue.test
class: "GraphSearchTest" algorithm: "aStarSearch" diagram: """ 1 1 1 *A ---> B ---> C ---> [G] | ^ | 10 | \---------------------/ A is the start state, G is the goal. Arrows mark possible state transitions. The number next to the arrow is the cost of that transition. If you fail this test case, you may be incorrectly testing if a node is a goal before adding it into the queue, instead of testing when you remove the node from the queue. See the algorithm pseudocode in lecture. """ graph: """ start_state: A goal_states: G A 0:A->G G 10.0 A 1:A->B B 1.0 B 0:B->C C 1.0 C 0:C->G G 1.0 """ # We only care about the solution, not the expansion order. exactExpansionOrder: "False"
homework_1_search/test_cases/q4/CONFIG
class: "PassAllTestsQuestion" max_points: "3"
homework_1_search/test_cases/q4/graph_backtrack.solution
# This is the solution file for test_cases/q4/graph_backtrack.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->C 0:C->G" expanded_states: "A B C D" rev_solution: "1:A->C 0:C->G" rev_expanded_states: "A B C D"
homework_1_search/test_cases/q4/graph_backtrack.test
class: "GraphSearchTest" algorithm: "aStarSearch" diagram: """ B ^ | *A --> C --> G | V D A is the start state, G is the goal. Arrows mark possible state transitions. This tests whether you extract the sequence of actions correctly even if your search backtracks. If you fail this, your nodes are not correctly tracking the sequences of actions required to reach them. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B B 1.0 A 1:A->C C 2.0 A 2:A->D D 4.0 C 0:C->G G 8.0 """
homework_1_search/test_cases/q4/graph_manypaths.solution
# This is the solution file for test_cases/q4/graph_manypaths.test. # This solution is designed to support both right-to-left # and left-to-right implementations. solution: "1:A->C 0:C->D 1:D->F 0:F->G" expanded_states: "A B1 C B2 D E1 F E2" rev_solution: "1:A->C 0:C->D 1:D->F 0:F->G" rev_expanded_states: "A B1 C B2 D E1 F E2"
homework_1_search/test_cases/q4/graph_manypaths.test
class: "GraphSearchTest" algorithm: "aStarSearch" diagram: """ B1 E1 ^ \ ^ \ / V / V *A --> C --> D --> F --> [G] \ ^ \ ^ V / V / B2 E2 A is the start state, G is the goal. Arrows mark possible state transitions. This graph has multiple paths to the goal, where nodes with the same state are added to the fringe multiple times before they are expanded. """ # The following section specifies the search problem and the solution. # The graph is specified by first the set of start states, followed by # the set of goal states, and lastly by the state transitions which are # of the form: # <start state> <actions> <end state> <cost> graph: """ start_state: A goal_states: G A 0:A->B1 B1 1.0 A 1:A->C C 2.0 A 2:A->B2 B2 4.0 B1 0:B1->C C 8.0 B2 0:B2->C C 16.0 C 0:C->D D 32.0 D 0:D->E1 E1 64.0 D 1:D->F F 128.0 D 2:D->E2 E2 256.0 E1 0:E1->F F 512.0 E2 0:E2->F F 1024.0 F 0:F->G G 2048.0 """
homework_1_search/test_cases/q5/CONFIG
class: "PassAllTestsQuestion" max_points: "3" depends: "q2"
homework_1_search/test_cases/q5/corner_tiny_corner.solution
# This is the solution file for test_cases/q5/corner_tiny_corner.test. solution_length: "28"
homework_1_search/test_cases/q5/corner_tiny_corner.test
class: "CornerProblemTest" layoutName: "tinyCorner" layout: """ %%%%%%%% %. .% % P % % %%%% % % % % % % %%%% %.% .% %%%%%%%% """
homework_1_search/test_cases/q6/CONFIG
class: "Q6PartialCreditQuestion" max_points: "3" depends: "q4"
homework_1_search/test_cases/q6/corner_sanity_1.solution
# In order for a heuristic to be admissible, the value # of the heuristic must be less at each state than the # true cost of the optimal path from that state to a goal. cost: "8" path: """ North South South East East East North North """
homework_1_search/test_cases/q6/corner_sanity_1.test
class: "CornerHeuristicSanity" points: "1" # The following specifies the layout to be used layout: """ %%%%%% %. .% %P % %. .% %%%%%% """
homework_1_search/test_cases/q6/corner_sanity_2.solution
# In order for a heuristic to be admissible, the value # of the heuristic must be less at each state than the # true cost of the optimal path from that state to a goal. cost: "8" path: """ West North North East East East South South """
homework_1_search/test_cases/q6/corner_sanity_2.test
class: "CornerHeuristicSanity" points: "1" # The following specifies the layout to be used layout: """ %%%%%% %. .% % %% % %.P%.% %%%%%% """
homework_1_search/test_cases/q6/corner_sanity_3.solution
# In order for a heuristic to be admissible, the value # of the heuristic must be less at each state than the # true cost of the optimal path from that state to a goal. cost: "28" path: """ South South South West West West West East East East East East North North North North North West West West South South South West West North North North """
homework_1_search/test_cases/q6/corner_sanity_3.test
class: "CornerHeuristicSanity" points: "1" # The following specifies the layout to be used layout: """ %%%%%%%% %.% .% % % % % % % %P % % % % %%%%% % %. .% %%%%%%%% """
homework_1_search/test_cases/q6/medium_corners.solution
# This solution file specifies the length of the optimal path # as well as the thresholds on number of nodes expanded to be # used in scoring. cost: "106" path: """ North East East East East North North West West West West North North North North North North North North West West West West South South East East East East South South South South South South West West South South South West West East East North North North East East East East East East East East South South East East East East East North North East East North North East East North North East East East East South South South South East East North North East East South South South South South North North North North North North North West West North North East East North North """ thresholds: "2000 1600 1200"
homework_1_search/test_cases/q6/medium_corners.test
class: "CornerHeuristicPacman" # The following specifies the layout to be used layout: """ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %. % % % %.% % % % %%%%%% %%%%%%% % % % % % % % % %%%%% %%%%% %%% %% %%%%% % %%% % % % % % % % % % % %%% % % % %%%%%%%% %%% %%% % % % %% % % % % %%% % %%%%%%% %%%% %%% % % % % % % %% % % % % % %%%%% % %%%% % %%% %%% % % % % % % % % %%% % %. %P%%%%% % %%% % .% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% """
homework_1_search/test_cases/q7/CONFIG
class: "PartialCreditQuestion" max_points: "4" depends: "q4"
homework_1_search/test_cases/q7/food_heuristic_1.solution
# This is the solution file for test_cases/q7/food_heuristic_1.test. solution_cost: "0"
homework_1_search/test_cases/q7/food_heuristic_1.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 1" layout: """ %%%%%% % % % % %P % %%%%%% """
homework_1_search/test_cases/q7/food_heuristic_10.solution
# This is the solution file for test_cases/q7/food_heuristic_10.test. solution_cost: "7"
homework_1_search/test_cases/q7/food_heuristic_10.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 10" layout: """ %%%%%%%% % % %. P .% % % %%%%%%%% """
homework_1_search/test_cases/q7/food_heuristic_11.solution
# This is the solution file for test_cases/q7/food_heuristic_11.test. solution_cost: "8"
homework_1_search/test_cases/q7/food_heuristic_11.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 11" layout: """ %%%%%%%% % % % P % %. . .% %%%%%%%% """
homework_1_search/test_cases/q7/food_heuristic_12.solution
# This is the solution file for test_cases/q7/food_heuristic_12.test. solution_cost: "1"
homework_1_search/test_cases/q7/food_heuristic_12.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 12" layout: """ %%%%%%%% % % % P.% % % %%%%%%%% """
homework_1_search/test_cases/q7/food_heuristic_13.solution
# This is the solution file for test_cases/q7/food_heuristic_13.test. solution_cost: "5"
homework_1_search/test_cases/q7/food_heuristic_13.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 13" layout: """ %%%%%%%% % % %P. .% % % %%%%%%%% """
homework_1_search/test_cases/q7/food_heuristic_14.solution
# This is the solution file for test_cases/q7/food_heuristic_14.test. solution_cost: "31"
homework_1_search/test_cases/q7/food_heuristic_14.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 14" layout: """ %%%%%%%%%% % % % ...%...% % .%.%.%.% % .%.%.%.% % .%.%.%.% % .%.%.%.% % .%.%.%.% %P.%...%.% % % %%%%%%%%%% """
homework_1_search/test_cases/q7/food_heuristic_15.solution
# This is the solution file for test_cases/q7/food_heuristic_15.test. solution_cost: "21"
homework_1_search/test_cases/q7/food_heuristic_15.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 15" layout: """ %%% % % % % % % % % % % %.% %.% % % % % % % % % % % % % % % %.% % % %P% % % % % % % % % %.% %%% """
homework_1_search/test_cases/q7/food_heuristic_16.solution
# This is the solution file for test_cases/q7/food_heuristic_16.test. solution_cost: "7"
homework_1_search/test_cases/q7/food_heuristic_16.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 16" layout: """ %%%% % .% % % %P % % % % .% %%%% """
homework_1_search/test_cases/q7/food_heuristic_17.solution
# This is the solution file for test_cases/q7/food_heuristic_17.test. solution_cost: "16"
homework_1_search/test_cases/q7/food_heuristic_17.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 17" layout: """ %%%%%%%% %.%....% %.% %%.% %.%P%%.% %... .% %%%%%%%% """
homework_1_search/test_cases/q7/food_heuristic_2.solution
# This is the solution file for test_cases/q7/food_heuristic_2.test. solution_cost: "0"
homework_1_search/test_cases/q7/food_heuristic_2.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 2" layout: """ %%% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %P% % % % % % % % % % % %%% """
homework_1_search/test_cases/q7/food_heuristic_3.solution
# This is the solution file for test_cases/q7/food_heuristic_3.test. solution_cost: "0"
homework_1_search/test_cases/q7/food_heuristic_3.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 3" layout: """ %%%% % % % % %P % % % % % %%%% """
homework_1_search/test_cases/q7/food_heuristic_4.solution
# This is the solution file for test_cases/q7/food_heuristic_4.test. solution_cost: "0"
homework_1_search/test_cases/q7/food_heuristic_4.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 4" layout: """ %%%%%%%% % % % % % %% % % %P%% % % % %%%%%%%% """
homework_1_search/test_cases/q7/food_heuristic_5.solution
# This is the solution file for test_cases/q7/food_heuristic_5.test. solution_cost: "11"
homework_1_search/test_cases/q7/food_heuristic_5.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 5" layout: """ %%%%%% %....% %....% %P...% %%%%%% """
homework_1_search/test_cases/q7/food_heuristic_6.solution
# This is the solution file for test_cases/q7/food_heuristic_6.test. solution_cost: "5"
homework_1_search/test_cases/q7/food_heuristic_6.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 6" layout: """ %%%%%% % .% %.P..% % % %%%%%% """
homework_1_search/test_cases/q7/food_heuristic_7.solution
# This is the solution file for test_cases/q7/food_heuristic_7.test. solution_cost: "7"
homework_1_search/test_cases/q7/food_heuristic_7.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 7" layout: """ %%%%%%% % .% %. P..% % % %%%%%%% """
homework_1_search/test_cases/q7/food_heuristic_8.solution
# This is the solution file for test_cases/q7/food_heuristic_8.test. solution_cost: "5"
homework_1_search/test_cases/q7/food_heuristic_8.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 8" layout: """ %%%%%% % .% % .% %P .% %%%%%% """
homework_1_search/test_cases/q7/food_heuristic_9.solution
# This is the solution file for test_cases/q7/food_heuristic_9.test. solution_cost: "6"
homework_1_search/test_cases/q7/food_heuristic_9.test
class: "HeuristicTest" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "Test 9" layout: """ %%%%%% % %. % % %%.% %P. .% %%%%%% """
homework_1_search/test_cases/q7/food_heuristic_grade_tricky.solution
# This is the solution file for test_cases/q7/food_heuristic_grade_tricky.test. # File intentionally blank.
homework_1_search/test_cases/q7/food_heuristic_grade_tricky.test
class: "HeuristicGrade" heuristic: "foodHeuristic" searchProblemClass: "FoodSearchProblem" layoutName: "trickySearch" layout: """ %%%%%%%%%%%%%%%%%%%% %. ..% % %.%%.%%.%%.%%.%% % % % P % % %%%%%%%%%%%%%%%%%% % %..... % %%%%%%%%%%%%%%%%%%%% """ # One point always, an extra point for each # threshold passed. basePoints: "1" gradingThresholds: "15000 12000 9000 7000"
homework_1_search/test_cases/q8/closest_dot_1.solution
# This is the solution file for test_cases/q8/closest_dot_1.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_1.test
class: "ClosestDotTest" layoutName: "Test 1" layout: """ %%%%%% %....% %....% %P...% %%%%%% """
homework_1_search/test_cases/q8/closest_dot_10.solution
# This is the solution file for test_cases/q8/closest_dot_10.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_10.test
class: "ClosestDotTest" layoutName: "Test 10" layout: """ %%%%%%%%%% % % % ...%...% % .%.%.%.% % .%.%.%.% % .%.%.%.% % .%.%.%.% % .%.%.%.% %P.%...%.% % % %%%%%%%%%% """
homework_1_search/test_cases/q8/closest_dot_11.solution
# This is the solution file for test_cases/q8/closest_dot_11.test. solution_length: "2"
homework_1_search/test_cases/q8/closest_dot_11.test
class: "ClosestDotTest" layoutName: "Test 11" layout: """ %%% % % % % % % % % % % %.% %.% % % % % % % % % % % % % % % %.% % % %P% % % % % % % % % %.% %%% """
homework_1_search/test_cases/q8/closest_dot_12.solution
# This is the solution file for test_cases/q8/closest_dot_12.test. solution_length: "3"
homework_1_search/test_cases/q8/closest_dot_12.test
class: "ClosestDotTest" layoutName: "Test 12" layout: """ %%%% % .% % % %P % % % % .% %%%% """
homework_1_search/test_cases/q8/closest_dot_13.solution
# This is the solution file for test_cases/q8/closest_dot_13.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_13.test
class: "ClosestDotTest" layoutName: "Test 13" layout: """ %%%%%%%% %.%....% %.% %%.% %.%P%%.% %... .% %%%%%%%% """
homework_1_search/test_cases/q8/closest_dot_2.solution
# This is the solution file for test_cases/q8/closest_dot_2.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_2.test
class: "ClosestDotTest" layoutName: "Test 2" layout: """ %%%%%% % .% %.P..% % % %%%%%% """
homework_1_search/test_cases/q8/closest_dot_3.solution
# This is the solution file for test_cases/q8/closest_dot_3.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_3.test
class: "ClosestDotTest" layoutName: "Test 3" layout: """ %%%%%%% % .% %. P..% % % %%%%%%% """
homework_1_search/test_cases/q8/closest_dot_4.solution
# This is the solution file for test_cases/q8/closest_dot_4.test. solution_length: "3"
homework_1_search/test_cases/q8/closest_dot_4.test
class: "ClosestDotTest" layoutName: "Test 4" layout: """ %%%%%% % .% % .% %P .% %%%%%% """
homework_1_search/test_cases/q8/closest_dot_5.solution
# This is the solution file for test_cases/q8/closest_dot_5.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_5.test
class: "ClosestDotTest" layoutName: "Test 5" layout: """ %%%%%% % %. % % %%.% %P. .% %%%%%% """
homework_1_search/test_cases/q8/closest_dot_6.solution
# This is the solution file for test_cases/q8/closest_dot_6.test. solution_length: "2"
homework_1_search/test_cases/q8/closest_dot_6.test
class: "ClosestDotTest" layoutName: "Test 6" layout: """ %%%%%%%% % % %. P .% % % %%%%%%%% """
homework_1_search/test_cases/q8/closest_dot_7.solution
# This is the solution file for test_cases/q8/closest_dot_7.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_7.test
class: "ClosestDotTest" layoutName: "Test 7" layout: """ %%%%%%%% % % % P % %. . .% %%%%%%%% """
homework_1_search/test_cases/q8/closest_dot_8.solution
# This is the solution file for test_cases/q8/closest_dot_8.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_8.test
class: "ClosestDotTest" layoutName: "Test 8" layout: """ %%%%%%%% % % % P.% % % %%%%%%%% """
homework_1_search/test_cases/q8/closest_dot_9.solution
# This is the solution file for test_cases/q8/closest_dot_9.test. solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_9.test
class: "ClosestDotTest" layoutName: "Test 9" layout: """ %%%%%%%% % % %P. .% % % %%%%%%%% """
homework_1_search/test_cases/q8/CONFIG
class: "PassAllTestsQuestion" max_points: "3"
homework_1_search/textDisplay.py
# textDisplay.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). import time try: import pacman except: pass DRAW_EVERY = 1 SLEEP_TIME = 0 # This can be overwritten by __init__ DISPLAY_MOVES = False QUIET = False # Supresses output class NullGraphics: def initialize(self, state, isBlue = False): pass def update(self, state): pass def checkNullDisplay(self): return True def pause(self): time.sleep(SLEEP_TIME) def draw(self, state): print(state) def updateDistributions(self, dist): pass def finish(self): pass class PacmanGraphics: def __init__(self, speed=None): if speed != None: global SLEEP_TIME SLEEP_TIME = speed def initialize(self, state, isBlue = False): self.draw(state) self.pause() self.turn = 0 self.agentCounter = 0 def update(self, state): numAgents = len(state.agentStates) self.agentCounter = (self.agentCounter + 1) % numAgents if self.agentCounter == 0: self.turn += 1 if DISPLAY_MOVES: ghosts = [pacman.nearestPoint(state.getGhostPosition(i)) for i in range(1, numAgents)] print("%4d) P: %-8s" % (self.turn, str(pacman.nearestPoint(state.getPacmanPosition()))),'| Score: %-5d' % state.score,'| Ghosts:', ghosts) if self.turn % DRAW_EVERY == 0: self.draw(state) self.pause() if state._win or state._lose: self.draw(state) def pause(self): time.sleep(SLEEP_TIME) def draw(self, state): print(state) def finish(self): pass
homework_1_search/util.py
# util.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). # util.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 # ([email protected]) and Dan Klein ([email protected]). # Student side autograding was added by Brad Miller, Nick Hay, and # Pieter Abbeel ([email protected]). import sys import inspect import heapq, random class FixedRandom: def __init__(self): fixedState = (3, (2147483648, 507801126, 683453281, 310439348, 2597246090, \ 2209084787, 2267831527, 979920060, 3098657677, 37650879, 807947081, 3974896263, \ 881243242, 3100634921, 1334775171, 3965168385, 746264660, 4074750168, 500078808, \ 776561771, 702988163, 1636311725, 2559226045, 157578202, 2498342920, 2794591496, \ 4130598723, 496985844, 2944563015, 3731321600, 3514814613, 3362575829, 3038768745, \ 2206497038, 1108748846, 1317460727, 3134077628, 988312410, 1674063516, 746456451, \ 3958482413, 1857117812, 708750586, 1583423339, 3466495450, 1536929345, 1137240525, \ 3875025632, 2466137587, 1235845595, 4214575620, 3792516855, 657994358, 1241843248, \ 1695651859, 3678946666, 1929922113, 2351044952, 2317810202, 2039319015, 460787996, \ 3654096216, 4068721415, 1814163703, 2904112444, 1386111013, 574629867, 2654529343, \ 3833135042, 2725328455, 552431551, 4006991378, 1331562057, 3710134542, 303171486, \ 1203231078, 2670768975, 54570816, 2679609001, 578983064, 1271454725, 3230871056, \ 2496832891, 2944938195, 1608828728, 367886575, 2544708204, 103775539, 1912402393, \ 1098482180, 2738577070, 3091646463, 1505274463, 2079416566, 659100352, 839995305, \ 1696257633, 274389836, 3973303017, 671127655, 1061109122, 517486945, 1379749962, \ 3421383928, 3116950429, 2165882425, 2346928266, 2892678711, 2936066049, 1316407868, \ 2873411858, 4279682888, 2744351923, 3290373816, 1014377279, 955200944, 4220990860, \ 2386098930, 1772997650, 3757346974, 1621616438, 2877097197, 442116595, 2010480266, \ 2867861469, 2955352695, 605335967, 2222936009, 2067554933, 4129906358, 1519608541, \ 1195006590, 1942991038, 2736562236, 279162408, 1415982909, 4099901426, 1732201505, \ 2934657937, 860563237, 2479235483, 3081651097, 2244720867, 3112631622, 1636991639, \ 3860393305, 2312061927, 48780114, 1149090394, 2643246550, 1764050647, 3836789087, \ 3474859076, 4237194338, 1735191073, 2150369208, 92164394, 756974036, 2314453957, \ 323969533, 4267621035, 283649842, 810004843, 727855536, 1757827251, 3334960421, \ 3261035106, 38417393, 2660980472, 1256633965, 2184045390, 811213141, 2857482069, \ 2237770878, 3891003138, 2787806886, 2435192790, 2249324662, 3507764896, 995388363, \ 856944153, 619213904, 3233967826, 3703465555, 3286531781, 3863193356, 2992340714, \ 413696855, 3865185632, 1704163171, 3043634452, 2225424707, 2199018022, 3506117517, \ 3311559776, 3374443561, 1207829628, 668793165, 1822020716, 2082656160, 1160606415, \ 3034757648, 741703672, 3094328738, 459332691, 2702383376, 1610239915, 4162939394, \ 557861574, 3805706338, 3832520705, 1248934879, 3250424034, 892335058, 74323433, \ 3209751608, 3213220797, 3444035873, 3743886725, 1783837251, 610968664, 580745246, \ 4041979504, 201684874, 2673219253, 1377283008, 3497299167, 2344209394, 2304982920, \ 3081403782, 2599256854, 3184475235, 3373055826, 695186388, 2423332338, 222864327, \ 1258227992, 3627871647, 3487724980, 4027953808, 3053320360, 533627073, 3026232514, \ 2340271949, 867277230, 868513116, 2158535651, 2487822909, 3428235761, 3067196046, \ 3435119657, 1908441839, 788668797, 3367703138, 3317763187, 908264443, 2252100381, \ 764223334, 4127108988, 384641349, 3377374722, 1263833251, 1958694944, 3847832657, \ 1253909612, 1096494446, 555725445, 2277045895, 3340096504, 1383318686, 4234428127, \ 1072582179, 94169494, 1064509968, 2681151917, 2681864920, 734708852, 1338914021, \ 1270409500, 1789469116, 4191988204, 1716329784, 2213764829, 3712538840, 919910444, \ 1318414447, 3383806712, 3054941722, 3378649942, 1205735655, 1268136494, 2214009444, \ 2532395133, 3232230447, 230294038, 342599089, 772808141, 4096882234, 3146662953, \ 2784264306, 1860954704, 2675279609, 2984212876, 2466966981, 2627986059, 2985545332, \ 2578042598, 1458940786, 2944243755, 3959506256, 1509151382, 325761900, 942251521, \ 4184289782, 2756231555, 3297811774, 1169708099, 3280524138, 3805245319, 3227360276, \ 3199632491, 2235795585, 2865407118, 36763651, 2441503575, 3314890374, 1755526087, \ 17915536, 1196948233, 949343045, 3815841867, 489007833, 2654997597, 2834744136, \ 417688687, 2843220846, 85621843, 747339336, 2043645709, 3520444394, 1825470818, \ 647778910, 275904777, 1249389189, 3640887431, 4200779599, 323384601, 3446088641, \ 4049835786, 1718989062, 3563787136, 44099190, 3281263107, 22910812, 1826109246, \ 745118154, 3392171319, 1571490704, 354891067, 815955642, 1453450421, 940015623, \ 796817754, 1260148619, 3898237757, 176670141, 1870249326, 3317738680, 448918002, \ 4059166594, 2003827551, 987091377, 224855998, 3520570137, 789522610, 2604445123, \ 454472869, 475688926, 2990723466, 523362238, 3897608102, 806637149, 2642229586, \ 2928614432, 1564415411, 1691381054, 3816907227, 4082581003, 1895544448, 3728217394, \ 3214813157, 4054301607, 1882632454, 2873728645, 3694943071, 1297991732, 2101682438, \ 3952579552, 678650400, 1391722293, 478833748, 2976468591, 158586606, 2576499787, \ 662690848, 3799889765, 3328894692, 2474578497, 2383901391, 1718193504, 3003184595, \ 3630561213, 1929441113, 3848238627, 1594310094, 3040359840, 3051803867, 2462788790, \ 954409915, 802581771, 681703307, 545982392, 2738993819, 8025358, 2827719383, \ 770471093, 3484895980, 3111306320, 3900000891, 2116916652, 397746721, 2087689510, \ 721433935, 1396088885, 2751612384, 1998988613, 2135074843, 2521131298, 707009172, \ 2398321482, 688041159, 2264560137, 482388305, 207864885, 3735036991, 3490348331, \ 1963642811, 3260224305, 3493564223, 1939428454, 1128799656, 1366012432, 2858822447, \ 1428147157, 2261125391, 1611208390, 1134826333, 2374102525, 3833625209, 2266397263, \ 3189115077, 770080230, 2674657172, 4280146640, 3604531615, 4235071805, 3436987249, \ 509704467, 2582695198, 4256268040, 3391197562, 1460642842, 1617931012, 457825497, \ 1031452907, 1330422862, 4125947620, 2280712485, 431892090, 2387410588, 2061126784, \ 896457479, 3480499461, 2488196663, 4021103792, 1877063114, 2744470201, 1046140599, \ 2129952955, 3583049218, 4217723693, 2720341743, 820661843, 1079873609, 3360954200, \ 3652304997, 3335838575, 2178810636, 1908053374, 4026721976, 1793145418, 476541615, \ 973420250, 515553040, 919292001, 2601786155, 1685119450, 3030170809, 1590676150, \ 1665099167, 651151584, 2077190587, 957892642, 646336572, 2743719258, 866169074, \ 851118829, 4225766285, 963748226, 799549420, 1955032629, 799460000, 2425744063, \ 2441291571, 1928963772, 528930629, 2591962884, 3495142819, 1896021824, 901320159, \ 3181820243, 843061941, 3338628510, 3782438992, 9515330, 1705797226, 953535929, \ 764833876, 3202464965, 2970244591, 519154982, 3390617541, 566616744, 3438031503, \ 1853838297, 170608755, 1393728434, 676900116, 3184965776, 1843100290, 78995357, \ 2227939888, 3460264600, 1745705055, 1474086965, 572796246, 4081303004, 882828851, \ 1295445825, 137639900, 3304579600, 2722437017, 4093422709, 273203373, 2666507854, \ 3998836510, 493829981, 1623949669, 3482036755, 3390023939, 833233937, 1639668730, \ 1499455075, 249728260, 1210694006, 3836497489, 1551488720, 3253074267, 3388238003, \ 2372035079, 3945715164, 2029501215, 3362012634, 2007375355, 4074709820, 631485888, \ 3135015769, 4273087084, 3648076204, 2739943601, 1374020358, 1760722448, 3773939706, \ 1313027823, 1895251226, 4224465911, 421382535, 1141067370, 3660034846, 3393185650, \ 1850995280, 1451917312, 3841455409, 3926840308, 1397397252, 2572864479, 2500171350, \ 3119920613, 531400869, 1626487579, 1099320497, 407414753, 2438623324, 99073255, \ 3175491512, 656431560, 1153671785, 236307875, 2824738046, 2320621382, 892174056, \ 230984053, 719791226, 2718891946, 624), None) self.random = random.Random() self.random.setstate(fixedState) """ Data structures useful for implementing SearchAgents """ class Stack: "A container with a last-in-first-out (LIFO) queuing policy." def __init__(self): self.list = [] def push(self,item): "Push 'item' onto the stack" self.list.append(item) def pop(self): "Pop the most recently pushed item from the stack" return self.list.pop() def isEmpty(self): "Returns true if the stack is empty" return len(self.list) == 0 class Queue: "A container with a first-in-first-out (FIFO) queuing policy." def __init__(self): self.list = [] def push(self,item): "Enqueue the 'item' into the queue" self.list.insert(0,item) def pop(self): """ Dequeue the earliest enqueued item still in the queue. This operation removes the item from the queue. """ return self.list.pop() def isEmpty(self): "Returns true if the queue is empty" return len(self.list) == 0 class PriorityQueue: """ Implements a priority queue data structure. Each inserted item has a priority associated with it and the client is usually interested in quick retrieval of the lowest-priority item in the queue. This data structure allows O(1) access to the lowest-priority item. """ def __init__(self): self.heap = [] self.count = 0 def push(self, item, priority): entry = (priority, self.count, item) heapq.heappush(self.heap, entry) self.count += 1 def pop(self): (_, _, item) = heapq.heappop(self.heap) return item def isEmpty(self): return len(self.heap) == 0 def update(self, item, priority): # If item already in priority queue with higher priority, update its priority and rebuild the heap. # If item already in priority queue with equal or lower priority, do nothing. # If item not in priority queue, do the same thing as self.push. for index, (p, c, i) in enumerate(self.heap): if i == item: if p <= priority: break del self.heap[index] self.heap.append((priority, c, item)) heapq.heapify(self.heap) break else: self.push(item, priority) class PriorityQueueWithFunction(PriorityQueue): """ Implements a priority queue with the same push/pop signature of the Queue and the Stack classes. This is designed for drop-in replacement for those two classes. The caller has to provide a priority function, which extracts each item's priority. """ def __init__(self, priorityFunction): "priorityFunction (item) -> priority" self.priorityFunction = priorityFunction # store the priority function PriorityQueue.__init__(self) # super-class initializer def push(self, item): "Adds an item to the queue with priority from the priority function" PriorityQueue.push(self, item, self.priorityFunction(item)) def manhattanDistance( xy1, xy2 ): "Returns the Manhattan distance between points xy1 and xy2" return abs( xy1[0] - xy2[0] ) + abs( xy1[1] - xy2[1] ) """ Data structures and functions useful for various course projects The search project should not need anything below this line. """ class Counter(dict): """ A counter keeps track of counts for a set of keys. The counter class is an extension of the standard python dictionary type. It is specialized to have number values (integers or floats), and includes a handful of additional functions to ease the task of counting data. In particular, all keys are defaulted to have value 0. Using a dictionary: a = {} print(a['test']) would give an error, while the Counter class analogue: >>> a = Counter() >>> print(a['test']) 0 returns the default 0 value. Note that to reference a key that you know is contained in the counter, you can still use the dictionary syntax: >>> a = Counter() >>> a['test'] = 2 >>> print(a['test']) 2 This is very useful for counting things without initializing their counts, see for example: >>> a['blah'] += 1 >>> print(a['blah']) 1 The counter also includes additional functionality useful in implementing the classifiers for this assignment. Two counters can be added, subtracted or multiplied together. See below for details. They can also be normalized and their total count and arg max can be extracted. """ def __getitem__(self, idx): self.setdefault(idx, 0) return dict.__getitem__(self, idx) def incrementAll(self, keys, count): """ Increments all elements of keys by the same count. >>> a = Counter() >>> a.incrementAll(['one','two', 'three'], 1) >>> a['one'] 1 >>> a['two'] 1 """ for key in keys: self[key] += count def argMax(self): """ Returns the key with the highest value. """ if len(self.keys()) == 0: return None all = self.items() values = [x[1] for x in all] maxIndex = values.index(max(values)) return all[maxIndex][0] def sortedKeys(self): """ Returns a list of keys sorted by their values. Keys with the highest values will appear first. >>> a = Counter() >>> a['first'] = -2 >>> a['second'] = 4 >>> a['third'] = 1 >>> a.sortedKeys() ['second', 'third', 'first'] """ sortedItems = self.items() compare = lambda x, y: sign(y[1] - x[1]) sortedItems.sort(cmp=compare) return [x[0] for x in sortedItems] def totalCount(self): """ Returns the sum of counts for all keys. """ return sum(self.values()) def normalize(self): """ Edits the counter such that the total count of all keys sums to 1. The ratio of counts for all keys will remain the same. Note that normalizing an empty Counter will result in an error. """ total = float(self.totalCount()) if total == 0: return for key in self.keys(): self[key] = self[key] / total def divideAll(self, divisor): """ Divides all counts by divisor """ divisor = float(divisor) for key in self: self[key] /= divisor def copy(self): """ Returns a copy of the counter """ return Counter(dict.copy(self)) def __mul__(self, y ): """ Multiplying two counters gives the dot product of their vectors where each unique label is a vector element. >>> a = Counter() >>> b = Counter() >>> a['first'] = -2 >>> a['second'] = 4 >>> b['first'] = 3 >>> b['second'] = 5 >>> a['third'] = 1.5 >>> a['fourth'] = 2.5 >>> a * b 14 """ sum = 0 x = self if len(x) > len(y): x,y = y,x for key in x: if key not in y: continue sum += x[key] * y[key] return sum def __radd__(self, y): """ Adding another counter to a counter increments the current counter by the values stored in the second counter. >>> a = Counter() >>> b = Counter() >>> a['first'] = -2 >>> a['second'] = 4 >>> b['first'] = 3 >>> b['third'] = 1 >>> a += b >>> a['first'] 1 """ for key, value in y.items(): self[key] += value def __add__( self, y ): """ Adding two counters gives a counter with the union of all keys and counts of the second added to counts of the first. >>> a = Counter() >>> b = Counter() >>> a['first'] = -2 >>> a['second'] = 4 >>> b['first'] = 3 >>> b['third'] = 1 >>> (a + b)['first'] 1 """ addend = Counter() for key in self: if key in y: addend[key] = self[key] + y[key] else: addend[key] = self[key] for key in y: if key in self: continue addend[key] = y[key] return addend def __sub__( self, y ): """ Subtracting a counter from another gives a counter with the union of all keys and counts of the second subtracted from counts of the first. >>> a = Counter() >>> b = Counter() >>> a['first'] = -2 >>> a['second'] = 4 >>> b['first'] = 3 >>> b['third'] = 1 >>> (a - b)['first'] -5 """ addend = Counter() for key in self: if key in y: addend[key] = self[key] - y[key] else: addend[key] = self[key] for key in y: if key in self: continue addend[key] = -1 * y[key] return addend def raiseNotDefined(): fileName = inspect.stack()[1][1] line = inspect.stack()[1][2] method = inspect.stack()[1][3] print("*** Method not implemented: %s at line %s of %s" % (method, line, fileName)) sys.exit(1) def normalize(vectorOrCounter): """ normalize a vector or counter by dividing each value by the sum of all values """ normalizedCounter = Counter() if type(vectorOrCounter) == type(normalizedCounter): counter = vectorOrCounter total = float(counter.totalCount()) if total == 0: return counter for key in counter.keys(): value = counter[key] normalizedCounter[key] = value / total return normalizedCounter else: vector = vectorOrCounter s = float(sum(vector)) if s == 0: return vector return [el / s for el in vector] def nSample(distribution, values, n): if sum(distribution) != 1: distribution = normalize(distribution) rand = [random.random() for i in range(n)] rand.sort() samples = [] samplePos, distPos, cdf = 0,0, distribution[0] while samplePos < n: if rand[samplePos] < cdf: samplePos += 1 samples.append(values[distPos]) else: distPos += 1 cdf += distribution[distPos] return samples def sample(distribution, values = None): if type(distribution) == Counter: items = sorted(distribution.items()) distribution = [i[1] for i in items] values = [i[0] for i in items] if sum(distribution) != 1: distribution = normalize(distribution) choice = random.random() i, total= 0, distribution[0] while choice > total: i += 1 total += distribution[i] return values[i] def sampleFromCounter(ctr): items = sorted(ctr.items()) return sample([v for k,v in items], [k for k,v in items]) def getProbability(value, distribution, values): """ Gives the probability of a value under a discrete distribution defined by (distributions, values). """ total = 0.0 for prob, val in zip(distribution, values): if val == value: total += prob return total def flipCoin( p ): r = random.random() return r < p def chooseFromDistribution( distribution ): "Takes either a counter or a list of (prob, key) pairs and samples" if type(distribution) == dict or type(distribution) == Counter: return sample(distribution) r = random.random() base = 0.0 for prob, element in distribution: base += prob if r <= base: return element def nearestPoint( pos ): """ Finds the nearest grid point to a position (discretizes). """ ( current_row, current_col ) = pos grid_row = int( current_row + 0.5 ) grid_col = int( current_col + 0.5 ) return ( grid_row, grid_col ) def sign( x ): """ Returns 1 or -1 depending on the sign of x """ if( x >= 0 ): return 1 else: return -1 def arrayInvert(array): """ Inverts a matrix stored as a list of lists. """ result = [[] for i in array] for outer in array: for inner in range(len(outer)): result[inner].append(outer[inner]) return result def matrixAsList( matrix, value = True ): """ Turns a matrix into a list of coordinates matching the specified value """ rows, cols = len( matrix ), len( matrix[0] ) cells = [] for row in range( rows ): for col in range( cols ): if matrix[row][col] == value: cells.append( ( row, col ) ) return cells def lookup(name, namespace): """ Get a method or class from any imported module from its name. Usage: lookup(functionName, globals()) """ dots = name.count('.') if dots > 0: moduleName, objName = '.'.join(name.split('.')[:-1]), name.split('.')[-1] module = __import__(moduleName) return getattr(module, objName) else: modules = [obj for obj in namespace.values() if str(type(obj)) == "<type 'module'>"] options = [getattr(module, name) for module in modules if name in dir(module)] options += [obj[1] for obj in namespace.items() if obj[0] == name ] if len(options) == 1: return options[0] if len(options) > 1: raise Exception('Name conflict for %s') raise Exception('%s not found as a method or class' % name) def pause(): """ Pauses the output stream awaiting user feedback. """ input("<Press enter/return to continue>") # code to handle timeouts # # FIXME # NOTE: TimeoutFuncton is NOT reentrant. Later timeouts will silently # disable earlier timeouts. Could be solved by maintaining a global list # of active time outs. Currently, questions which have test cases calling # this have all student code so wrapped. # import signal import time class TimeoutFunctionException(Exception): """Exception to raise on a timeout""" pass class TimeoutFunction: def __init__(self, function, timeout): self.timeout = timeout self.function = function def handle_timeout(self, signum, frame): raise TimeoutFunctionException() def __call__(self, *args, **keyArgs): # If we have SIGALRM signal, use it to cause an exception if and # when this function runs too long. Otherwise check the time taken # after the method has returned, and throw an exception then. if hasattr(signal, 'SIGALRM'): old = signal.signal(signal.SIGALRM, self.handle_timeout) signal.alarm(self.timeout) try: result = self.function(*args, **keyArgs) finally: signal.signal(signal.SIGALRM, old) signal.alarm(0) else: startTime = time.time() result = self.function(*args, **keyArgs) timeElapsed = time.time() - startTime if timeElapsed >= self.timeout: self.handle_timeout(None, None) return result _ORIGINAL_STDOUT = None _ORIGINAL_STDERR = None _MUTED = False class WritableNull: def write(self, string): pass def mutePrint(): global _ORIGINAL_STDOUT, _ORIGINAL_STDERR, _MUTED if _MUTED: return _MUTED = True _ORIGINAL_STDOUT = sys.stdout #_ORIGINAL_STDERR = sys.stderr sys.stdout = WritableNull() #sys.stderr = WritableNull() def unmutePrint(): global _ORIGINAL_STDOUT, _ORIGINAL_STDERR, _MUTED if not _MUTED: return _MUTED = False sys.stdout = _ORIGINAL_STDOUT #sys.stderr = _ORIGINAL_STDERR
homework_1_search/VERSION
v1.001
