I'm trying to write the minimax algorithm in Javascript for a tic-tac-toe game project. It's a person vs computer game. I want to find the best move for the computer but I keep getting the following error on the Chrome console: Uncaught RangeError: Maximum call stack size exceeded.
I've tried to solve the problem many different ways but it has become hard for me to debug.
If anyone could help it would be appreciated, thanks in advance.
Here is my sample code:
let board_index = ["X", 1, 2, 3, "O", 5, 6, "X", 8]; // original board with the somes indexies played
let ai = "X";
let hu = "O";
// filter the available boxes in the board
function emptySpot(board) {
return board.filter(st => st != "O" && st != "X");
}
// winning combinations using the board indexies
function evaluate(board, player) {
if (
(board[0] == player && board[1] == player && board[2] == player) ||
(board[3] == player && board[4] == player && board[5] == player) ||
(board[6] == player && board[7] == player && board[8] == player) ||
(board[0] == player && board[3] == player && board[6] == player) ||
(board[1] == player && board[4] == player && board[7] == player) ||
(board[2] == player && board[5] == player && board[8] == player) ||
(board[0] == player && board[4] == player && board[8] == player) ||
(board[2] == player && board[4] == player && board[6] == player)
)
{
if(player == ai) {
return 10;
}
else
if(player == hu) {
return -10;
}
return 0;
}
}
// minimax algorithm
function minimax(board, depth, isMax) {
// available spots in board
let avail = emptySpot(board);
// evaluate score on board
let score = evaluate(board);
// check and return a value for terminal states such as win, lose, and tie
if(score == 10 || score == -10) {
return score;
}
else if(avail == []) {
return 0;
}
if(isMax) {
let bestScore = -1000;
for(let i = 0; i < avail.length; i++) {
let index = avail[i];
// make move
avail[i] = ai;
// call minimax recursively and choose the maximum value
bestScore = minimax(board, depth+1, !isMax);
// undo the move
avail[i] = index;
}
return bestScore;
}
else {
let bestScore = 1000;
for(let i = 0; i < avail.length; i++) {
let index = avail[i];
// make move
avail[i] = hu;
// call minimax recursively and choose the minimum value
bestScore = minimax(board, depth+1, !isMax);
// undo the move
avail[i] = index;
}
return bestScore;
}
}
// finding the best possible move and return it
function findBestMove(board) {
let bestVal = -1000;
let bestMove = -1;
let avail = emptySpot(board);
for(let i = 0; i < avail.length; i++) {
// save index
let index = avail[i];
// compute the evalutation for this move
let moveVal = minimax(board, 0, false);
// undo move
avail[i] = index;
if(moveVal > bestVal){
bestVal = moveVal;
bestMove = avail[i];
}
}
console.log(bestVal);
console.log(bestMove);
}
let bestSpot = findBestMove(board_index);