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

Question

我一直在尝试在我的tic-tac-toe游戏中使用minimax算法，以使我的AI无敌。然而，它并不总是返回最佳移动。

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/

但我仍然不明白为什么它不总是返回最佳移动。我希望有人能把我引向正确的方向。提前谢谢！

Answer 1

如果你看到每个i的moveVal，你会发现它是零。
这是因为在极小值函数中，你调用isMoves↓，当false返回0时。
你的程序的问题是isMoves↓总是返回false。
你应该把它改成：

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

这个变化应该让你的程序得到6作为最好的移动。

参数depth从未在任何地方使用
您可以在返回分数时使用它：返回分数/深度
这将确保输赢的短期后果比长期后果更有效。