I have tried to impliment the minimax algorithm with alpha/beta pruning for a TicTacToe game I'm making in the Godot Engine, however, it doesn't seem to work as expected. The AI seems to always pick the next available spot on the board from left to right. Can anyone let me know where I might have gone wrong?
Here's my code:
func winner_score() -> int:
# 0 is X, 1 is Y
if board.won(0)[0]: return -10
elif board.won(1)[0]: return 10
else: return 0
func minimax(_board, _depth: int, alpha, beta, maximizingPlayer: bool):
var result = winner_score()
if _depth == 0 or result != 0:
return result
if maximizingPlayer:
var maxEval: int = -100
for row in range(board.size):
for col in range(board.size):
var square = _board[row][col]
if square.type == null:
square.type = HUMAN
var eval: int = minimax(_board, _depth - 1, alpha, beta, false)
square.type = null
maxEval = max(maxEval, eval)
alpha = max(alpha, eval)
if beta <= alpha: break
return maxEval
else:
var minEval = 100
for row in range(board.size):
for col in range(board.size):
var square = _board[row][col]
if square.type == null:
square.type = AI
var eval: int = minimax(_board, _depth - 1, alpha, beta, true)
square.type = null
minEval = min(minEval, eval)
beta = min(beta, eval)
if beta <= alpha: break
return minEval