"""Author : Amit Jagannath Magar
Assignment No 2: Designing unbeatable Tic Tac Toe game using MinMax Algorithm and MinMax algorithm using alpha beta pruning
Version : 1.0

Reference := Game search from Geek for Geeks
"""

"""
Player's move will always represented as 'x' and Computer's move will be represented as 'o'
"""

no_states = 0  # this variable will count no of states generated by each min max algo
no_statesab = 0  # this variable will count no of states generated by min max algorithm with pruning


def getVal(matrix):
    """This function checks if Player or Computer has own the game"""
    # Checking for rows
    for iter in range(0, 3):
        if matrix[iter][0] == matrix[iter][1] and matrix[iter][1] == matrix[iter][2]:
            if matrix[iter][0] == 'x':
                return 1
            if matrix[iter][0] == 'o':
                return -1
    # Checking for columns

    for iter in range(0, 3):
        if matrix[0][iter] == matrix[1][iter] and matrix[1][iter] == matrix[2][iter]:
            if matrix[0][iter] == 'x':
                return 1
            if matrix[0][iter] == 'o':
                return -1
    # Checking for diagonals
    if matrix[0][0] == matrix[1][1] and matrix[1][1] == matrix[2][2]:
        if matrix[0][0] == 'x':
            return 1
        if matrix[0][0] == 'o':
            return -1
    if matrix[0][2] == matrix[1][1] and matrix[1][1] == matrix[2][0]:
        if matrix[0][2] == 'x':
            return 1;
        if matrix[0][2] == 'o':
            return -1

    return 0


"""
This function checks if there are possible moves on board which player can take
"""


def checkMoves(matrix):
    for iter1 in range(0, 3):
        for iter2 in range(0, 3):
            if matrix[iter1][iter2] == '_':
                return True
    return False


"""
This function is implementation of minimax algorithms which generate minimax tree recursively
"""


def miniMax(matrix, player):
    global no_states
    no_states = no_states + 1  # Increment count of global states generated by minimax algorithm for each step

    INFINITY = float("inf")

    # Evaluate board to check if anyone has won the game or not
    val = getVal(matrix)
    if val == 1:
        return 1
    elif val == -1:
        return -1
    else:
        if checkMoves(matrix) == False:  # if there is no winner in game and no possible moves to take return 0
            return 0

        if player == 'x':  # check if this is maximizer player
            max1 = -INFINITY

            for it1 in range(0, 3):
                for it2 in range(0, 3):
                    if matrix[it1][it2] == '_':  # check for empty position on board and generate tree
                        matrix[it1][it2] = 'x'
                        max1 = max(max1, miniMax(matrix, 'o'))  # Call minimizer ply
                        matrix[it1][it2] = '_'
            return max1  # return maximum gain which can be achieved
        else:
            min1 = INFINITY
            for it1 in range(0, 3):
                for it2 in range(0, 3):
                    if matrix[it1][it2] == '_':  # check for empty position on board and generate tree
                        matrix[it1][it2] = 'o'
                        min1 = min(min1, miniMax(matrix, 'x'))  # Call maximizer ply
                        matrix[it1][it2] = '_'
            return min1


"""
This function implements MiniMax algorithm with alph beta pruning
"""


def miniMaxAB(matrix, player, alpha, beta):
    global no_statesab  # Increment count of global states generated by minimax algorithm using pruning for each step
    no_statesab = no_statesab + 1
    INFINITY = float("inf")

    # Evaluate currenet matrix board
    val = getVal(matrix)
    if val == 1:
        return 1
    elif val == -1:
        return -1
    else:
        if checkMoves(matrix) == False:
            return 0

        if player == 'x':  # check if this is maximizer player
            # print ('in max function')

            for it1 in range(0, 3):
                for it2 in range(0, 3):
                    if matrix[it1][it2] == '_':  # check for empty position on board and generate tree
                        matrix[it1][it2] = 'x'
                        val = miniMaxAB(matrix, 'o', alpha, beta)
                        matrix[it1][it2] = '_'
                        alpha = max(val, alpha)

                        if beta <= alpha:  # pruning
                            return beta
            return alpha  # return maximum gain which can be achieved
        else:
            for it1 in range(0, 3):
                for it2 in range(0, 3):
                    if matrix[it1][it2] == '_':  # check for empty position on board and generate tree
                        matrix[it1][it2] = 'o'
                        val = miniMaxAB(matrix, 'x', alpha, beta)
                        matrix[it1][it2] = '_'
                        beta = min(beta, val)
                        if beta <= alpha:  # pruning
                            return alpha
            return beta


"""this functions calls both min max functions and min max with alpha beta pruning functions to get optimal move to play """


def findBest(matrix):
    global no_states
    global no_statesab
    bestVal = float("inf")
    bestVal2 = float("inf")

    x = -1
    y = -1
    x2 = -1
    y2 = -1

    no_states = 0
    no_statesab = 0

    for it1 in range(0, 3):
        for it2 in range(0, 3):
            if matrix[it1][it2] == '_':
                matrix[it1][it2] = 'o'

                moveVal = miniMax(matrix, 'x')

                moveVal2 = miniMaxAB(matrix, 'x', -9999, 9999)
                matrix[it1][it2] = '_'

                if bestVal2 > moveVal2:
                    x2 = it1
                    y2 = it2
                    bestVal2 = moveVal2

                if (bestVal > moveVal):
                    x = it1
                    y = it2
                    bestVal = moveVal
    print ("No of States Generated by Min Max", no_states)
    print ("X and Y values selected by Min Max", x, y)
    print ("No of States Generated by Min Max with pruning", no_statesab)
    print ("X and Y values selected by Min Max with pruning", x2, y2)
    return x, y


"""Printing the Game Board to User properly"""


def printMat(matrix):
    print ("-----------------------Matrix-------------------------------")
    for it1 in range(0, 3):
        print(matrix[it1][0], matrix[it1][1], matrix[it1][2])
    print ("------------------------------------------------------------")


"""This is main functions which drives the program"""
if __name__ == '__main__':
    matrix = [['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]

    print ("Human moves represented by x and Computer moves is represented o in matrix")
    print ("You are starting player")
    val = getVal(matrix)
    while val == 0 and checkMoves(matrix):
        x = int(input("Enter X Coordniate"))
        y = int(input("Enter Y Coordniate"))
        if matrix[x][y] == 'x' or matrix[x][y] == 'o':
            print ()
            print ("Wrong X and Y cordinates enter again")
            continue
        matrix[x][y] = 'x'
        x1, y1 = findBest(matrix)
        matrix[x1][y1] = 'o'
        printMat(matrix)
        val = getVal(matrix)
    if (val == 0):
        print ("Game is draw")
    elif (val == -1):
        print ("Computer won the game (dont mind it!) he is unbeatable")
    else:
        print ("Strange you won the game")
