Javascript中用极大极小算法求解TicTacToe

xam8gpfp  于 2023-01-16  发布在  Java
关注(0)|答案(2)|浏览(122)
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()结果和最佳得分,看起来递归在工作,但我不明白为什么在_setAIPlay()
如果在最后一个if语句中返回我console.log(bestScore)作为最终值,或者返回01而不是-1,在这种情况下,我认为-1作为最小值应该是最佳得分。
如果需要,您可以在此处找到完整的存储库gitHub

6yt4nkrj

6yt4nkrj1#

下面是一个简单的JavaScript中的井字游戏的极大极小算法的实现。搜索树会不断加深,直到检测到游戏结束状态。如果检测到获胜,则当前玩家不能玩游戏,因此静态值为负(-10)。如果检测到平局,则返回值为0。
在所有其他情况下,搜索会更深入,这个实现使用了一个极大极小算法,在这个算法中,双方的价值都被最大化,因此,从更深入的评估中返回的价值的符号总是颠倒的("对我的对手有利的东西对我不利,反之亦然")。
如果一个棋盘被发现有一个赢的位置,那么导致"最短"路径的移动将被优先考虑。这是通过每次我们回溯时将绝对值降低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>
4szc88ey

4szc88ey2#

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>

一个一个三个一个一个一个一个一个四个一个一个一个一个一个五个一个

相关问题