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

        gameState.isWin():
        Returns whether or not the game state is a winning state

        gameState.isLose():
        Returns whether or not the game state is a losing state
        """
        def dispatcher(depth, index, gameState):
            if (index == gameState.getNumAgents() - 1 and depth == self.depth) or gameState.isWin() or gameState.isLose():
                return self.evaluationFunction(gameState)
            if index:
                return min_func(depth, index, gameState)
            else:
                if depth:
                    return max_func(depth, index, gameState)
                else:
                    return max_func_start(depth, index,gameState)
        def min_func(depth, index, gameState):
            v = float("inf")
            index = index + 1
            index %= gameState.getNumAgents()
            if not index:
                depth += 1
            for action in gameState.getLegalActions():
                successor = gameState.generateSuccessor(index,action)
                v = min(v, dispatcher(depth, index, successor))
            return v
        def max_func(depth, index, gameState):
            v = float("-inf")
            index = index + 1
            index %= gameState.getNumAgents()
            if not index:
                depth += 1
            for action in gameState.getLegalActions():
                successor = gameState.generateSuccessor(index,action)
                v = max(v, dispatcher(depth, index, successor))
            return v
        def max_func_start(depth, index, gameState):
            v = float("-inf")
            index = index + 1
            index %= gameState.getNumAgents()
            if not index:
                depth += 1
            bestAction = None
            for action in gameState.getLegalActions():
                oldv = v
                successor = gameState.generateSuccessor(index,action)
                v = max(v, dispatcher(depth, index, successor))
                if v != oldv:
                    bestAction = action
            return bestAction
        return dispatcher(0, 0, gameState)
        "*** YOUR CODE HERE ***"
        util.raiseNotDefined()