Minimax 算法未按预期运行（在 C 中实现）

Question

我一直在用 C 实现 minimax 算法时遇到问题，对于井字游戏，这里是

minimax()

函数的代码：

int minimax(char(*board)[3], int isMax, char var)
{
    int score;
    char oppVar;
    int maxScore = -1000;
    int minScore = 1000;

    if (var == 'X')
        oppVar = 'O';
    else
        oppVar = 'X';

    if (checkWnr(board, var))
        return 1;
    else if (var == 'O' && checkWnr(board, oppVar)) //the condition without which the program doesn't run properly
        return -1;                                  //details lower in the post
    else if (!emptyCells(board))
        return 0;

    if(isMax)
    {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (board[i][j] == ' ')
                {
                    board[i][j] = var;
                    score = minimax(board, 0, oppVar);
                    maxScore = max(maxScore, score);
                    board[i][j] = ' ';
                }
        return maxScore;
    }
    else
    {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (board[i][j] == ' ')
                {
                    board[i][j] = var;
                    score = minimax(board, 1, oppVar);
                    minScore = min(minScore, score);
                    board[i][j] = ' ';
                }
        return minScore;
    }

调用它并实际在棋盘上移动的函数：

void bestMove(int dum1, int dum2, char(*board)[3], char var)
{
    int score;
    MOVES move;
    move.grade = -1000;
    char oppVar;

    if (var == 'X')
        oppVar = 'O';
    else
        oppVar = 'X';

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (board[i][j] == ' ')
            {
                board[i][j] = var;
                score = minimax(board, 0, oppVar);
                if (score > move.grade)
                {
                    move.grade = score;
                    move.line = i;
                    move.column = j;
                }
                board[i][j] = ' ';
            }
    board[move.line][move.column] = var;
}

以及上面使用的 MOVES 结构和

checkWnr()

、

emptyCells()

函数：

typedef struct {
    int line;
    int column;
    int grade;
}MOVES;


int checkWnr(char(*board)[3], char var)
{
    if (board[0][0] == var && board[1][1] == var && board[2][2] == var)
        return 1;
    else if (board[0][2] == var && board[1][1] == var && board[2][0] == var)
        return 1;
    for (int i = 0; i < 3; i++)
        if (board[i][0] == var && board[i][1] == var && board[i][2] == var)
            return 1;
        else if (board[0][i] == var && board[1][i] == var && board[2][i] == var)
return 1;
    return 0;
}

int emptyCells(char(*board)[3])
{
    int nr = 0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (board[i][j] == ' ')
                nr++;
    return nr;
}

基本上，该算法仅在满足以下条件时才按预期工作，（返回 -1，表示损失）：

else if (var == 'O' && checkWnr(board, oppVar)) return -1;

例如，如果我删除

var == 'O'

条件或添加另一个条件，类似于'X'，如：

else if (var == 'X' && checkWnr(board, oppVar)) return -1;

在保持另一个位置的同时，程序仍会开始从左到右在板上放置值，而不管获得的分数。

我不知道为什么会这样，任何帮助将不胜感激，提前致谢！

Answer 1

问题是你尝试了一些替代方案；这里：

    if (checkWnr(board, var))
        return 1;
    else if (var == 'O' && checkWnr(board, oppVar))
        return -1;

条件

checkWnr(board, var)

是错误的，因为

var

是轮到它的玩家在minimax搜索中。所以如果比赛赢了，那肯定是对方在上一步棋中赢了。

其次，当

oppVar

获胜时，您需要检查当前玩家是否是最大化玩家。如果最大化，则返回 -1，否则返回 1。这样你就表明这是 bad 情况（对手赢了）。

因此将该代码块更改为：

    if (checkWnr(board, oppVar))
        return isMax ? -1 : 1;