"""
### The unbeatable tic-tac-toe game
The following piece of code uses adversarial search to create an artificially intelligent opponent that always tries to win or draw a tic tac toe game.
"""
"""
First, we import required components
"""
from math import inf
"""
Then, we initialize a bunch of winning states. These states let us know the board configuration that contains a winning state
"""
WINNING_STATES = [
    0b111000000,
    0b000111000,
    0b000000111,
    0b100100100,
    0b010010010,
    0b001001001,
    0b100010001,
    0b001010100,
]
"""
Next, let's create our players, I am color-coding them for ease of recognition in the program output
"""
playerX = "\033[32mX\033[39m"
playerO = "\033[33mO\033[39m"
"""
Now we create the `TicTacToe` class to hold the logic of the game
"""
class InvalidMoveException(Exception):
    pass


class TicTacToe:

    def __init__(self):
        self.board = [
            "1", "2", "3",
            "4", "5", "6",
            "7", "8", "9",
        ]

        self.players = [playerX, playerO]
        self.no_of_moves_played = 0

    def play(self, box: int):
        next_player_index = self.no_of_moves_played % 2
        self._act(self.players[next_player_index], box)
        self.no_of_moves_played += 1

        if self._terminal(self.board):
            print("game terminated")
            exit()

    def ai_turn(self):
        next_player_index = self.no_of_moves_played % 2

        player = self.players[next_player_index]

        action = self._minimax([*self.board], player)
        self._act(player, action[1])
        self.no_of_moves_played += 1

        if self._terminal(self.board):
            print("game terminated")
            exit()

    def _get_box(self, box: int) -> str:
        return self.board[box - 1]

    def _set_box(self, box: int, value: str):
        self.board[box - 1] = value

    def _act(self, player: str, box: int):
        if self._get_box(box) in self.players:
            raise InvalidMoveException("Invalid move")
        self._set_box(box, player)
        print(f"player {player} has acted in box {box}")

    def _get_available_moves(self, board: list) -> list:
        return [int(box) for box in filter(lambda box: box not in self.players, board)]

    def _terminal(self, board: list) -> bool:
        if all([box in self.players for box in board]):
            return True

        if board.count(self.players[0]) < 3 and board.count(self.players[1]) < 3:
            return False

        return self._winning(playerX, board) or self._winning(playerO, board)

    def _get_binary_state(self, player: str, board: list) -> int:
        state = 0b0

        for i in range(0, len(board)):
            if board[i] == player:
                state += 2 ** i
        return state

    def _minimax(self, board: list, player: str):
        available_moves = self._get_available_moves(board)
        if self._winning(playerX, board):
            return 1, None
        elif self._winning(playerO, board):
            return -1, None
        elif len(available_moves) == 0:
            return 0, None

        actions = []

        for available_move in available_moves:
            board_to_update = [*board]
            board_to_update[available_move - 1] = player

            if player == playerX:
                action = self._minimax(board_to_update, playerO)
            else:
                action = self._minimax(board_to_update, playerX)

            actions.append((action[0], available_move))

        if player == playerX:
            best_score = -inf
            best_move = None

            for (score, available_move) in actions:
                if score > best_score:
                    best_score, best_move = score, available_move
            return best_score, best_move
        else:
            best_score = inf
            best_move = None

            for (score, available_move) in actions:
                if score < best_score:
                    best_score, best_move = score, available_move
            return best_score, best_move

    def _winning(self, player: str, board: list):
        player_state = self._get_binary_state(player, board)

        for winning_state in WINNING_STATES:
            if player_state & winning_state == winning_state:
                return True
        return False

    def __str__(self):
        return (f"{self._get_box(1)} | {self._get_box(2)} | {self._get_box(3)}\n"
                f"---------\n"
                f"{self._get_box(4)} | {self._get_box(5)} | {self._get_box(6)}\n"
                f"---------\n"
                f"{self._get_box(7)} | {self._get_box(8)} | {self._get_box(9)}")
if __name__ == '__main__':
    game = TicTacToe()

    i = 0
    while i < 9:
        try:
            if game.players[i % 2] == playerO:
                game.ai_turn()
            else:
                box_number = int(input(f"Player {game.players[i % 2]} turn to play: "))
                game.play(box_number)
            i += 1
        except InvalidMoveException as e:
            print(e.args[0])
        finally:
            print(game)