# tools for minimax

def _switch_rate(r):
    '''Return opposing players rating corresponding to r.'''

    return r * -1 # one's loss is the other's gain

class GameState:

    """State of a two-person game, including player about to play.

       Assumptions:
       Two-person, zero-sum game, with exactly three outcomes:
       player one can win, lose, or draw, whereas player two
       can (respectively) lose, win, or draw.
       Each ply toggles player_1 <-> player_2.
    """
    '''Class constants.'''
    WIN = 1
    LOSE = -1
    DRAW = 0
    INF = float(9999999999999999999999999)


    def __init__(self, start_state):
        """Create a new Game in starting state.

            Arguments
            start_state:  Tuple (layout, starting player).
        """

        self._state = start_state

    def terminal_eval(self):
        """Return current player's score at end of game.

           Assumptions:
           The game is in a state reachable from the initial position by a
           sequence of plies, with a current player to play, but no further
           plies allowed.

           Returns:
           Return whether the current player wins, loses, or ties.
        """

        if self.winner(self.player()):
            return self.WIN
        elif self.winner(self.opponent()):
            return self.LOSE
        else:
            return self.DRAW

    def heuristic_eval(self):
        """Return estimate of current player's score at end of game.

           Assumptions:
           Game is in a state reachable from initial position by sequence
           of plies, current player to play, possibly further moves allowed.

           Returns:
           Confidence that current player wins (0,1], loses [-1,0), or
           draws (0).
        """

        raise NotImplementedError('Implemented in GameState subclass')

    def minimax(self, foresight, pred_max=-1, layout=None):
        """Return best move and score for current GameState.

           Arguments:
           foresight: Number of plies we may look ahead.
           pred_max:  Best score so far of predecessor GameState.
           layout:    Dictionary containing best score and move
                      for each layout

            Assumptions:
            Current player has at least one legal move available.
            foresight is positive.

            Returns (m, s)
            s:  Highest score that current player can guarantee.
            m:  Next move that allows current player to guarantee s.
        """
        if self.next_move() == []:
            return terminal_eval()
        for plys in self.next_move():
            game_after_ply = self.make_move(plys)
            score =  game_after_ply.heuristic_eval()
            if foresight == 0:
                if  game_after_ply.next_move() == []:
                    if score == -1:
                        return (1, plys)
                    elif score == 0:
                        if 0 > pred_max:
                            return (0, plys)
                    else:
                        return (-1, plys)
                else:
                    if score < pred_max:
                        return (score, plys)
            else:
                foresight -= 1
                tup = self.minimax((foresight), pred_max, layout)
                layout[tup[0]] = tup[1]
        keys = layout.keys()
        keys_s = keys.sort()
        return (keys_s[0], layout[keys_s[0]])









    def player(self):
        """Return current player --- the one with option of moving.

           Assumptions
           Player returned is one of 'p1' or 'p2'.
           Player returned might have no legal moves available.
        """

        return self._state[1]  # state is a 2-tuple

    def opponent(self):
        """Return opponent of current player."""
        if self.player() == 'p1':
            return 'p2'
        else:
            return 'p1'

    def next_move(self):
        """Return a sequence of all legal moves."""
        raise NotImplementedError('Implement next_move in GameState subclass')

    def winner(self, player):
        """Return whether this player has won."""
        raise NotImplementedError('Implement winner in GameState subclass')

    def make_move(self, move):
        """Return new GameState by applying move."""
        raise NotImplementedError('Implement make_move in GameState subclass')