在 Javascript 中使用极小极大算法解决 TicTacToe

let _board = [[null, null, null], [null, null, null], [null, null, null]];
   let _flag = true;
   let _AIrowIndex = null;
   let _AIcellIndex = null;
   const _wrapper = document.querySelector(".wrapper");

   const _changeTurn = function () {
       if (_flag == true) {
           _flag = false;
           return playerOne.getSign();
       } else {
           _flag = true;
           return playerTwo.getSign();
       }
   };

   const _displayTurn = function () {
       let turn = document.querySelector(".playerInfo__turn")
       if (_flag == true) {
           turn.innerHTML = `${playerOne.getName()} is your turn`;
       } else {
           turn.innerHTML = `${playerTwo.getName()} is your turn`;
       }
   };

   
   const _evaluation = (winner) => {
           if(winner == "X"){
               return 1;
           }else if(winner == "O"){
               return -1;
           }
           else{
               return null;
           }
   };

   const _evaluationFunction = function (board) {
               /*CHECK 1 DIAG*/
           if (board[0][0] === board[1][1] && board[2][2] === board[0][0]) {
               return _evaluation(board[0][0]);
               /*CHECK 2 DIAG*/
           } 
           if (board[0][2] === board[1][1] && board[2][0] === board[0][2]) {
               return _evaluation(board[0][2]);
               /*CHECK PAIR*/
           } 
           for (let col = 0; col < 3; col++) {
               if (board[0][col] === board[1][col] && board[1][col] === board[2][col]) {
                   return _evaluation(board[0][col]);
               }
           }
           for (let row = 0; row < 3; row++) {
               if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
                   return _evaluation(board[row][0]);
               }
           }
           return 0;        
   };

   const minimax = (_board, depth, isMaximizer) => {

       let result = _evaluationFunction(_board);
       console.log(result);
       if (result !== null) {
           return result;
       }

       if (isMaximizer) {
           let bestScore = -Infinity;

           for (let i = 0; i < 3; i++) {
               for (let j = 0; j < 3; j++) {
                   if (_board[i][j] == null) {
                       _board[i][j] = playerOne.getSign();
                       let score = minimax(_board, depth + 1, false);
                       _board[i][j] = null;
                       bestScore = Math.max(score, bestScore);
                   }
               }

           }
           return bestScore;

       } else {
           let bestScore = Infinity;

           for (let i = 0; i < 3; i++) {
               for (let j = 0; j < 3; j++) {
                   if (_board[i][j] == null) {
                       _board[i][j] = playerTwo.getSign();
                       let score = minimax(_board, depth + 1, true);
                       _board[i][j] = null;
                       bestScore = Math.min(score, bestScore);
                   }
               }
           }
           return bestScore;
       }
   };
   
   const _setAIPlay = () => {
       
       let bestScore = Infinity;
       let bestMove;

       for (let i = 0; i < 3; i++) {
           for (let j = 0; j < 3; j++) {
               if (_board[i][j] == null) {
                   _board[i][j] = playerTwo.getSign();
                   let score = minimax(_board, 0, true);       
                   _board[i][j] = null;
                   if(score < bestScore){
                       bestScore = score;
                       console.log(bestScore);
                       bestMove = {i, j}
                   }
               }
           }
       };

       _board[bestMove.i][bestMove.j] = playerTwo.getSign();
       _AIrowIndex = bestMove.i;
       _AIcellIndex = bestMove.j;
       _displayAIPlay(_AIrowIndex, _AIcellIndex);
       _changeTurn();
       _checkWinner();
   };

   


   const _displayAIPlay = (rowIndex, cellIndex) => {
       let AIcell = document.querySelector(`[data-row="${rowIndex}"][data-cell="${cellIndex}"]`);
       AIcell.textContent = playerTwo.getSign();
   }

我试图用极小极大算法解决这个井字游戏问题，但我不明白为什么它继续将“O”放在相邻的单元格中，我试图console.log()结果，以及 minimax 函数内的最佳分数，看起来递归正在工作，但我不明白为什么里面_setAIPlay()

if I console.log(bestScore)在最后if声明它返回我作为最终值或0 or 1并不是-1在这种情况下，我认为这应该是作为最小化器的最佳分数。

如果需要，您可以在这里找到完整的存储库gitHub

以下是 JavaScript 中 Tic Tac Toe 的极小极大算法的简单实现。搜索树不断加深，直到检测到游戏结束状态。如果检测到获胜，则当前玩家无法玩游戏，因此静态值为负数 (-10)。如果检测到平局，则返回值为 0。

在所有其他情况下，搜索都会加深。此实现使用极小极大算法，其中两个玩家的值都最大化。因此，从更深入的评估中返回的价值符号总是会翻转（“对我的对手有利的对我不利，反之亦然”）。

如果发现棋盘有获胜位置，则导致获胜的棋步shortest通往胜利的道路是优先考虑的。这是通过每次回溯将绝对值降低 1 个点来实现的。

如果有多个动作具有相同的值，那么将从这些动作中随机选择一个。

下面是带有一些基本 HTML 的实现：

class TicTacToe {
    constructor() {
        this.board = Array(9).fill(0); // 0 means "empty"
        this.moves = [];
        this.isWin = this.isDraw = false;
    }
    get turn() { // returns 1 or 2
        return 1 + this.moves.length % 2;
    }
    get validMoves() {
        return [...this.board.keys()].filter(i => !this.board[i])
    }
    play(move) { // move is an index in this.board
        if (this.board[move] !== 0 || this.isWin) return false; // invalid move
        this.board[move] = this.turn; // 1 or 2
        this.moves.push(move);
        // Use regular expression to detect any 3-in-a-row
        this.isWin = /^(?:...)*([12])\1\1|^.?.?([12])..\2..\2|^([12])...\3...\3|^..([12]).\4.\4/.test(this.board.join(""));
        this.isDraw = !this.isWin && this.moves.length === this.board.length;
        return true;
    }
    takeBack() {
        if (this.moves.length === 0) return false; // cannot undo
        this.board[this.moves.pop()] = 0;
        this.isWin = this.isDraw = false;
        return true;
    }
    minimax() {
        if (this.isWin) return { value: -10 };
        if (this.isDraw) return { value: 0 };
        let best = { value: -Infinity };
        for (let move of this.validMoves) {
            this.play(move);
            let {value} = this.minimax();
            this.takeBack();
            // Reduce magnitude of value (so shorter paths to wins are prioritised) and negate it
            value = value ? (Math.abs(value) - 1) * Math.sign(-value) : 0;
            if (value >= best.value) {
                if (value > best.value) best = { value, moves: [] };
                best.moves.push(move); // keep track of equally valued moves
            }
        }
        return best;
    }
    goodMove() {
        let {moves} = this.minimax();
        // Pick a random move when there are choices:
        return moves[Math.floor(Math.random() * moves.length)];
    }
}

(function main() {
    const table = document.querySelector("#game");
    const btnNewGame = document.querySelector("#newgame");
    const btnCpuMove = document.querySelector("#cpumove");
    const messageArea = document.querySelector("#message");
    let game, human;

    function display() {
        game.board.forEach((cell, i) => table.rows[Math.floor(i / 3)].cells[i % 3].className = " XO"[cell]);
        messageArea.textContent = game.isWin ? (game.turn == human ? "CPU won" : "You won")
                                : game.isDraw ? "It's a draw"
                                : game.turn == human ? "Your turn" 
                                : "CPU is preparing move...";
        table.className = game.isWin || game.isDraw || game.turn !== human ? "inactive" : "";
    }

    function computerMove() {
        if (game.isWin || game.isDraw) return; 
        human = 3 - game.turn;
        display();
        setTimeout(() => {
            game.play(game.goodMove());
            display();
        }, 500); // Artificial delay before computer move is calculated and played
    }

    function humanMove(i) {
        if (game.turn !== human || !game.play(i)) return; // ignore click when not human turn, or when invalid move
        display();
        computerMove();
    }

    function newGame() {
        game = new TicTacToe();
        human = 1;
        display();
    }

    table.addEventListener("click", e => humanMove(e.target.cellIndex + 3 * e.target.parentNode.rowIndex));
    btnNewGame.addEventListener("click", newGame);
    btnCpuMove.addEventListener("click", computerMove);
    newGame();
})();

#game { border-collapse: collapse }
#game td { border: 1px solid black; width: 30px; height: 30px; text-align: center; cursor: pointer } 
#game td.X, #game td.O { cursor: default }
#game td.X { color: green }
#game td.O { color: red }
#game td.X:after { content: "X" }
#game td.O:after { content: "O" }
#game.inactive { background: silver }

<table id="game">
    <tr><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td></tr>
</table>
<h4 id="message"></h4>
<button id="newgame">New Game</button>
<button id="cpumove">Let CPU play a move</button>