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
        """
        "*** YOUR CODE HERE ***"

        agentCount = gameState.getNumAgents()
        foodCount = len(gameState.getFood().asList())
        score = []
        MAX_ROUND = self.depth * agentCount

        def isGhost(index):
          return index != 0

        def isOver(state):
          return state.isWin() or state.isLose()

        def terminalTest(state, round):
          return isOver(state) or round >= MAX_ROUND

        def minValue(state, round, agentIndex):
          result = foodCount
          for action in state.getLegalActions(agentIndex):
            result = min(minMax(state.generateSuccessor(agentIndex,action), round + 1),result)
          return result

        def maxValue(state, round, agentIndex):
          result = -foodCount
          for action in state.getLegalActions(agentIndex):
            result = max(minMax(state.generateSuccessor(agentIndex,action), round + 1),result)
            if round==0:
              score.append(result)
          return result

        def minMax(state, round):
          agentIndex = round%agentCount
          if terminalTest(state, round):
            return self.evaluationFunction(state)
          if isGhost(agentIndex):
            return minValue(state, round, agentIndex)
          else:
            return maxValue(state, round, agentIndex)

        minMax(gameState, 0)
        maxValue = max(score)
        return gameState.getLegalActions(0)[score.index(maxValue)]

        #util.raiseNotDefined()

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 ***"

        agentCount = gameState.getNumAgents()
        foodCount = len(gameState.getFood().asList())
        score = []
        MAX_ROUND = self.depth * agentCount

        def isGhost(index):
          return index != 0

        def isOver(state):
          return state.isWin() or state.isLose()

        def terminalTest(state, round):
          return isOver(state) or round >= MAX_ROUND

        def minValue(state, round, agentIndex, alpha, beta):
          result = foodCount
          for action in state.getLegalActions(agentIndex):
            result = min(alphaBeta(state.generateSuccessor(agentIndex,action), round + 1, alpha, beta),result)
            beta = min(beta, result)
            if beta < alpha:
              break
          return result

        def maxValue(state, round, agentIndex, alpha, beta):
          result = -foodCount
          for action in state.getLegalActions(agentIndex):
            result = max(alphaBeta(state.generateSuccessor(agentIndex,action), round + 1, alpha, beta),result)
            alpha = max(alpha, result)
            if round == 0:
              score.append(result)
            if beta < alpha:
              break
          return result

        def alphaBeta(state, round, alpha, beta):
          agentIndex = round%agentCount
          if terminalTest(state, round):
            return self.evaluationFunction(state)
          if isGhost(agentIndex):
            minValue(state, round, agentIndex, alpha, beta)
          else:
            maxValue(state, round, agentIndex, alpha, beta)

        alphaBeta(gameState, 0, -foodCount, foodCount)
        maxValue = max(score)
        return gameState.getLegalActions(0)[score.index(maxValue)]

        #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.
        """
        agentCount = gameState.getNumAgents()
        foodCount = len(gameState.getFood().asList())
        score = []
        MAX_ROUND = self.depth * agentCount

        def isGhost(index):
          return index != 0

        def isOver(state):
          return state.isWin() or state.isLose()

        def terminalTest(state, round):
          return isOver(state) or round >= MAX_ROUND

        def minValue(state, round, agentIndex):
          succ = []
          scoreSum = 0
          result = foodCount
          for action in state.getLegalActions(agentIndex):
            result = expectiMax(state.generateSuccessor(agentIndex,action), round + 1)
            succ.append(result)
          for s in succ:
            scoreSum += s
          average = scoreSum/len(succ)
          return average

        def maxValue(state, round, agentIndex):
          result = -foodCount
          for action in state.getLegalActions(agentIndex):
            result = max(expectiMax(state.generateSuccessor(agentIndex,action), round + 1),result)
            if round==0:
              score.append(result)
          return result

        def expectiMax(state, round):
          agentIndex = round%agentCount
          if terminalTest(state, round):
            return self.evaluationFunction(state)
          if isGhost(agentIndex):
            return minValue(state, round, agentIndex)
          else:
            return maxValue(state, round, agentIndex)

        expectiMax(gameState, 0);
        maxValue = max(score)
        return gameState.getLegalActions(0)[score.index(maxValue)]

        #util.raiseNotDefined()



 # def foodDistanceHeuristic():
 #   distanceToFood = []
 #   for food in gameState.getFood().asList():
 #     distanceToFood.append(manhattanDistance(gameState.getPacmanPosition(), food))
 #   if len(distanceToFood) > 0:
 #     return 100.0/(1.0 + min(distanceToFood))
 #   else:
 #     return 0.0

# 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 dynamicHeuristic(state):

#   def computeLambda():
#     foods_left = len(state.getFood().asList())
#     foods_total = len(problem.getStartState().getFood().asList())

#     return (foods_total - foods_left) / foods_total

#   heuristic_early_game = foodDistanceHeuristicd
#   heuristic_late_game = manhattanHeuristic(state, problem, 0)

#   # Scale heuristics to same scale
#   pass

#   weight = computeLambda()

#   # Convex combination
#   return ((1 - weight) * heuristic_early_game) + (weight * heuristic_late_game)

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 ***"
    def ghostScore(gameState):
      score = 0
      for ghost in gameState.getGhostStates():
        distance = manhattanDistance(gameState.getPacmanPosition(), ghost.getPosition())
        if ghost.scaredTimer > distance:
          score += 1/(1 + sqrt(distance))
        else:
          score -= 1/(1 + sqrt(distance))
      return score

    def foodScore(gameState):
      distance = []
      for food in gameState.getFood().asList():
        distance.append(manhattanDistance(gameState.getPacmanPosition(), food))
      if len(distance) > 0:
        return 100.0/(1.0 + min(distance))
      else:
        return 0.0

    def capsuleScore(gameState):
      distance = []
      for capsule in gameState.getCapsules():
        distance.append(manhattanDistance(gameState.getPacmanPosition(), capsule))
      if len(distance) > 0:
        return 1000.0/(1.0 + min(distance))
      else:
        return 0

    #def _suicide(gameState):
    #  score = 0
    #  disGhost = 1e6
    #  for ghost in gameState.getGhostStates():
    #    disGhost = min(manhattanDistance(gameState.getPacmanPosition(), ghost.getPosition()), disGhost)
    #  score -= pow(disGhost, 2)
    #  if gameState.isLose():
    #    score = 1e6
    #  return score

    score = currentGameState.getScore()
    scoreGhosts = ghostScore(currentGameState)
    scoreFood = foodScore(currentGameState)
    scoreCapsules = capsuleScore(currentGameState)
    #foodHeuristic = dynamicHeuristic(currentGameState, problem)
    #if score < 800 and currentGameState.getNumFood() <= 1 and len(currentGameState.getCapsules()) == 0:
    #  return _suicide(currentGameState)
    #else:
    return score + scoreGhosts + scoreFood + scoreCapsules