JavaScript 中的 Tic tac toe with minimax algorithm 给出错误 maximum call stack size exceeded

Question

我正在做作业井字游戏。我的 minimax 算法本身可以很好地处理一个数组和提供的两个玩家，但是当处理 html 个 divs 的集合时，它给出了最大调用堆栈大小超过的错误。我不明白为什么会这样。通过搜索 google 我知道我的函数在某处一遍又一遍地调用自己，但无法弄清楚如何解决这个问题。我尝试将 .cells div 集合转换为数组，但仍然出现相同的错误。有人请帮我解决这个问题。谢谢。

var humanPlayer, aiPlayer;
humanPlayer = 'x';
aiPlayer = 'o';
var cells = document.querySelectorAll(".cell");

/** Tic Tac Toe game object **/
var TicTacToe = {
  checkWinner : function(arr, player){
    if(
      (arr[0] === player && arr[1] === player && arr[2] === player)||
      (arr[3] === player && arr[4] === player && arr[5] === player)||
      (arr[6] === player && arr[7] === player && arr[8] === player)||
      (arr[0] === player && arr[3] === player && arr[6] === player)||
      (arr[1] === player && arr[4] === player && arr[7] === player)||
      (arr[2] === player && arr[5] === player && arr[8] === player)||
      (arr[0] === player && arr[4] === player && arr[8] === player)||
      (arr[2] === player && arr[4] === player && arr[6] === player)
    ){
      return true;
    }
    else{
      return false;
    }
  },//checkWinner function.

  getAvailableSpots : function(arr){
    var spots = [];
    for(var i = 0; i < arr.length; i++){
      if(arr[i].textContent !== "x" && arr[i].textContent !== "o"){
        spots.push(i);
      }
    }
    return spots;
  },// getAvailableSpots function.

  minimax : function(newBoard, player){
    newBoard = Array.from(newBoard);
    var availSpots = this.getAvailableSpots(newBoard);
    if(this.checkWinner(newBoard, aiPlayer)){
      return {score: 10};
    }
    else if(this.checkWinner(newBoard, humanPlayer)){
      return {score: -10};
    }
    else if(availSpots.length === 0){
      return {score: 0};
    }

    var moves = [];

    for(var j = 0; j < availSpots.length; j++){
      var move = {};
      move.index = availSpots[j];
      newBoard[availSpots[j]] = player;
      if(player === aiPlayer){
        var result1 = this.minimax(newBoard, humanPlayer);
        move.score = result1.score;
      }
      else{
        var result2 = this.minimax(newBoard, aiPlayer);
        move.score = result2.score;
      }

      newBoard[availSpots[j]] = move.index;
      moves.push(move);
    }

    var bestMove;
    if(player === aiPlayer){
      var bestScore1 = -100000;
      for(var k = 0; k < moves.length; k++){
        if(moves[k].score > bestScore1){
          bestScore1 = moves[k].score;
          bestMove = k;
        }
      }
    }
    else{
      var bestScore2 = 100000;
      for(var l = 0; l < moves.length; l++){
        if(moves[l].score < bestScore2){
          bestScore2 = moves[l].score;
          bestMove = l;
        }
      }
    }

    return moves[bestMove];
  }// minimax function.


};//TicTacToe object literal.

function move(e){
  if(e.target.className === "cell" && e.target.textContent === ""){
    e.target.textContent = humanPlayer;
    var result = TicTacToe.minimax(cells, aiPlayer);
    cells[result.index].textContent = aiPlayer;
  }
}


document.querySelector('.cells').addEventListener('click', move);

.*{
  -webkit-box-sizing: border-box;
  -moz-box-sizing: border-box;
  box-sizing: border-box;
}
.cells  {
  width: 390px;
  height: 390px;
  margin: 50px auto;
}

.cell {
  width:128px;
  height: 128px;
  border: 1px solid #dedede;
  float: left;
  text-align: center;
  line-height: 128px;
  font-size: 80px;
  font-weight: bold;
}

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width">
  <title>JS Bin</title>
</head>
<body>

  <div class="cells">
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
  </div>
</body>
</html>

Answer 1

这是因为您的 minmax 函数是递归的，这意味着它会尝试所有可能的组合链。为了不一遍又一遍地重复相同的链，它会在每次递归时创建一个板的克隆（通过 Array.from(newBoard)）。

现在，当您使用原始数组对其进行测试时，电路板的复制工作正常。但是，现在您的 board 数组实际上包含 DOM 个对象，这些对象不会被 Array.from() 克隆。因此，您的 AI 基本上会在每次尝试导致堆栈溢出时更改单元格。

我的建议是在将当前棋盘传递给 minmax 函数之前将其转换为原始数组。

var humanPlayer, aiPlayer;
humanPlayer = 'x';
aiPlayer = 'o';
var cells = document.querySelectorAll(".cell");

/** Tic Tac Toe game object **/
var TicTacToe = {
  checkWinner : function(arr, player){
    if(
      (arr[0] === player && arr[1] === player && arr[2] === player)||
      (arr[3] === player && arr[4] === player && arr[5] === player)||
      (arr[6] === player && arr[7] === player && arr[8] === player)||
      (arr[0] === player && arr[3] === player && arr[6] === player)||
      (arr[1] === player && arr[4] === player && arr[7] === player)||
      (arr[2] === player && arr[5] === player && arr[8] === player)||
      (arr[0] === player && arr[4] === player && arr[8] === player)||
      (arr[2] === player && arr[4] === player && arr[6] === player)
    ){
      return true;
    }
    else{
      return false;
    }
  },//checkWinner function.

  getAvailableSpots : function(arr){
    var spots = [];
    for(var i = 0; i < arr.length; i++){
      if(arr[i] !== "x" && arr[i] !== "o"){
        spots.push(i);
      }
    }
    return spots;
  },// getAvailableSpots function.

  minimax : function(newBoard, player){
    newBoard = Array.from(newBoard);
    var availSpots = this.getAvailableSpots(newBoard);
    if(this.checkWinner(newBoard, aiPlayer)){
      return {score: 10};
    }
    else if(this.checkWinner(newBoard, humanPlayer)){
      return {score: -10};
    }
    else if(availSpots.length === 0){
      return {score: 0};
    }

    var moves = [];

    for(var j = 0; j < availSpots.length; j++){
      var move = {};
      move.index = availSpots[j];
      newBoard[availSpots[j]] = player;
      if(player === aiPlayer){
        var result1 = this.minimax(newBoard, humanPlayer);
        move.score = result1.score;
      }
      else{
        var result2 = this.minimax(newBoard, aiPlayer);
        move.score = result2.score;
      }

      newBoard[availSpots[j]] = move.index;
      moves.push(move);
    }

    var bestMove;
    if(player === aiPlayer){
      var bestScore1 = -100000;
      for(var k = 0; k < moves.length; k++){
        if(moves[k].score > bestScore1){
          bestScore1 = moves[k].score;
          bestMove = k;
        }
      }
    }
    else{
      var bestScore2 = 100000;
      for(var l = 0; l < moves.length; l++){
        if(moves[l].score < bestScore2){
          bestScore2 = moves[l].score;
          bestMove = l;
        }
      }
    }

    return moves[bestMove];
  }// minimax function.


};//TicTacToe object literal.

function move(e){
  if(e.target.className === "cell" && e.target.textContent === ""){
    e.target.textContent = humanPlayer;
    var result = TicTacToe.minimax(domBoardToArray(cells), aiPlayer);
    cells[result.index].textContent = aiPlayer;
  }
}

function domBoardToArray(cells){
  return Array.prototype.slice.call(cells).map(function (cell){
    return cell.textContent
  })
}


document.querySelector('.cells').addEventListener('click', move);

.*{
  -webkit-box-sizing: border-box;
  -moz-box-sizing: border-box;
  box-sizing: border-box;
}
.cells  {
  width: 390px;
  height: 390px;
  margin: 50px auto;
}

.cell {
  width:128px;
  height: 128px;
  border: 1px solid #dedede;
  float: left;
  text-align: center;
  line-height: 128px;
  font-size: 80px;
  font-weight: bold;
}

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width">
  <title>JS Bin</title>
</head>
<body>

  <div class="cells">
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
    <div class="cell"></div>
  </div>
</body>
</html>

JavaScript 中的 Tic tac toe with minimax algorithm 给出错误 maximum call stack size exceeded

Tic tac toe in JavaScript with minimax algorithm giving error maximum call stack size exceed

javascript

algorithm

callstack

tic-tac-toe

minimax