TicTacToe MinMax 算法不返回最佳移动

Question

在与 AI（“O”）对战时，很多时候它并没有做出最佳着法。

我相信它必须在 MinMax() 函数中对板之间的评估做一些事情，但我没有看到任何错误，并希望另一双眼睛能抓住我错过的东西。

compare_winning(board, winningPlayer, depth, checkTie)
   {
       const winning_combos = [
       [0,1,2],
       [3,4,5],
       [6,7,8],
       [0,3,6],
       [1,4,7],
       [2,5,8],
       [0,4,8],
       [2,4,6]
       ];
       
       for (let i = 0; i < winning_combos.length; i++)
       {
           if (board[winning_combos[i][0]].color === "x" && board[winning_combos[i][1]].color === "x" && board[winning_combos[i][2]].color === "x")
           {
               winningPlayer.win = -100 + depth;
               return true;
           }
           if (board[winning_combos[i][0]].color === "ai" && board[winning_combos[i][1]].color === "ai" && board[winning_combos[i][2]].color === "ai")
           {
               winningPlayer.win = 100 - depth; // '- depth' to choose a move that will lead to a sooner win.
               return true;
           }
       }

       if(checkTie){
           for (let i = 0; i < board.length; i++)
               if (board[i].color === "w")
                   return false;
           winningPlayer.win = 0;
           return true;
       }
       return false;
   }

MinMax(board, depth, player, bestSuccessor)
   {
       // When reaches a leaf node.
       let winningPlayer = {};
       if (this.compare_winning(board, winningPlayer, depth, true)){
           return winningPlayer.win;
       }

       // Returns an array filled with different boards with every possible move 'player' can move.
       let successors = this.Successors(board, player);

       if (player === "ai"){
           let result_value = Number.NEGATIVE_INFINITY;
           
           for (let i = 0; i < successors.length; i++){
               let value = this.MinMax(successors[i], depth + 1, "x", bestSuccessor);
               
               if (value > result_value){
                   result_value = value;
                   bestSuccessor.move = successors[i];
               }

           }
           return result_value;
       }

       else{
           let result_value = Number.POSITIVE_INFINITY;

           for (let i = 0; i < successors.length; i++){
               let value = this.MinMax(successors[i], depth + 1, "ai", bestSuccessor);
               
               if (value < result_value){
                   result_value = value;
                   bestSuccessor.move = successors[i];
               }
               
           }
           return result_value;
       }
   }

我在使用用户移动（“X”）设置 this.state.board 后立即在我的 handleClick() 函数中调用 MinMax()。

...
    let bestMove = {};
    this.MinMax(this.state.board.flat(), 0, "ai", bestMove)
...

Answer 1

与其将对象 bestMove = {} 传递到 MinMax() 函数，不如 return 将棋盘状态与 MinMax() 函数中的 minmax 值一起作为 object/list 好像return 合适的板子。（又名。下一个继任板）

之前，通过将对象 bestMove = {} 传递给 MinMax() 函数，它 return 在叶节点处编辑了棋盘状态。相反，我想要下一个最佳动作的棋盘状态。

MinMax(board, depth, player)
    {
        // When reaches a leaf node.
        let winningPlayer = {};
        if (this.compare_winning(board, winningPlayer, depth, true)){
            return [winningPlayer.win, board];
        }

        let successors = this.Successors(board, player);
        let bestBoard; 

        if (player === "ai"){
            let result_value = Number.NEGATIVE_INFINITY;
            for (let i = 0; i < successors.length; i++){
                let value = this.MinMax(successors[i], depth + 1, "x")[0];
                
                if (value > result_value){
                    result_value = value;
                    bestBoard = successors[i];
                }
            }
            return [result_value, bestBoard];
        }
        else{
            let result_value = Number.POSITIVE_INFINITY;
            for (let i = 0; i < successors.length; i++){
                let value = this.MinMax(successors[i], depth + 1, "ai")[0];
                
                if (value < result_value){
                    result_value = value;
                    bestBoard = successors[i];
                }
            }
            return [result_value, bestBoard];
        }
    }

//let bestMove = {};
let bestBoard = this.MinMax(newBoard.flat(), 0, "ai");

TicTacToe MinMax 算法不返回最佳移动

TicTacToe MinMax Algorithm Not Returning Optimal Move

javascript

tic-tac-toe

minmax