I have been developing a Tic-Tac-Toe AI system that uses the Alpha-Beta Pruning Minimax algorithm to determine the best move for the AI player (X) on the game board. Unfortunately, I am running into an issue where the algorithm is not returning the correct optimal move index.
According to my calculations, the ideal move for the AI player should be at index 4. However, when I run the minimax function, it returns bestAIMove.index = 8 instead.
Below is the code snippet I have been working on:
let humanPlayer = "O";
let aiPlayer = "X";
let origBoard = ["X", "O", 2, "X", 4, 5, "O", 7, 8];
let MAX = {index: 99, score: 1000};
let MIN = {index: 99, score: -1000}
let fc = 0;
function checkAvailableMoves(board) {
return board.filter(s => s !== "O" && s !== "X");
}
function winning(board, player) {
const winningCombinations = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8],
[0, 3, 6],
[1, 4, 7],
[2, 5, 8],
[0, 4, 8],
[2, 4, 6]
];
return winningCombinations.some(combination =>
combination.every(cell => board[cell] === player)
);
}
function max(a,b) {return a.score > b.score ? a : b;}
function min(a,b) {return a.score < b.score ? a : b;}
function minimax(newBoard, depth, player, alpha, beta) {
const availableMoves = checkAvailableMoves(newBoard);
let theBestMove = {};
fc++
if (winning(newBoard, humanPlayer)) {return { score: -10 + depth }}
else if (winning(newBoard, aiPlayer)) {return { score: 10 - depth }}
else if (availableMoves.length === 0) {return { score: 0 }};
if (player === aiPlayer) {
for (let i = 0; i < availableMoves.length; i++) {
const index = availableMoves[i];
newBoard[index] = player;
let result = minimax(newBoard, depth + 1, humanPlayer, alpha, beta);
result.index = index;
alpha = max(alpha,result)
newBoard[index] = index;
if (alpha.score >= beta.score) {break}
}
theBestMove = alpha;
} else if (player === humanPlayer) {
for (let i = 0; i < availableMoves.length; i++) {
const index = availableMoves[i];
newBoard[index] = player;
let result = minimax(newBoard, depth + 1, aiPlayer, alpha, beta);
result.index = index;
beta = min(beta, result);
newBoard[index] = index;
if (alpha.score >= beta.score){break}
}
theBestMove = beta;
}
return theBestMove;
}
bestAIMove = minimax(origBoard,0,aiPlayer,MIN,MAX)
console.log(bestAIMove)
console.log(fc)
Could you please help me identify what might be causing this problem?