[Python] Performance Optimization for Minimax Algorithm in Tic-Tac-Toe with Variable Board...

I'm implementing a Tic-Tac-Toe game with an AI using the Minimax algorithm (with Alpha-Beta Pruning) to select optimal moves. However, I'm experiencing performance issues when the board size increases or the number of consecutive marks required to win (k) grows. The current implementation works fine for smaller board sizes (e.g., 3x3), but as I scale up the board size to larger grids (e.g., 8x12), the performance drops significantly, especially with the depth of the search.

The algorithm is running too slowly on larger boards (e.g., 6x6 or 8x12) with more complex win conditions (e.g., 4 in a row, 5 in a row).

import random
import time

# Check if a player has won
def check_win(board, player, k):
rows = len(board)
cols = len(board[0])

# Check horizontally, vertically, and diagonally
for r in range(rows):
for c in range(cols):
if c <= cols - k and all(board[r][c+i] == player for i in range(k)): # Horizontal
return True
if r <= rows - k and all(board[r+i][c] == player for i in range(k)): # Vertical
return True
if r <= rows - k and c <= cols - k and all(board[r+i][c+i] == player for i in range(k)): # Diagonal
return True
if r >= k - 1 and c <= cols - k and all(board[r-i][c+i] == player for i in range(k)): # Anti-diagonal
return True
return False

# Heuristic function to evaluate the board state
def evaluate_board(board, player, k):
# Check if the player has already won
if check_win(board, player, k):
return 1000 # Win
elif check_win(board, 3-player, k): # Opponent
return -1000 # Loss
return 0 # No winner yet

# Minimax algorithm with Alpha-Beta Pruning
def minimax(board, depth, alpha, beta, is_maximizing_player, player, k):
# Evaluate the current board state
score = evaluate_board(board, player, k)
if score == 1000 or score == -1000:
return score
if depth == 0:
return 0 # Depth limit reached

if is_maximizing_player:
best = -float('inf')
for r in range(len(board)):
for c in range(len(board[0])):
if board[r][c] == 0: # Empty cell
board[r][c] = player # Make move
best = max(best, minimax(board, depth-1, alpha, beta, False, player, k))
board[r][c] = 0 # Undo move
alpha = max(alpha, best)
if beta <= alpha:
break
return best
else:
best = float('inf')
for r in range(len(board)):
for c in range(len(board[0])):
if board[r][c] == 0: # Empty cell
board[r][c] = 3 - player # Opponent's move
best = min(best, minimax(board, depth-1, alpha, beta, True, player, k))
board[r][c] = 0 # Undo move
beta = min(beta, best)
if beta <= alpha:
break
return best

# Function to find the best move for the AI
def best_move(board, player, k):
best_val = -float('inf')
best_move = (-1, -1)
for r in range(len(board)):
for c in range(len(board[0])):
if board[r][c] == 0: # Empty cell
board[r][c] = player # Make move
move_val = minimax(board, 4, -float('inf'), float('inf'), False, player, k) # Depth 4 for searching
board[r][c] = 0 # Undo move
if move_val > best_val:
best_move = (r, c)
best_val = move_val
return best_move

# Function to play the game
def play_game(board_size=(3, 3), k=3):
board = [[0 for _ in range(board_size[1])] for _ in range(board_size[0])]
player = 1 # 1 - X, 2 - O

while True:
# Display the board
for row in board:
print(' '.join(str(x) if x != 0 else '.' for x in row))
print()

# Check if someone has won
if check_win(board, player, k):
print(f"Player {player} wins!")
break

# AI's move
if player == 1:
row, col = best_move(board, player, k)
print(f"AI (X) move: {row}, {col}")
else:
# Simple random move for player O
row, col = random.choice([(r, c) for r in range(board_size[0]) for c in range(board_size[1]) if board[r][c] == 0])
print(f"Player O move: {row}, {col}")

board[row][col] = player
player = 3 - player # Switch player

# Check for a draw
if all(board[r][c] != 0 for r in range(board_size[0]) for c in range(board_size[1])):
print("It's a draw!")
break

# Speed test function
def test_speed(board_size=(3, 3), k=3):
start_time = time.time()
play_game(board_size, k)
print(f"Game duration: {time.time() - start_time} seconds")

# Example: play on a 8x8 board, with 4 in a row to win
test_speed((8,8), 4)



I tried limiting the depth of the Minimax search to reduce the number of possibilities being evaluated. For example, I reduced the search depth to 2 for larger boards:

move_val = minimax(board, depth=2, alpha=-float('inf'), beta=float('inf'), is_maximizing_player=False, player=player, k=k)


However, this only partially mitigates the issue, and the AI's decision-making still seems too slow.

Also i explored parallelizing the move evaluation using the ThreadPoolExecutor from Python’s concurrent.futures module:

from concurrent.futures import ThreadPoolExecutor
def parallel_minimax(board, depth, alpha, beta, is_maximizing_player, player, k):
with ThreadPoolExecutor() as executor:
futures = []
for r in range(len(board)):
for c in range(len(board[0])):
if board[r][c] == 0:
board[r][c] = player
futures.append(executor.submit(minimax, board, depth-1, alpha, beta, False, player, k))
board[r][c] = 0 # Undo move
for future in futures:
result = future.result()
# [process the result]


This approach improved parallelism, but it still does not solve the underlying issue of time complexity for large boards.

Please help to make the algorithm as fast as possible

Continue reading...