Tic Tac Toe in Python with Alpha Beta Pruning and Minimax

tic_tac_toe.py

# https://stackabuse.com/minimax-and-alpha-beta-pruning-in-python/
# Changes include:
# 1. Reducing the amount of code for looking for end of the game
# 2. Allow for boards of N size. But the game is impossible to play
#    because it takes too long to find the optimial moves even with
#    alpha beta pruning.

import time
from collections import namedtuple
from typing import List, Tuple, Optional

Point = namedtuple("Point", ["row", "col"])


class Game:
    def __init__(self, size=3):
        self.state: List[List[str]] = [['.'] * size for _ in range(size)]
        self.width: int = len(self.state[0])
        self.height: int = len(self.state)

    def print(self) -> None:
        for row in self.state:
            print("|".join(row))

    def is_valid(self, point: Point) -> bool:
        if point.row < 0 or point.col < 0 \
           or point.row >= self.height or point.col >= self.width:
            return False
        elif self.state[point.row][point.col] != '.':
            return False
        else:
            return True

    def is_end(self) -> str:
        # Vertical win
        for col in range(self.width):
            check = set(self.state[row][col] for row in range(self.height))
            if "." not in check and len(check) == 1:
                return check.pop()

        # Horizontal win
        for row in range(self.height):
            check = set(self.state[row])
            if "." not in check and len(check) == 1:
                return check.pop()

        # Diagonal win
        check = set(self.state[row][row] for row in range(self.height))
        if "." not in check and len(check) == 1:
            return check.pop()

        # Diagonal win
        check = set(self.state[row][self.height-1-row]
                    for row in range(self.height))
        if "." not in check and len(check) == 1:
            return check.pop()

        # Continue the game
        check = set()
        for state_row in self.state:
            check.update(state_row)
        if '.' in check:
            return "C"

        # Tie
        return "T"

    def minmax(self, maximizing_robot=False) -> Tuple[int, Optional[Point]]:
        result = self.is_end()
        if result == 'X':
            # Player win so -1
            return (-1, None)
        elif result == 'O':
            # Robot win so 1
            return (1, None)
        elif result == 'T':
            # Tie so 0
            return (0, None)

        if maximizing_robot:
            # -2 is so it always updates
            max_value = -2
            max_point = None
            for row in range(self.height):
                for col in range(self.width):
                    if self.state[row][col] == '.':
                        self.state[row][col] = 'O'

                        value, _ = self.minmax(False)
                        if max_value < value:
                            max_value = value
                            max_point = Point(row, col)

                        self.state[row][col] = '.'
            return max_value, max_point
        else:
            min_value = 2
            min_point = None
            for row in range(self.height):
                for col in range(self.width):
                    if self.state[row][col] == '.':
                        self.state[row][col] = 'X'

                        value, _ = self.minmax(True)
                        if min_value > value:
                            min_value = value
                            min_point = Point(row, col)

                        self.state[row][col] = '.'
            return min_value, min_point

    def minmax_alphabeta(self, alpha=-2, beta=2, maximizing_robot=False) -> \
            Tuple[int, Optional[Point]]:
        # The only difference between this and minmax is if state to exit
        # early and to update alpha and beta
        result = self.is_end()
        if result == 'X':
            # Player win so -1
            return (-1, None)
        elif result == 'O':
            # Robot win so 1
            return (1, None)
        elif result == 'T':
            # Tie so 0
            return (0, None)

        if maximizing_robot:
            # -2 is so it always updates
            max_value = -2
            max_point = None
            for row in range(self.height):
                for col in range(self.width):
                    if self.state[row][col] == '.':
                        self.state[row][col] = 'O'

                        value, _ = self.minmax_alphabeta(alpha, beta, False)
                        if max_value < value:
                            max_value = value
                            max_point = Point(row, col)

                        self.state[row][col] = '.'

                        if max_value >= beta:
                            return max_value, max_point
                        if max_value > alpha:
                            alpha = max_value
            return max_value, max_point
        else:
            min_value = 2
            min_point = None
            for row in range(self.height):
                for col in range(self.width):
                    if self.state[row][col] == '.':
                        self.state[row][col] = 'X'

                        value, _ = self.minmax_alphabeta(alpha, beta, True)
                        if min_value > value:
                            min_value = value
                            min_point = Point(row, col)

                        self.state[row][col] = '.'

                        if min_value <= alpha:
                            return min_value, min_point
                        if min_value < beta:
                            beta = min_value
            return min_value, min_point

    def play(self):
        player_turn = "X"
        while True:
            self.print()
            result = self.is_end()

            if result != "C":
                if result == "X":
                    print("Winner is X")
                elif result == "O":
                    print("Winner is O")
                elif result == "T":
                    print("Game is a tie!")
                return

            if player_turn == "X":
                while True:
                    start_time = time.time()
                    # _, minp = self.minmax(False)
                    _, minp = self.minmax_alphabeta()
                    end_time = time.time()
                    print(
                        f"Evaluation time: {round(end_time - start_time, 2)}")
                    print(f"Recommended move: {minp}")

                    row = int(input("Insert row: "))
                    col = int(input("Insert col: "))

                    if self.is_valid(Point(row, col)):
                        self.state[row][col] = 'X'
                        player_turn = 'O'
                        break
                    else:
                        print("Move not valid")
            else:
                # _, maxp = self.minmax(True)
                _, maxp = self.minmax_alphabeta(maximizing_robot=True)
                self.state[maxp.row][maxp.col] = 'O'
                player_turn = 'X'


if __name__ == "__main__":
    # Even with alpha beta pruning, it's still impossible
    # to play boards that are above 3
    game = Game(3)
    game.play()

I made changes to the original code to allow for boards of N size but it turns out it was useless since using alpha-beta pruning on boards of size 4 is a bad idea. It takes too long to process and it turns out you need fancier methods to get it to work.

https://stackoverflow.com/questions/51427156/how-to-solve-tic-tac-toe-4x4-game-using-minimax-algorithem-and-alpha-beta-prunin