# Showing optimal AI strategy for playing tic-tac-toe by using minmax function
# With alpha-beta pruning implementation:
# You can for example see that its now much faster in deciding the first move.

import time  # for measuring time of evaluation


class Game:
    def __init__(self):
        self.initialize_game()

    def initialize_game(self):
        self.current_state = [[".", ".", "."], [".", ".", "."], [".", ".", "."]]

        # Player X always plays first
        self.player_turn = "X"

    def draw_board(self):
        for i in range(0, 3):
            for j in range(0, 3):
                print("{}|".format(self.current_state[i][j]), end=" ")
            print()
        print()

    # A game loop for actual playing:
    def play_alpha_beta(self):
        while True:
            self.draw_board()
            self.result = self.is_end()

            # Printing the appropriate message if the game has ended
            if self.result != None:
                if self.result == "X":
                    print("The winner is X!")
                elif self.result == "O":0
                    print("The winner is O!")
                elif self.result == ".":
                    print("It's a tie!")

                self.initialize_game()
                return

            # If it's player's turn
            if self.player_turn == "X":

                while True:

                    start = time.time()
                    (m, qx, qy) = self.min_alpha_beta(-2, 2)
                    end = time.time()
                    print("Evaluation time: {}s".format(round(end - start, 7)))
                    print("Recommended move: X = {}, Y = {}".format(qx, qy))

                    px = int(input("Insert the X coordinate: "))
                    py = int(input("Insert the Y coordinate: "))

                    qx = px
                    qy = py

                    if self.is_valid(px, py):
                        self.current_state[px][py] = "X"
                        self.player_turn = "O"
                        break
                    else:
                        print("The move is not valid! Try again.")

            # If it's AI's turn
            else:
                (m, px, py) = self.max_alpha_beta(-2, 2)
                self.current_state[px][py] = "O"
                self.player_turn = "X"

    # Checking is move is legal
    def is_valid(self, px, py):
        if px < 0 or px > 2 or py < 0 or py > 2:
            return False
        elif self.current_state[px][py] != ".":
            return False
        else:
            return True

    # Checking if game has ended (a player can win by connecting three consecutive symbols in either a horizontal,
    # diagonal or vertical line.)

    def is_end(self):
        # Vertical win
        for i in range(0, 3):
            if (
                self.current_state[0][i] != "."
                and self.current_state[0][i] == self.current_state[1][i]
                and self.current_state[1][i] == self.current_state[2][i]
            ):
                return self.current_state[0][i]

        # Horizontal win
        for i in range(0, 3):
            if self.current_state[i] == ["X", "X", "X"]:
                return "X"
            elif self.current_state[i] == ["O", "O", "O"]:
                return "O"

        # Main diagonal win
        if (
            self.current_state[0][0] != "."
            and self.current_state[0][0] == self.current_state[1][1]
            and self.current_state[0][0] == self.current_state[2][2]
        ):
            return self.current_state[0][0]

        # Second diagonal win
        if (
            self.current_state[0][2] != "."
            and self.current_state[0][2] == self.current_state[1][1]
            and self.current_state[0][2] == self.current_state[2][0]
        ):
            return self.current_state[0][2]

        # Is whole board full?
        for i in range(0, 3):
            for j in range(0, 3):
                # There's an empty field, we continue the game
                if self.current_state[i][j] == ".":
                    return None

        # It's a tie!
        return "."

    # The AI we play with is seeking to maximize its own score and to minimize ours.
    # max() method is used for the AIs optimal decision making:

    def max_alpha_beta(self, alpha, beta):
        maxv = -2
        px = None
        py = None

        result = self.is_end()

        if result == "X":
            return (-1, 0, 0)
        elif result == "O":
            return (1, 0, 0)
        elif result == ".":
            return (0, 0, 0)

        for i in range(0, 3):
            for j in range(0, 3):
                if self.current_state[i][j] == ".":
                    self.current_state[i][j] = "O"
                    (m, min_i, min_j) = self.min_alpha_beta(alpha, beta)
                    if m > maxv:
                        maxv = m
                        px = i
                        py = j
                    self.current_state[i][j] = "."

                    # Next two ifs show the difference between regular algo and minimax
                    if maxv >= beta:
                        return (maxv, px, py)
                    if maxv > alpha:
                        alpha = maxv

        return (maxv, px, py)

    # Then we will also need a min() method for help us minimize AIs score!

    def min_alpha_beta(self, alpha, beta):
        minv = 2
        qx = None
        qy = None

        result = self.is_end()

        if result == "X":
            return (-1, 0, 0)
        elif result == "O":
            return (1, 0, 0)
        elif result == ".":
            return (0, 0, 0)

        for i in range(0, 3):
            for j in range(0, 3):
                if self.current_state[i][j] == ".":
                    self.current_state[i][j] = "X"
                    (m, max_i, max_j) = self.max_alpha_beta(alpha, beta)
                    if m < minv:
                        minv = m
                        qx = i
                        qy = j
                    self.current_state[i][j] = "."

                    if minv <= alpha:
                        return (minv, qx, qy)
                    if minv < beta:
                        beta = minv

        return (minv, qx, qy)


# For starting the game
def main():
    g = Game()
    g.play_alpha_beta()


if __name__ == "__main__":
    main()
