class AlphaBetaAgent(MultiAgentSearchAgent):
    """
    Your minimax agent with alpha-beta pruning (question 3)
    """

    def get_action(self, game_state):
        """
        Returns the minimax action using self.depth and self.evaluationFunction
        """
        """*** YOUR CODE HERE ***"""
        return self.alphabeta(game_state, self.depth * 2, 0 , -float('inf'), float('inf'))[1]

    def alphabeta(self, state, curr_depth, player, alpha, beta):
        if curr_depth == 0:
            return self.evaluation_function(state), Action.STOP

        if player == 0: # max
            best_value = -float('inf')
            actions = state.get_legal_actions(player)
            succ_states = [state.generate_successor(player, action) for action in actions]

            if len(actions) == 0:
                return self.evaluation_function(state), Action.STOP
            best_action = actions[0]

            for index, succ in enumerate(succ_states):
                value, drop = self.alphabeta(succ, curr_depth - 1, 1, alpha, beta)
                if value > best_value:
                    best_value = value
                    best_action = actions[index]

                if value >= beta:
                    return (best_value, best_action)

                alpha = max(alpha, value)


        else: # min
            best_value = float('inf')
            actions = state.get_legal_actions(player)
            succ_states = [state.generate_successor(player, action) for action in actions]

            if len(actions) == 0:
                return self.evaluation_function(state), Action.STOP
            best_action = actions[0]

            for index, succ in enumerate(succ_states):
                value, drop = self.alphabeta(succ, curr_depth - 1, 0, alpha, beta)
                if value < best_value:
                    best_value = value
                    best_action = actions[index]

                if value <= alpha:
                    return (best_value, best_action)

                beta = min(beta, value)

        return (best_value, best_action)