JavaScript中的Tic tac toe使用minimax算法，错误最大调用堆栈大小超过

问题描述 投票：2回答：1

我正在做一个任务tic tac toe游戏。我的minimax算法可以自行运行，并且有一个数组和两个提供的播放器，但是当使用div的html集合时，它会给出一个最大调用堆栈大小超过的错误。我不明白为什么会这样。通过搜索谷歌我知道我的功能在一个地方一遍又一遍地调用自己，但无法弄清楚该做什么来解决这个问题。我尝试将.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>
javascript algorithm tic-tac-toe callstack minimax
1个回答
4
投票

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

现在，当您使用primitve数组进行测试时，复制板的工作正常。但是，现在你的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>
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.