井字游戏MiniMax实现总是返回第一个空位

Question

我正在尝试实现Minimax，以便在js的井字游戏中每转找到最佳移动。

但是，它总是返回第一个空位：0,0，当该位取为0.1时，依此类推。事实证明miniMax函数始终返回1。

let board = [
    ['', '', ''],
    ['', '', ''],
    ['', '', '']
];

const p1 = 'X';
const p2 = 'O';
const scores = {
    'X': 1,
    'O': -1
}

function bestMove(board, isMaximizing, player, turns) {
    let bestScore = isMaximizing ? -Infinity : Infinity;
    let bestMove;
    let score;

    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[i][j] == '') {
                board[i][j] = player;
                score = miniMax(board, !isMaximizing, isMaximizing ? p2 : p1, turns + 1);
                board[i][j] = '';
                if (isMaximizing) {
                    if (score > bestScore) {
                        bestScore = score;
                        bestMove = [i, j];
                    }
                }
                else {
                    if (score < bestScore) {
                        bestScore = score;
                        bestMove = [i, j];
                    }
                }

            }
        }
    }
    return bestMove;
}

function miniMax(board, isMaximizing, player, turns) {
    let winner = checkForWinner(board);
    if (winner != null)
        return scores[winner];
    if (turns > 9)
        return 0;

    let bestScore = isMaximizing ? -Infinity : Infinity;
    let score;

    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[i][j] == '') {
                board[i][j] = player;
                score = miniMax(board, !isMaximizing, isMaximizing ? p2 : p1, turns + 1);
                board[i][j] = '';
                if (isMaximizing)
                    bestScore = Math.max(score, bestScore);
                else
                    bestScore = Math.min(score, bestScore);
            }
        }
    }

    return bestScore;
}

我尝试查看其他人对井字游戏的Minimax的实现，但我不明白是什么使我的失败。

我做错了什么？

Answer 1

我看到您的minimax（negamax）代码有2个问题：

'1。在您的minimax函数中，您正在遍历每个正方形，以找出最佳的移动方法。但是，您只返回分数，而不是最佳动作。如果您找到获胜的举动，请写下：

return None, 1

然后在您编写的minimax递归调用中：

miniMax(board, !isMaximizing, isMaximizing ? p2 : p1, turns + 1)[1]

在最下面的返回处写：

return bestMove, bestScore

您决定bestScore的位置，也只有在最高/最低得分发生变化时，才需要更新bestMove。与在bestMove函数中执行的操作类似。

'2。在bestMove函数中，您将再次遍历所有正方形。这就是为什么它一遍又一遍地返回相同的平方。由于您的极小值将找到最佳移动，因此您只需要拨打初始电话：

bestMove, bestScore = miniMax(board, !isMaximizing, isMaximizing ? p2 : p1, turns + 1)

否则，它将转到第一个方块并进行完整的最小极大，因此找到该位置的最佳移动（无论起始移动如何）。由于永远不会找到比最佳移动更好的移动，因此不会将bestMove更新为除第一个可能的正方形以外的任何内容。

希望我有任何意义，英语不是我的母语，我只习惯用Python进行编码：）