def getAction(self, state):
     "The agent receives a GameState (defined in pacman.py)."
     "[Project 1] YOUR CODE HERE"
     vector = {Directions.EAST:(1, 0), Directions.WEST:(-1, 0), Directions.SOUTH:(0, -1), Directions.NORTH:(0, 1), Directions.STOP:(0, 0)}
     pacman_pos = state.getPacmanPosition()
     ghost_pos_all = []
     for ghost_pos in state.getGhostPositions():
         ghost_pos = util.nearestPoint(ghost_pos)
         for key in vector:
             x = ghost_pos[0] + vector[key][0]
             y = ghost_pos[1] + vector[key][1]
             ghost_pos_all.append((x, y))
     print ghost_pos_all
     next_pos_all = []
     for action in state.getLegalActions():
         next_pos_all.append((pacman_pos[0] + vector[action][0], pacman_pos[1] + vector[action][1]))
     for next_pos in next_pos_all:
         if next_pos in ghost_pos_all:
             for action in [Directions.NORTH, Directions.SOUTH]:
                 if action in state.getLegalActions():
                     return action
     for action in [Directions.EAST, Directions.WEST]:
         if (pacman_pos[0] + vector[action][0], pacman_pos[1] + vector[action][1]) in ghost_pos_all:
             return Directions.REVERSE[action]
     return Directions.STOP

 def getAction(self, gameState):
   """
   Calls chooseAction on a grid position, but continues on half positions.
   
   This method also cedes some processing time to the distance calculator, 
   which computes the shortest path distance between all pairs of points.
   
   If you subclass CaptureAgent, you shouldn't need to override this method.  It
   takes care of appending the current gameState on to your observation history
   (so you have a record of the game states of the game) and will call your
   choose action method if you're in a state (rather than halfway through your last
   move - this occurs because Pacman agents move half as quickly as ghost agents).
   
   If you aren't going to be using the distance calculator we provide, you can comment
   out the line beginning "distanceCalculator" so as not to lose computing time to the
   calculating distances you're not using.
   """
   # Give some time to the distance calculator thread
   distanceCalculator.waitOnDistanceCalculator(self.timeForComputing)
   
   self.observationHistory.append(gameState)
   
   myState = gameState.getAgentState(self.index)
   myPos = myState.getPosition()
   if myPos != nearestPoint(myPos): 
     # We're halfway from one position to the next
     return gameState.getLegalActions(self.index)[0]
   else:
     return self.chooseAction(gameState)

  def getSuccessor(self, index, gameState, action):
    """
    Finds the next successor which is a grid position (location tuple).
    """
    team = self.getTeam(gameState)
    for agent in team:
        if index == agent:
            temp = gameState.generateSuccessor(self.index, action)
            successor = temp.deepCopy()
            successor.data.agentStates = copy.deepcopy(temp.data.agentStates)
            pos = successor.getAgentState(self.index).getPosition()
            
            if pos != nearestPoint(pos):
                # Only half a grid position was covered
                return successor.generateSuccessor(self.index, action)
            else:
                return successor            

    successor = gameState.deepCopy()
    successor.data.agentStates = copy.deepcopy(gameState.data.agentStates)
    #successor.data.agentStates = gameState.copyAgentStates(successor.data.agentStates)
    position = self.getNextPosition(successor, successor.data.agentStates[index].configuration.pos, action)
    successor.data.agentStates[index].configuration.pos = position
    
    
    foodList = self.getFoodYouAreDefending(gameState).asList()
    for food in foodList:
        if food == position:
            x,y = position
            successor.data.food[x][y] = False
            successor.data.score += 1
            successor.data.scoreChange = 1
        
    return successor

    def __str__(self):
        width, height = self.layout.width, self.layout.height
        map = Grid(width, height)
        if ut.isInstance(self.food, (1, 2)):
            self.food = ut.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 is None:
                continue
            if agentState.configuration is None:
                continue
            x, y = [int(i) for i in
                    ut.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 mstHeuristic(state, problem):
    if "calc" not in problem.heuristicInfo:
        problem.heuristicInfo["calc"] = DistanceCalculator(problem.startingGameState.data.layout)
    calculator = problem.heuristicInfo["calc"]

    BIG_COST = 1000
    totalCost = -BIG_COST
    foodList = state[1].asList()
    # only works for integral pacman positions
    foodList.append(util.nearestPoint(state[0]))
    treeNodes = {}
    nonTreeNodes = util.PriorityQueue()
    nodeCosts = {}
    for pos in foodList:
        nonTreeNodes.push(pos, BIG_COST)
        nodeCosts[pos] = BIG_COST
    while not nonTreeNodes.isEmpty():
        newNode = nonTreeNodes.pop()
        cost = nodeCosts[newNode]
        totalCost += cost
        treeNodes[newNode] = 1
        for nonTreeNode in foodList:
            if treeNodes.has_key(nonTreeNode):
                continue
            newDist = calculator.getDistance(newNode, nonTreeNode)
            # newDist = manhattanDist(newNode, nonTreeNode)
            oldDist = nodeCosts[nonTreeNode]
            if newDist < oldDist:
                nodeCosts[nonTreeNode] = newDist
                nonTreeNodes.push(nonTreeNode, newDist)
    return totalCost

  def applyAction( state, action, index ):
    """
    Edits the state to reflect the results of the action.
    """
    legal = BombermanRules.getLegalActions( state, index)
    if action not in legal:
      print ("Illegal action " + str(action) + " with agentIndex " + str(index) + ' and legals:' + str(legal))
      #action = random.choice(legal)
      if Directions.STOP in legal: action = Directions.STOP
      else : action =random.choice(legal)

    agentState = state.data.agentStates[index]

    # Update Configuration
    vector = Actions.directionToVector( action, agentState.getSpeed() )
    agentState.configuration = agentState.configuration.generateSuccessor( vector )
    # Eat
    next = agentState.configuration.getPosition()
    nearest = nearestPoint( next )
    if manhattanDistance( nearest, next ) <= 0.5 :
      # consume item
      BombermanRules.consume( nearest, state, index )
    # Lay bomb
    if action is Actions.LAY:
      state.layABomb(index,nearest)

 def isGoalState(self, state):
   pos = state.getAgentState(self.agentIndex).getPosition()
   x,y = nearestPoint(pos)
   if pos != (x,y): return False
   if self.targets[x][y]:
     pass
   return self.targets[x][y]

  def applyAction(state, action, agentIndex):
    """
    Edits the state to reflect the results of the action.
    """
    legal = AgentRules.getLegalActions(state, agentIndex)
    if action not in legal:
      raise Exception("Illegal action " + str(action))

    # Update Configuration
    agentState = state.data.agentStates[agentIndex]
    speed = 1.0
    # if agentState.isPacman: speed = 0.5
    vector = Actions.directionToVector(action, speed)
    oldConfig = agentState.configuration
    agentState.configuration = oldConfig.generateSuccessor(vector)

    # Eat
    next = agentState.configuration.getPosition()
    nearest = nearestPoint(next)
    if agentState.isPacman and manhattanDistance(nearest, next) <= 0.9 :
      AgentRules.consume(nearest, state, state.isOnRedTeam(agentIndex))

    # Change agent type
    if next == nearest:
      agentState.isPacman = [state.isOnRedTeam(agentIndex), state.isRed(agentState.configuration)].count(True) == 1

 def getSuccessor(self, gameState, action):
     successor = gameState.generateSuccessor(self.index, action)
     pos = successor.getAgentState(self.index).getPosition()
     if pos != nearestPoint(pos):
         return successor.generateSuccessor(self.index, action)
     else:
         return successor

 def getPathToNearestDot(self, gameState, myState):
   """
   A path takes the form [(whereYouAre, whatYouDo), ...]
   """
   food = self.getFood(gameState)
   problem = AnyDotOnSideWillDo(nearestPoint(myState.getPosition()), food, gameState.getWalls())
   states, actions, cost = search.breadthFirstSearch(problem)
   return zip(states, actions)

 def evalFn(self, successor, action):
   if self.getFood(successor).count() == 0: return 1000
   myState = successor.getAgentState(self.index)
   pos = myState.getPosition() 
   if pos != nearestPoint(pos): return self.evalFn(successor.generateSuccessor(self.index, action), action)
   
   food = self.getFood(successor)
   problem = AnyDotOnSideWillDo(nearestPoint(pos), food, successor.getWalls())
   distanceToFood = search.breadthFirstSearch(problem)[2]
   
   distanceToOpponent = 100
   for enemyIndex in self.getOpponents(successor):
     opp = successor.getAgentState(enemyIndex)
     if not opp.isPacman:
       distanceToOpponent = min(distanceToOpponent, manhattanDistance(myState.getPosition(), opp.getPosition()))
     
   return -0.3 * distanceToFood + self.getScore(successor) + 2 * math.log(distanceToOpponent)

 def getSuccessor(self, gameState, action):
   # Finds the next successor which is a grid position (location tuple).
   successor = gameState.generateSuccessor(self.index, action)
   pos = successor.getAgentState(self.index).getPosition()
   if pos != nearestPoint(pos):
     # Only half a grid position was covered
     return successor.generateSuccessor(self.index, action)
   else:
     return successor

 def getAction(self, gameState):
     self.observationHistory.append(gameState)
     myState = gameState.getAgentState(self.index)
     myPos = myState.getPosition()
     if myPos != util.nearestPoint(myPos):
       # We're halfway from one position to the next
           return gameState.getLegalActions(self.index)[0]
     else:
           return self.chooseAction(gameState)

  def getAction(self, state):
    myState = state.getAgentState(self.index)
    myPos = myState.getPosition()
    if myPos != nearestPoint(myPos): 
      return self.lastAction

    action = self.chooseAction(state, myState)
    if action == Directions.STOP: print 'stop'
    self.lastAction = action
    return action

 def capsuleEdible(self, pacmanPos, capsulePos):
     """
     arguments:
         pacmanPos is an x,y position on the board (representing pacman's location)
         capsulePos is an x,y position on the board (representing a capsule's location)
     returns:
         True if pacman can eat the capsule at capsulePos from pacmanPos, else False
     """
     nearest = nearestPoint(pacmanPos)
     return nearest == capsulePos and manhattanDistance(nearest, pacmanPos) <= 0.5

 def cumGhostsDistance(position, ghostPositions, state):
   ghostStates = state.getGhostStates()
   scaredTimes = [ghostState.scaredTimer for ghostState in ghostStates]
   total = 0
   for i in range(len(scaredTimes)):
     d = math.sqrt(mazeDistance(position, util.nearestPoint(state.getGhostPosition(i+1)), state))
     if scaredTimes[i] > 0:
       d = d * math.sqrt(scaredTimes[i])
     else:
       d *= -1 
     total += int(d)
   return total

  def applyAction( state, action, agentIndex ):
    """
    Edits the state to reflect the results of the action.
    """
    legal = AgentRules.getLegalActions( state, agentIndex )
    if action not in legal:
      raise Exception("Illegal action " + str(action))

    # Update Configuration
    agentState = state.data.agentStates[agentIndex]
    speed = 1.0
    # if agentState.isPacman: speed = 0.5
    vector = Actions.directionToVector( action, speed )
    oldConfig = agentState.configuration
    agentState.configuration = oldConfig.generateSuccessor( vector )

    # Eat
    next = agentState.configuration.getPosition()
    nearest = nearestPoint( next )
# TODO limit change agent type(in our case always 1 pacman two ghost)
# TODO or just say we think in this way it's fun...
    if next == nearest:
      isRed = state.isOnRedTeam(agentIndex)
      # Change agent type
      # important for change agent type once on opponent's land
      agentState.isPacman = [isRed, state.isRed(agentState.configuration)].count(True) == 1
      # if he's no longer pacman, he's on his own side, so reset the num carrying timer
      #agentState.numCarrying *= int(agentState.isPacman)
      if agentState.numCarrying > 0 and not agentState.isPacman:
        # TODO score = agentState.numCarrying if isRed else -1*agentState.numCarrying
        # TODO temp disable one point score per numcarrying
        score = 0
        state.data.scoreChange += score

        agentState.numReturned += agentState.numCarrying
        agentState.numCarrying = 0

        redCount = 0
        blueCount = 0
        for index in range(state.getNumAgents()):
          agentState = state.data.agentStates[index]
          if index in state.getRedTeamIndices():
            redCount += agentState.numReturned
          else:
            blueCount += agentState.numReturned
        #if redCount >= (TOTAL_FOOD/2) - MIN_FOOD or blueCount >= (TOTAL_FOOD/2) - MIN_FOOD:
          #state.data._win = True


    if agentState.isPacman and manhattanDistance( nearest, next ) <= 0.9 :
      AgentRules.consume( nearest, state, state.isOnRedTeam(agentIndex) )

  def getSuccessor(self, gameState, action, alternateId = None):
    """
    Finds the next successor which is a grid position (location tuple).
    """
    if alternateId: id = alternateId
    else: id = self.index

    successor = gameState.generateSuccessor(id, action)
    pos = successor.getAgentState(id).getPosition()
    if pos != nearestPoint(pos):
      # Only half a grid position was covered
      return successor.generateSuccessor(id, action)
    else:
      return successor

def scoreEvaluation(state):
    score  = state.getScore()
    position = state.getPacmanPosition()
    nearest = nearestPoint(position)
	
    for index in range(1,len(state.data.agentStates)):
        if not state.data.agentStates[index].scaredTimer > 0:
            gstate = state.data.agentStates[index].configuration.getPosition()
            dis = manhattanDistance(gstate,nearest)
            if dis <= 3:
                score -= (20-5*dis)
            elif dis <= 5:
                score -= (11-2*dis)
    return score

    def evalState(state):
      position = state.getPacmanPosition()
      capsules = state.getCapsules()
      foodGrid = state.getFood()
      foodState = position, foodGrid, tuple(capsules)
      closestFood = None
      if foodState in closestFoodCache:
        closestFood = closestFoodCache[foodState]
      else:
        nodes = util.Queue()
        node = position, 0
        nodes.push(node)
        closestFood = findClosestFood(nodes, foodGrid, capsules, state.getWalls())
        closestFoodCache[foodState] = closestFood
      
      ghostState = position, tuple(ghostPositions)
      closestGhost = None
      if ghostState in evalCache:
        closestGhost = evalCache[ghostState]
      else:
        closestGhost = min(mazeDistance(position, util.nearestPoint(ghostPosition), state) for ghostPosition in ghostPositions)
        evalCache[ghostState] = closestGhost

      foodLeft = state.getNumFood()         
      score = state.getScore()
      #scared = newScaredTimes[0] > 0
      #cgd = cumGhostsDistance(position, ghostPositions, state)
      #numFoodEaten = startNumFood - foodLeft

      # a = 0
      # if score < 0:
      #   a = -1 * math.sqrt(abs(score))
      # elif score > 0:
      #   a = math.sqrt(score)
      a = score
      b = -1 * closestFood
      c = -1 * foodLeft**2
      #d = 0.5 * (( closestGhost**(1.0/4)) + ( 10 * scared * closestGhost))
      d = -1 * closestGhost
      #e = cgd
      f = 100 * len(capsules) 
      #print 'newScaredTimes', newScaredTimes
      #print 'score, closestFood, cgd', score, b, e
      result = a + b + d + f
      return result