javascript minimax 算法 tic tac toe，并不总是给出最好的着法

Question

我一直在尝试在我的井字游戏中使用 minimax 算法，以使我的 AI 无敌。然而，它并不总是 return 最佳着法。

AI = X; human = "O"

var board =  ["x", "x", "-",
               "-", "o", "o",
               "-", "-", "-"]

它给出了索引[2]上方的棋盘作为正确的最佳着法。

然而，对于下面的棋盘，它给出的答案是索引[3]，这将允许人类玩家在轮到它时获胜。

var boardB = ["x","x","o",
             "-","o","-",
             "-","_","-"];

var player = 'x';
var opponent = 'o';

function isMovesLeft(board){
    for (var i = 0; i<board.length; i++){
        if (board[i] =='-'){
            return 'true';
        }
        else{
            return 'false';
        }
    }
}



function evaluate(){
    for (var i = 0; i < board.length; i += 3) {
        if (board[i] === board[i + 1] && board[i + 1] === board[i + 2]) {
            if (board[i] == player){
                return +10;  
            }
            else if(board[i]== opponent){
                return -10;
            } 
        }
    }
    for (var j = 0; j < board.length; j++) {
        if (board[j] === board[j + 3] && board[j + 3] === board[j + 6]) {
            if (board[j] == player){
                return +10;  
            }
            else if(board[j] == opponent){
                return -10;
            } 
        }
    }


  if ((board[4]==board[0] && board[4]==board[8]) || (board[4]==board[2] && board[4]==board[6])) {
    if (board[4]==player){
        return +10;
    }
    else if (board[4]==opponent){
        return -10;
    }
 }

return 0;
}



function minimax(board, depth, isMax){
    var score = evaluate(board);

    if (score == 10){
        return score;
    }

    if (score == -10){
        return score;
    }

    if (isMovesLeft(board) =="false"){
        return 0;
    }

    if (isMax == "true"){
        var best = -1000;

        for (var i = 0; i< board.length; i++){
            if (board[i]=='-'){
                board.splice(i, 1, player);
                var value = minimax(board, depth+1, "false");
                best = Math.max(best, value);

                board.splice(i, 1, "-");
            }
         }
         return best;  
     }

    else if (isMax == 'false'){
        var best = 1000;
        for (var i = 0; i<board.length; i++){
            if (board[i]=='-'){
             board.splice(i, 1, opponent);
             var value = minimax(board, depth+1, "true");
             best = Math.min(best, value);

             board.splice(i, 1, "-");
            }
         }
        return best;
      }
}

function findBestMove(board){
    var bestVal = -1000;
    var bestMove= -1;

    for (var i = 0; i<board.length; i++){
        if (board[i]=='-'){
            board.splice(i, 1, player);
            var moveVal = minimax(board, 0, "false");

            board.splice(i, 1, "-");

            if (moveVal > bestVal)
            {
                bestMove = i;
                bestVal = moveVal;
            }
        }
    }
    alert("bestVal is : " + bestVal + "<br> best Move is : " + bestMove;)
}

我想知道我的代码有什么问题。以下是我用作参考的一些网站：

http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/

https://blog.vivekpanyam.com/how-to-build-an-ai-that-wins-the-basics-of-minimax-search/

但我仍然无法弄清楚为什么它并不总是 return 最佳着法的原因。我希望有人能引导我走向正确的方向。提前致谢！

Answer 1

如果您看到每个 i 的 moveVal，您会发现它为零。
那是因为在 minimax 函数中你调用 isMovesLeft which when false returns 0.
你的程序的问题是 isMovesLeft 总是 returns false.
您应该将其更改为：

function isMovesLeft(board){
    for (var i = 0; i<board.length; i++){
        if (board[i] =='-'){
            return 'true';
        }
    }
return false;
}

此更改应使您的程序获得 6 作为最佳着法。

从未在任何地方使用参数 depth。
您可以在返回分数时使用它：return score/depth
这将确保 losing/winning 的短期影响比长期影响更大。

javascript minimax 算法 tic tac toe，并不总是给出最好的着法

javascript minimax algorithm tic tac toe, not always giving the best move

javascript

algorithm

tic-tac-toe

minimax