diff options
Diffstat (limited to 'src/multiAgents.py')
| -rw-r--r-- | src/multiAgents.py | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/src/multiAgents.py b/src/multiAgents.py new file mode 100644 index 0000000..31a3b3c --- /dev/null +++ b/src/multiAgents.py @@ -0,0 +1,232 @@ +# multiAgents.py +# -------------- +# Licensing Information: You are free to use or extend these projects for +# educational purposes provided that (1) you do not distribute or publish +# solutions, (2) you retain this notice, and (3) you provide clear +# attribution to UC Berkeley, including a link to http://ai.berkeley.edu. +# +# Attribution Information: The Pacman AI projects were developed at UC Berkeley. +# The core projects and autograders were primarily created by John DeNero +# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu). +# Student side autograding was added by Brad Miller, Nick Hay, and +# Pieter Abbeel (pabbeel@cs.berkeley.edu). + + +from util import manhattanDistance +from game import Directions +import random, util +import sys + +from game import Agent + +class ReflexAgent(Agent): + """ + A reflex agent chooses an action at each choice point by examining + its alternatives via a state evaluation function. + + The code below is provided as a guide. You are welcome to change + it in any way you see fit, so long as you don't touch our method + headers. + """ + + + def getAction(self, gameState): + """ + You do not need to change this method, but you're welcome to. + + getAction chooses among the best options according to the evaluation function. + + Just like in the previous project, getAction takes a GameState and returns + some Directions.X for some X in the set {North, South, West, East, Stop} + """ + # Collect legal moves and successor states + legalMoves = gameState.getLegalActions() + + # Choose one of the best actions + scores = [self.evaluationFunction(gameState, action) for action in legalMoves] + bestScore = max(scores) + bestIndices = [index for index in range(len(scores)) if scores[index] == bestScore] + chosenIndex = random.choice(bestIndices) # Pick randomly among the best + + "Add more of your code here if you want to" + + return legalMoves[chosenIndex] + + def evaluationFunction(self, currentGameState, action): + """ + Design a better evaluation function here. + + The evaluation function takes in the current and proposed successor + GameStates (pacman.py) and returns a number, where higher numbers are better. + + The code below extracts some useful information from the state, like the + remaining food (newFood) and Pacman position after moving (newPos). + newScaredTimes holds the number of moves that each ghost will remain + scared because of Pacman having eaten a power pellet. + + Print out these variables to see what you're getting, then combine them + to create a masterful evaluation function. + """ + # Useful information you can extract from a GameState (pacman.py) + successorGameState = currentGameState.generatePacmanSuccessor(action) + newPos = successorGameState.getPacmanPosition() + newFood = successorGameState.getFood() + newGhostStates = successorGameState.getGhostStates() + newScaredTimes = [ghostState.scaredTimer for ghostState in newGhostStates] + + "*** YOUR CODE HERE ***" + closestFoodDistance = float('inf') + newFoodList = newFood.asList() + #pacman eats a food, no penalty + if len(currentGameState.getFood().asList()) > len(newFoodList): + closestFoodDistance = 0 + #pacman won't eat a food in this successor + else: + for food in newFoodList: + if manhattanDistance(newPos, food) < closestFoodDistance: + closestFoodDistance = manhattanDistance(newPos, food) + + #penalties for ghosts being too close to pacman + ghostModifier = 0 + for ghost in newGhostStates: + #worst case a ghost will kill him (3 ** 2) = 9 + #best case, ghost is far away (theoretically) ~(3 ** -inf) = 0 + #on larger maps this will need to be increased + ghostModifier += 3 ** (2-manhattanDistance(newPos, ghost.getPosition())) + + #worst case is when pacman is far from food and a ghost will kill him + penalty = closestFoodDistance + ghostModifier + #the highest score of all successors gets picked, i.e. the best case of this function + return -penalty + +def scoreEvaluationFunction(currentGameState): + """ + This default evaluation function just returns the score of the state. + The score is the same one displayed in the Pacman GUI. + + This evaluation function is meant for use with adversarial search agents + (not reflex agents). + """ + return currentGameState.getScore() + +class MultiAgentSearchAgent(Agent): + """ + This class provides some common elements to all of your + multi-agent searchers. Any methods defined here will be available + to the MinimaxPacmanAgent, AlphaBetaPacmanAgent & ExpectimaxPacmanAgent. + + You *do not* need to make any changes here, but you can if you want to + add functionality to all your adversarial search agents. Please do not + remove anything, however. + + Note: this is an abstract class: one that should not be instantiated. It's + only partially specified, and designed to be extended. Agent (game.py) + is another abstract class. + """ + + def __init__(self, evalFn = 'scoreEvaluationFunction', depth = '2'): + self.index = 0 # Pacman is always agent index 0 + self.evaluationFunction = util.lookup(evalFn, globals()) + self.depth = int(depth) + +class MinimaxAgent(MultiAgentSearchAgent): + """ + Your minimax agent (question 2) + """ + + def getAction(self, gameState): + """ + Returns the minimax action from the current gameState using self.depth + and self.evaluationFunction. + + Here are some method calls that might be useful when implementing minimax. + + gameState.getLegalActions(agentIndex): + Returns a list of legal actions for an agent + agentIndex=0 means Pacman, ghosts are >= 1 + + gameState.generateSuccessor(agentIndex, action): + Returns the successor game state after an agent takes an action + + gameState.getNumAgents(): + Returns the total number of agents in the game + """ + + self.action = None + + def minimax(gameState, depth, agentIndex): + if gameState.isWin() or gameState.isLose() or depth == self.depth: + return self.evaluationFunction(gameState) + + if agentIndex == 0: + return value(gameState, depth, agentIndex, max) + else: + return value(gameState, depth, agentIndex, min) + + #generic value function that excepts a lambda function to return either then min or max value + def value(gameState, depth, agentIndex, minMax): + score = float('inf') + if minMax == max: + score = -score + + agentActions = gameState.getLegalActions(agentIndex) + + if agentIndex == gameState.getNumAgents() - 1: + #recurse down to the bottom depth + depth = depth + 1 + nextIndex = 0 + else: + #get the min action for every agent at this depth + nextIndex = agentIndex + 1 + + for action in agentActions: + successorState = gameState.generateSuccessor(agentIndex, action) + oldScore = score + score = minMax(score, minimax(successorState, depth, nextIndex)) + if depth == 0 and minMax == max and score != oldScore: + self.action = action + return score + + score = minimax(gameState, 0, self.index) + return self.action + +class AlphaBetaAgent(MultiAgentSearchAgent): + """ + Your minimax agent with alpha-beta pruning (question 3) + """ + + def getAction(self, gameState): + """ + Returns the minimax action using self.depth and self.evaluationFunction + """ + "*** YOUR CODE HERE ***" + util.raiseNotDefined() + +class ExpectimaxAgent(MultiAgentSearchAgent): + """ + Your expectimax agent (question 4) + """ + + def getAction(self, gameState): + """ + Returns the expectimax action using self.depth and self.evaluationFunction + + All ghosts should be modeled as choosing uniformly at random from their + legal moves. + """ + "*** YOUR CODE HERE ***" + util.raiseNotDefined() + +def betterEvaluationFunction(currentGameState): + """ + Your extreme ghost-hunting, pellet-nabbing, food-gobbling, unstoppable + evaluation function (question 5). + + DESCRIPTION: <write something here so we know what you did> + """ + "*** YOUR CODE HERE ***" + util.raiseNotDefined() + +# Abbreviation +better = betterEvaluationFunction + |