具有 minimax 的 Tic Tac Toe 机器人无法找到最佳着法

Question

我正在尝试按照 freecodecamp 的教程使用 minimax 算法制作井字游戏 ai。但是机器人无法找到获胜的动作。我尝试将代码与其他人的代码进行比较，但没有发现任何错误。

我检查了该函数返回的着法，它返回了一个得分为 -10 的着法，即使得分为 10 的着法可用。

请告诉我我的代码有什么问题。

function minimax(gameBoard, player){
    if(checkWin(gameBoard, bot)) return {score: 10};
    if(checkWin(gameBoard, human)) return {score: -10};
    
    var emptyCells = board.filter(e => typeof e === "number");
    
    if(emptyCells.length===0) return {score: 0};
    
    var possibleMoves = [];
    
    for(var i=0;i<emptyCells.length;i++){
        var move = {};
        move.id = gameBoard[emptyCells[i]];
        
        gameBoard[emptyCells[i]] = player;
        
        if(player === bot){
            move.score = minimax(gameBoard, human).score;
        }else{
            move.score = minimax(gameBoard, bot).score;
        }
        
        gameBoard[emptyCells[i]] = move.id;
        possibleMoves.push(move);
        
        var bestMove;
        if(player === bot){
            var bestScore = -100;
            for(var i=0;i<possibleMoves.length;i++){
                if(possibleMoves[i].score>bestScore){
                    bestScore = possibleMoves[i].score;
                    bestMove = i;
                }
            }
        }
        else{
            var bestScore = 100;
            for(var i=0;i<possibleMoves.length;i++){
                if(possibleMoves[i].score<bestScore){
                    bestScore = possibleMoves[i].score;
                    bestMove = i;
                }
            }
        }
    }
    return possibleMoves[bestMove];
}

Answer 1

假设您的函数checkWin没有错误，并且您在初始调用中传递的参数有效，那么您的代码中存在以下两个问题：

在下面的语句中引用了board，实际上应该是gameBoard:
```
var emptyCells = board.filter(e => typeof e === "number");
```
确定bestMove（以var bestMove;开头）的代码部分不应在循环内。您想要 first 将所有移动添加到 possibleMoves，然后仅 then 迭代这些移动以找到最佳移动。但是现在，每次向 possibleMove 添加一步时，您都会搜索最佳着法。更糟糕的是，你使用已经在外循环中使用的 same 循环变量 i，这将完全混淆你的外循环。

解决这两个问题应该可以解决您描述的问题。

具有 minimax 的 Tic Tac Toe 机器人无法找到最佳着法

Tic Tac Toe bot with minimax not able to find best move

javascript

algorithm

minimax