I wrote a module that I intend to use in my next tic-tac-toe project. All it is is a class that stores the boardstate along with some methods/properties. The biggest thing is the minimax alg. As shown in the line profiler results below, the check_win attribute takes by far the most time out of anything in the minimax. The algorithm runs pretty quickly already (taking around a second to calculate an empty board and practically instantly for a board with any move on it already), but it would be nice to be able to speed it up a bit. Improving the check_win speed is the only specific thing I am looking for, other than just general improvements.
Edit: I forgot to mention at first, the way I implemented the minimax, instead of having one player minimize and one player maximize, both players maximize and then return the negative of their value. Also, is there any concern with creating multiple instances of the Board class in terms of Board.board being mutable?
Edit 2: Added an example usage to the code
tictactoe_framework.py:
"(tictactoe_framework.py) Module for representing a tictactoe board"
from math import cos
from random import randint
from typing import Self
from line_profiler import profile
class Board:
"""
Represents the state of a tictactoe board.
Attributes:
- self.board (list[int]): Represents the state of the board in a
9-element flat array where moves by X are represented by 1,
moves by O are represented by -1, and empty spaces are represented
by 0.
"""
def __init__(self, board: list[int] | None = None) -> None:
if board is None:
board = [0] * 9
self.board: list[int] = board
@property
@profile
def check_win(self) -> int | None:
"""
(Property) Checks all possible winning combinations of board spaces and returns
based on whether the current board state has a winner, is a draw, or
is ongoing.
Returns (int | None):
Int:
- 1 if X has won
- -1 if O has won
- 0 if game is a draw
None:
- None if game is ongoing
"""
win_indices: list[list[int]] = [
[0, 1, 2], [3, 4, 5], [6, 7, 8], # Rows
[0, 3, 6], [1, 4, 7], [2, 5, 8], # Columns
[0, 4, 8], [2, 4, 6], # Diagonals
]
for win_condition in win_indices:
line_sum = (self.board[win_condition[0]]
+ self.board[win_condition[1]]
+ self.board[win_condition[2]])
if abs(line_sum) == 3:
return line_sum // 3
if 0 in self.board:
return None
return 0
@property
def player_to_move(self) -> int:
"""
(Property) Determines which player's turn it is to move by finding
the parity of the total number of moves.
Returns (int):
- 1 if player X is to move
- -1 if player O is to move
"""
num_of_moves: int = sum(abs(space) for space in self.board)
if num_of_moves % 2 == 0:
return 1
return -1
@property
def ideal_move(self) -> int | None:
"""
(Property) Determines the ideal move for the current player using the minimax algorithm.
Returns (int | None):
Int:
- The index of the ideal move if the game has not ended yet
None:
- None if the game has already ended
"""
@profile
def minimax(board: Board = self, depth: int = 0) -> int | None:
win_state: int | None = board.check_win
if (not depth) and (win_state is not None):
return None
if (depth) and (win_state is not None):
return -1 * win_state * board.player_to_move
if win_state is None:
move_list: list[int] = []
for idx, state in enumerate(board.board):
if not state:
move_list.append(idx)
value_list: list[int | None] = [0 for _ in move_list]
for idx, move in enumerate(move_list):
board.move(move)
value_list[idx] = minimax(board, depth + 1)
board.board[move] = 0
if depth:
return -1 * max(i for i in value_list if i is not None)
max_value: int = max(i for i in value_list if i is not None)
max_indices: list[int] = [
idx for idx, val in enumerate(value_list) if max_value == val
]
board_state_int: int = sum(
(2**j) * abs(board.board[j]) + 4 for j in range(len(value_list))
)
board_state_seed: int = (
int(100 * abs(cos(board_state_int)) % len(max_indices)) - 1
)
return move_list[max_indices[board_state_seed]]
return depth
return minimax()
def move(self, space: int | None) -> None:
"""
Plays a move in a space on the board. Raises an error if the move is not valid.
Returns:
None
"""
if space is not None:
try:
assert self.board[space] == 0
self.board[space] = self.player_to_move
except AssertionError:
print(
"ERROR: Invalid Move\n"
f"Boardstate: {self.board}\n"
f"Attempted move: {space}"
)
def __str__(self) -> str:
disp_dict: dict[int, str] = {0: " ", 1: "X", -1: "O"}
disp_board: list[str] = [disp_dict[space] for space in self.board]
disp_string: str = (
f"-----\n"
f"{disp_board[0]} {disp_board[1]} {disp_board[2]}\n"
f"{disp_board[3]} {disp_board[4]} {disp_board[5]}\n"
f"{disp_board[6]} {disp_board[7]} {disp_board[8]}\n"
f"-----"
)
return disp_string
@classmethod
def random(cls) -> Self:
"""
Creates an instance of the class with board state with a
random number of moves made by both players.
Returns (Self):
- An instance of Board representing a random boardstate
"""
num_of_moves: int = randint(0, 8)
random_board: Self = cls()
for _ in range(num_of_moves):
while True:
move: int = randint(0, 8)
if random_board.board[move] == 0:
random_board.board[move] = random_board.player_to_move
if random_board.check_win is None:
break
return random_board
if __name__ == "__main__":
x = Board()
print(x)
while x.check_win is None:
x.move(x.ideal_move)
print(x)
Line profiler results for check_win and minimax:
Timer unit: 1e-06 s
Total time: 0.0001395 s
File: tictactoe_framework.py
Function: minimax at line 85
Line # Hits Time Per Hit % Time Line Contents
==============================================================
85 @profile
86 def minimax(board: Board = self, depth: int = 0) -> int | None:
87 2 81.7 40.9 58.6 win_state: int | None = board.check_win
88
89 2 0.6 0.3 0.4 if (not depth) and (win_state is not None):
90 return None
91 2 0.6 0.3 0.4 if (depth) and (win_state is not None):
92 1 9.5 9.5 6.8 return -1 * win_state * board.player_to_move
93 1 0.2 0.2 0.1 if win_state is None:
94 1 0.3 0.3 0.2 move_list: list[int] = []
95 10 5.4 0.5 3.9 for idx, state in enumerate(board.board):
96 9 3.0 0.3 2.2 if not state:
97 1 0.9 0.9 0.6 move_list.append(idx)
98
99 2 1.2 0.6 0.9 value_list: list[int | None] = [0 for _ in move_list]
100 2 1.2 0.6 0.9 for idx, move in enumerate(move_list):
101 1 15.4 15.4 11.0 board.move(move)
102 1 2.0 2.0 1.4 value_list[idx] = minimax(board, depth + 1)
103 1 0.6 0.6 0.4 board.board[move] = 0
104
105 1 0.4 0.4 0.3 if depth:
106 return -1 * max(i for i in value_list if i is not None)
107 1 3.3 3.3 2.4 max_value: int = max(i for i in value_list if i is not None)
108 2 0.8 0.4 0.6 max_indices: list[int] = [
109 2 1.3 0.7 0.9 idx for idx, val in enumerate(value_list) if max_value == val
110 ]
111 2 4.2 2.1 3.0 board_state_int: int = sum(
112 1 1.1 1.1 0.8 (2**j) * abs(board.board[j]) + 4 for j in range(len(value_list))
113 )
114 1 0.3 0.3 0.2 board_state_seed: int = (
115 1 4.2 4.2 3.0 int(100 * abs(cos(board_state_int)) % len(max_indices)) - 1
116 )
117 1 1.3 1.3 0.9 return move_list[max_indices[board_state_seed]]
118
119 return depth
Total time: 10.0331 s
File: tictactoe_framework.py
Function: check_win at line 26
Line # Hits Time Per Hit % Time Line Contents
==============================================================
26 @property
27 @profile
28 def check_win(self) -> int | None:
29 """
30 (Property) Checks all possible winning combinations of board spaces and returns
31 based on whether the current board state has a winner, is a draw, or
32 is ongoing.
33
34 Returns (int | None):
35 Int:
36 - 1 if X has won
37 - -1 if O has won
38 - 0 if game is a draw
39 None:
40 - None if game is ongoing
41 """
42 618208 181935.5 0.3 1.8 win_indices: list[list[int]] = [
43 618208 245636.1 0.4 2.4 [0, 1, 2], [3, 4, 5], [6, 7, 8], # Rows
44 618208 208033.1 0.3 2.1 [0, 3, 6], [1, 4, 7], [2, 5, 8], # Columns
45 618208 178003.1 0.3 1.8 [0, 4, 8], [2, 4, 6], # Diagonals
46 ]
47 4570613 1416790.5 0.3 14.1 for win_condition in win_indices:
48 12561585 3763096.5 0.3 37.5 line_sum = (self.board[win_condition[0]]
49 4187195 1087555.1 0.3 10.8 + self.board[win_condition[1]]
50 4187195 1090959.8 0.3 10.9 + self.board[win_condition[2]])
51 4187195 1401266.0 0.3 14.0 if abs(line_sum) == 3:
52 234790 129333.6 0.6 1.3 return line_sum // 3
53 383418 132961.0 0.3 1.3 if 0 in self.board:
54 331273 170638.7 0.5 1.7 return None
55 52145 26844.3 0.5 0.3 return 0
0.00 seconds - tictactoe_framework.py:85 - minimax
10.03 seconds - tictactoe_framework.py:26 - check_win
mainso we can run this. \$\endgroup\$