c - 确定井字游戏中的最佳 Action

Question

我想编写一个递归函数来确定给定井字游戏中的最佳着法

int nextMove(struct Game g, enum Symbol player) {
if (game_over(g) != 0) {
return -1;
}
int i, j;
int score, end;
for(i = 0; i < 3; i += 1) {
    for (j = 0; j < 3; j += 1) {
        if(g.board.fields[i][j] == 0) {
            g.board.fields[i][j] = player;
            score = nextMove(g, -player);
        }
    }
}
end = game_over(g)
}

我的 game_over 函数:

enum Symbol game_over(struct Game g)
{
int x, y = x = 0;
int full = 0;

for (y = 0; y < SIZE_Y_AXIS; y += 1)
{
    for (x = 0; x < SIZE_X_AXIS; x += 1)
    {
        if (g.board.fields[x][y] == NONE)
            full++;
        else if (x < SIZE_X_AXIS - 2 &&
                 g.board.fields[x][y] == g.board.fields[x+1][y] &&
                 g.board.fields[x][y] == g.board.fields[x+2][y])
            return g.board.fields[x][y];
        else if (y < SIZE_Y_AXIS - 2 &&
                 g.board.fields[x][y] == g.board.fields[x][y+1] &&
                 g.board.fields[x][y] == g.board.fields[x][y+2])
            return g.board.fields[x][y];
        else if (x < SIZE_X_AXIS - 2 && y < SIZE_Y_AXIS - 2 &&
                 g.board.fields[x][y] == g.board.fields[x+1][y+1] &&
                 g.board.fields[x][y] == g.board.fields[x+2][y+2])
            return g.board.fields[x][y];
        else if (x >= 2 && y < SIZE_Y_AXIS - 2 &&
                 g.board.fields[x][y] == g.board.fields[x-1][y+1] &&
                 g.board.fields[x][y] == g.board.fields[x-2][y+2])
            return g.board.fields[x][y];
    }
}
if (full == 0)
    return FULL;
return NONE;
}

我认为叶子的制作效果很好，但我不知道如何确定哪一片叶子(或哪一步)是最好的？现在有什么建议吗？

谢谢

Answer 1

在 tic-tac-toe 等游戏中，搜索树非常小，以至于可以评估所有叶节点(不像在象棋或围棋这样的游戏中，搜索被缩短)。由于检查了所有节点，因此可以通过检查它们是赢、输还是平来评估叶节点。您可以分别使用 1、-1 和 0 来表示这些值。完成后，将节点的值返回给它的父节点。 对于非叶节点，它必须选择其子节点的最高值或最低值，具体取决于它是最大节点(计算机)还是最小节点(其对手)。这将一路备份树到根，给它所有可能的 Action 一个值。具有最高值(value)的树的根部移动是该位置的最佳移动这就是极小极大算法。此外，在您提供的代码示例中，您未能在所有字段填满之前检查游戏是否结束。相反，检查玩家是否已经连续获得三个，因为游戏已经结束。 注意:您的 nextMove 函数声称返回一个 int 但在大多数情况下不会。这必须解决。这是我要添加到您的代码中的内容(伪代码中添加的部分)。我不确定 game_over 函数到底做了什么，所以我不能确定确切的代码应该是什么。因此，我打算将其取出并添加伪代码来取代它。

int nextMove(struct Game g, enum Symbol player) {
    if (computerWon) {
    return 1;
    }
    if (OpponnentWon) {
    return -1;
    }
    if (allSquaresAreFull) {
    return 0;
    }
    int i, j;
    int bestScore;//use this to calculate which move to return
    int score, end;
    //now check whose turn it is
    if(player == 1){//I'm assuming this is the computer player
        bestScore = -100;//start with an arbitrary low value 
        for(i = 0; i < 3; i += 1) {
            for (j = 0; j < 3; j += 1) {
                if(g.board.fields[i][j] == 0) {
                    g.board.fields[i][j] = player;
                    score = nextMove(g, -player);
                    g.board.fields[i][j] = 0;//make sure to undo every move made in the search
                    if(score > bestScore){//a better move for this player
                         bestScore = score;//update bestScore
                    }
               }
           }
        }
        return bestScore;//return best move to parent;

    }
    if(player == -1){//I'm assuming this is the opponent
        bestScore = 100;//start with an arbitrary high value 
        for(i = 0; i < 3; i += 1) {
            for (j = 0; j < 3; j += 1) {
                if(g.board.fields[i][j] == 0) {
                    g.board.fields[i][j] = player;
                    score = nextMove(g, -player);
                    g.board.fields[i][j] = 0;//make sure to undo every move made in the search
                    if(score < bestScore){//a better move for the opponent is a lower move
                         bestScore = score;//update bestScore
                    }
               }
           }
        }
        return bestScore;//return best move to parent;

    }
end = game_over(g)//this variable is never used. Not sure what it does. I would remove it, it seems useless
}

这应该返回位置的值(如果它赢了、输了或平局)。要确定采取哪一步，必须稍微修改一下。添加一个测试，看看我们是否在第一次调用 nextMove(即根)，而不是跟踪唯一的 bestMove，这是移动的值，同时跟踪实际的最佳移动是什么(也许在移动结构中)。如果最好移动，请返回它。现在 nextMove 将返回要采取的行动。