from tkinter import NE
from turtle import position
import game_rules, random
###########################################################################
# Explanation of the types:
# The board is represented by a row-major 2D list of characters, 0 indexed
# A point is a tuple of (int, int) representing (row, column)
# A move is a tuple of (point, point) representing (origin, destination)
# A jump is a move of length 2
###########################################################################

# I will treat these like constants even though they aren't
# Also, these values obviously are not real infinity, but close enough for this purpose
NEG_INF = -1000000000
POS_INF = 1000000000

class Player(object):
    """ This is the player interface that is consumed by the GameManager. """
    def __init__(self, symbol): self.symbol = symbol # 'x' or 'o'

    def __str__(self): return str(type(self))

    def selectInitialX(self, board): return (0, 0)
    def selectInitialO(self, board): pass

    def getMove(self, board): pass

    def h1(self, board, symbol):
        return -len(game_rules.getLegalMoves(board, 'o' if symbol == 'x' else 'x'))


# This class has been replaced with the code for a deterministic player.
class MinimaxPlayer(Player):
    def __init__(self, symbol, depth): 
        super(MinimaxPlayer, self).__init__(symbol)
        self.depth = depth

    def selectInitialX(self, board): return (0,0)
    def selectInitialO(self, board):
        validMoves = game_rules.getFirstMovesForO(board)
        return list(validMoves)[0]

    """function minimax-decision(state) returns an action
            v<- max-value(state)
            return the action in Successors(state) with value v"""
    def getMove(self, board):
        return self.maxValue(board, self.depth, self.symbol)[1]

    """function maxValue(state) returns a utility value
            if Terminal-Test(state) then return utility(state)
            v <- -inf
            for a,s in Successors(state) do
                v<-max(v,min-value(s))
            return v"""
    def maxValue(self, board, depth, symbol):
        legalMoves = game_rules.getLegalMoves(board, symbol)
        if depth == 0 or len(legalMoves) == 0:
            return (self.h1(board, self.symbol), None)
        maxVal = (NEG_INF, None)
        for i in range(len(legalMoves)):
            nextBoard = game_rules.makeMove(board, legalMoves[i])
            if symbol == 'x':
                eval = self.minValue(nextBoard, depth-1, 'o')[0]
            else:
                eval = self.minValue(nextBoard, depth-1, 'x')[0]
            if maxVal[0] < eval:
                maxVal = (eval, legalMoves[i])
        print(maxVal[1])
        return maxVal

    """function minValue(state) returns a utility value
            if Terminal-Test(state) then return utility(state)
            v <- inf
            for a,s in Successors(state) do
                v<-min(v,min-value(s))
            return v"""        
    def minValue(self, board, depth, symbol):
        legalMoves = game_rules.getLegalMoves(board, symbol)
        if depth == 0 or len(legalMoves) == 0:
            return (self.h1(board, self.symbol), None)
        minVal = (POS_INF, None)
        for i in range(len(legalMoves)):
            nextBoard = game_rules.makeMove(board, legalMoves[i])
            if symbol == 'x':
                eval = self.maxValue(nextBoard, depth-1, 'o')[0]
            else:
                eval = self.maxValue(nextBoard, depth-1, 'x')[0]
            if minVal[0] > eval:
                minVal = (eval, legalMoves[i])
        return minVal


# This class has been replaced with the code for a deterministic player.
class AlphaBetaPlayer(Player):
    def __init__(self, symbol, depth): 
        super(AlphaBetaPlayer, self).__init__(symbol)
        self.depth = depth

    # Leave these two functions alone.
    def selectInitialX(self, board): return (0,0)
    def selectInitialO(self, board):
        validMoves = game_rules.getFirstMovesForO(board)
        return list(validMoves)[0]

    """function alpha-beta-search(state) returns an action
            inputs: state, current state in game
            v<- max-value(state,-inf,inf)
            return the action in Successors(state) with value v"""
    def getMove(self, board):
        return self.alphabetaSearch(board)[1]
    def alphabetaSearch(self, board):
        return self.maxValue(board, NEG_INF, POS_INF, self.depth, self.symbol)

    """function maxValue(state, alpha, beta) returns a utility value
            inputs: state, current state in game
                    alpha, the value of the best alternative for MAX along the path to state
                    beta, the value of the best alternative for MIN along the path to state
            if Terminal-Test(state) then return utility(state)
            v <- -inf
            for a,s in Successors(state) do
                v<-max(v,min-value(s,alpha,beta))
                if v >= beta then return v
                alpha <- max(alpha, v)
            return v"""
    def maxValue(self, board, alpha, beta, depth, symbol):
        legalMoves = game_rules.getLegalMoves(board, symbol)
        if depth == 0 or len(legalMoves) == 0:
            return (self.h1(board, self.symbol), None)
        maxVal = (NEG_INF, None)
        for i in range(len(legalMoves)):
            nextBoard = game_rules.makeMove(board, legalMoves[i])
            if symbol == 'x':
                eval = self.minValue(nextBoard, alpha, beta, depth-1, 'o')[0]
            else:
                eval = self.minValue(nextBoard, alpha, beta, depth-1, 'x')[0]
            if maxVal[0] < eval:
                maxVal = (eval, legalMoves[i])
            if maxVal[0] >= beta:
                return maxVal
            if alpha < maxVal[0]:
                alpha = maxVal[0]
        print(maxVal[1])
        return maxVal

    """function minValue(state) returns a utility value
            inputs: state, current state in game
                    alpha, the value of the best alternative for MAX along the path to state
                    beta, the value of the best alternative for MIN along the path to state
            if Terminal-Test(state) then return utility(state)
            v <- inf
            for a,s in Successors(state) do
                v<-min(v,min-value(s, alpha, beta))
                if v =< alpha then return v
                beta <- min(beta, v)
            return v"""        
    def minValue(self, board, alpha, beta, depth, symbol):
        legalMoves = game_rules.getLegalMoves(board, symbol)
        if depth == 0 or len(legalMoves) == 0:
            return (self.h1(board, self.symbol), None)
        minVal = (POS_INF, None)
        for i in range(len(legalMoves)):
            nextBoard = game_rules.makeMove(board, legalMoves[i])
            if symbol == 'x':
                eval = self.maxValue(nextBoard, alpha, beta, depth-1, 'o')[0]
            else:
                eval = self.maxValue(nextBoard, alpha, beta, depth-1, 'x')[0]
            if minVal[0] > eval:
                minVal = (eval, legalMoves[i])
            if minVal[0] <= alpha:
                return minVal
            if beta > minVal[0]:
                beta = minVal[0]
        return minVal



class RandomPlayer(Player):
    def __init__(self, symbol):
        super(RandomPlayer, self).__init__(symbol)

    def selectInitialX(self, board):
        validMoves = game_rules.getFirstMovesForX(board)
        return random.choice(list(validMoves))

    def selectInitialO(self, board):
        validMoves = game_rules.getFirstMovesForO(board)
        return random.choice(list(validMoves))

    def getMove(self, board):
        legalMoves = game_rules.getLegalMoves(board, self.symbol)
        if len(legalMoves) > 0: return random.choice(legalMoves)
        else: return None


class DeterministicPlayer(Player):
    def __init__(self, symbol): super(DeterministicPlayer, self).__init__(symbol)

    def selectInitialX(self, board): return (0,0)
    def selectInitialO(self, board):
        validMoves = game_rules.getFirstMovesForO(board)
        return list(validMoves)[0]

    def getMove(self, board):
        legalMoves = game_rules.getLegalMoves(board, self.symbol)
        if len(legalMoves) > 0: 
            print(legalMoves[0])
            return legalMoves[0]
        else: return None


class HumanPlayer(Player):
    def __init__(self, symbol): super(HumanPlayer, self).__init__(symbol)
    def selectInitialX(self, board): raise NotImplementedException('HumanPlayer functionality is handled externally.')
    def selectInitialO(self, board): raise NotImplementedException('HumanPlayer functionality is handled externally.')
    def getMove(self, board): raise NotImplementedException('HumanPlayer functionality is handled externally.')


def makePlayer(playerType, symbol, depth=1):
    player = playerType[0].lower()
    if player   == 'h': return HumanPlayer(symbol)
    elif player == 'r': return RandomPlayer(symbol)
    elif player == 'm': return MinimaxPlayer(symbol, depth)
    elif player == 'a': return AlphaBetaPlayer(symbol, depth)
    elif player == 'd': return DeterministicPlayer(symbol)
    else: raise NotImplementedException('Unrecognized player type {}'.format(playerType))

def callMoveFunction(player, board):
    if game_rules.isInitialMove(board): return player.selectInitialX(board) if player.symbol == 'x' else player.selectInitialO(board)
    else: return player.getMove(board)