0

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);
  • What's the purpose of `depth` variable? – MinusFour Oct 13 '17 at 01:17
  • Maybe this post will be useful to you:[**maximum-call-stack-size-exceeded-error**](https://stackoverflow.com/questions/6095530/maximum-call-stack-size-exceeded-error) – NewToJS Oct 13 '17 at 01:27
  • Don't know if it is *the* problem, but `if(avail == [])` is certainly *a* problem in that that condition will never be true. Used with arrays (or other objects), the `==` operator tests whether its operands refer to the same array, not whether they refer to two arrays with the same elements. If you're trying to test if the array is empty, test `if (avail.length === 0)`. – nnnnnn Oct 13 '17 at 02:18
  • In addition to what nnnnn said, you re-calculate the available slots eachtime from `board`, but `board` never changes. The assignments to `avail[i]` should be to `board[index]`. The way your loops work, your `bestScore` will always be that of the last available slot; you must find the min/max of the current score and the best score. In addition to the best Score you should also keep track of the associated grid cell. You don't pass the player to `evaluate`, which means your score is always 0, and you never return anything from `findBestMove` . – M Oehm Oct 13 '17 at 10:30
  • @M-Oehm, I think it makes a lot of sense for me now. I've fixed some of the bugs but my code is still not working, properly :( I''m trying to implement the solutions you mentioned. I will re-update my post later. Hope you guys can check it. – Wadson Fourrien Oct 13 '17 at 16:48
  • @nnnnnn I fixed the avail == [] . That was stupid from my part, hahah – Wadson Fourrien Oct 13 '17 at 16:49

0 Answers0