确定 minimax tic-tac-toe 中的正确位置

Question

我尝试使用 minimax 算法在 C++ 中编写一个简单版本的井字游戏，但是运行在尝试确定得分最高的位置时遇到了问题。 minEval (Returns score for min), maxEval(returns score for max) 和 playMove (确定下哪个位置然后下棋) 函数如下所示。

int maxEval(int board[9]) {
    if (checkDraw(board)) {
        return 0;
    }
    else if (checkWin(board)) {
        return -1000;
    }
    int finalScore = -1000;
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = 1;
            int score = minEval(board);
            if (score > finalScore) {
                finalScore = score;
            }
            board[i] = 0;
        }
    }
    return finalScore;
}

int minEval(int board[9]) {
    if (checkDraw(board)) {
        return 0;
    }
    else if (checkWin(board)) {
        return 1000;
    }
    int finalScore = 1000;
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = -1;
            int score = maxEval(board);
            if (score < finalScore) {
                finalScore = score;
            }
            board[i] = 0;
        }
    }
    return finalScore;
}

void playMove(int board[9], int player) {
    int finalScore = player * -1000;
    int position;
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = player;
            int score;
            if (player == 1) {
                score = maxEval(board);
            }
            else {
                score = minEval(board);
            }
            if (player == 1 && score >= finalScore) {
                finalScore = score;
                position = i;
            }
            else if (player == -1 && score <= finalScore) {
                finalScore = score;
                position = i;
            }
            board[i] = 0;
        }
    }

    board[position] = player;
}

当我测试不同的位置以查看 minEval 和 maxEval 是否正确评估位置时，函数 return 正确得分（1000 表示最大赢，-1000 表示最小赢，0 表示平局）。但是，当我使用 playMove 函数让 AI 下棋时，它下的棋步非常可疑，几乎总是走 "incorrect" 步棋。这是我让程序玩的游戏示例（与自身一起玩）：

我怀疑是我把position设置成i的方式有问题，但我尝试修改也无济于事。关于评估功能有什么问题的任何建议？谢谢

这是整个代码的 link：http://ideone.com/6791d4

Answer 1

我会检查发现的变化，而不仅仅是分数。您是找到任何获胜的变化，还是找到对手最好的变化？

例如修改您的 min/max Eval 代码，将选择的移动也添加到数组中。

顺便说一句，如果将 min/max Eval 例程合并为一个，可能会更容易看到发生了什么。

警告未经测试的代码

int minmaxEval(int board[9], int player, int moves[9], int move) {
    if (checkDraw(board)) {
        return 0;
    }
    int finalScore = player * -1000;
    if (checkWin(board)) {
        return finalScore;
    }
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = player;
            int score = minmaxEval(board, -player, moves, move+1);
            if ( (player > 0 && score > finalScore) ||
                (player < 0 && score < finalScore) ) {
                  finalScore = score;
                  moves[move] = i;
            }
            board[i] = 0;
        }
    }
    return finalScore;
}

如果您在顶级例程中打印出 moves[]，您应该会看到给出该分数的变化。那里的不匹配会告知您对算法的理解，例如当它找到胜利时它是否停止。

一般来说，重要的是要有一种方法来仔细检查您的代码是否按照您的预期进行。研究单元测试和测试驱动开发。

Answer 2

感谢您的指点，我解决了问题。 playMove 函数中存在一个错误，我将 maxEval 和 minEval 不匹配，这导致 AI 无法为胜利或平局而战。所以，更正后的代码是：

void playMove(int board[9], int player) {
    int finalScore = player * -1000;
    int position;
    for (int i = 0; i < 9; i++) {
        if (board[i] == 0) {
            board[i] = player;
            int score;
            if (player == 1) {
                score = minEval(board);  //Previously Mismatched
            }
            else {
                score = maxEval(board);  //Previously Mismatched
            }
            if (player == 1 && score >= finalScore) {
                finalScore = score;
                position = i;
            }
            else if (player == -1 && score <= finalScore) {
                finalScore = score;
                position = i;
            }
            board[i] = 0;
        }
    }

    board[position] = player;
}

确定 minimax tic-tac-toe 中的正确位置

Determining the right position in minimax tic-tac-toe

c++

tic-tac-toe

minimax