c# - Tic Tac Toe完美AI算法: deeper in "create fork" step

Question

我已经在 StackOverflow 上阅读了许多 Tic Tac Toe 主题。我发现维基百科上的策略适合我的演示项目:

A player can play perfect tic-tac-toe if they choose the move with the highest priority in the following table[3].

1) Win: If you have two in a row, play the third to get three in a row.

2) Block: If the opponent has two in a row, play the third to block them.

3) Fork: Create an opportunity where you can win in two ways.

4) Block Opponent's Fork:

Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)

Option 2: If there is a configuration where the opponent can fork, block that fork.

5) Center: Play the center.

6) Opposite Corner: If the opponent is in the corner, play the opposite corner.

7) Empty Corner: Play an empty corner.

8) Empty Side: Play an empty side.

我按照这些步骤操作，计算机从未丢失。然而，它的攻击方式并不完美。因为我不知道如何执行第 3 步。这是我在第 3 步中所做的:扫描每个单元格，检查将 token 放在该单元格上是否会创建一个 fork ，然后将其放在那里。

private void step3() // Create Fork.
{
    int[] dummyField = (int[])field.Clone();
    // Try Level 1 Dummy
    for (int i = 0; i < 9; i++)
    {
        if (dummyField[i] != 0) continue;
        dummyField[i] = 2;
        if (countFork(dummyField, 2) >= 2)
        {
            nextCell = i;
            return;
        }
        dummyField[i] = 0;
    }

}

请给我一些关于这一步的建议。

EDIT1: count fork 将计算计算机有多少个fork(计算机的 token 为2，玩家 token 为1，因为我在步骤4中也使用了该方法，所以countFork<中有一个 token 参数 函数)。

EDIT2:我说它不完美的原因是这样的(CPU在前，它的细胞是蓝色的，人体细胞是红色的)。 如您所见，如果我放入顶层单元格，则计算机获胜。但是如果我把右边的单元格放进去，那就是平局，尽管计算机仍然可以赢。

EDIT3:不知道为什么，但我注释掉了第 3 步，电脑播放……完美!我真的很惊讶! 这是我的 countFork 函数(我需要将这段代码移植到不支持二维数组的 Alice，所以我使用 getNumberFromXY 将二维数组转换为一维数组) :

private int countFork(int[] field, int token)
{
    int result = 0;

    // Vertical
    int cpuTokenCount;
    int spareCell;
    for (int x = 0; x < 3; x++)
    {
        cpuTokenCount = 0;
        spareCell = -1;
        for (int y = 0; y < 3; y++)
        {
            if (field[getNumberFromXY(x, y)] == token)
                cpuTokenCount++;
            else if (field[getNumberFromXY(x, y)] == 0)
                spareCell = getNumberFromXY(x, y);
        }
        if (cpuTokenCount == 2 && spareCell != -1) result++;
    }

    // Horizontal
    for (int y = 0; y < 3; y++)
    {
        cpuTokenCount = 0;
        spareCell = -1;
        for (int x = 0; x < 3; x++)
        {
            if (field[getNumberFromXY(x, y)] == token)
                cpuTokenCount++;
            else if (field[getNumberFromXY(x, y)] == 0)
                spareCell = getNumberFromXY(x, y);
        }
        if (cpuTokenCount == 2 && spareCell != -1) result++;
    }

    // Top-Left To Lower-Right Diagonal
    cpuTokenCount = 0;
    spareCell = -1;
    for (int i = 0; i < 3; i++)
    {
        if (field[getNumberFromXY(i, i)] == token)
            cpuTokenCount++;
        else if (field[getNumberFromXY(i, i)] == 0)
            spareCell = getNumberFromXY(i, i);
    }
    if (cpuTokenCount == 2 && spareCell != -1) result++;

    // Top-Right To Lower-Left Diagonal
    cpuTokenCount = 0;
    spareCell = -1;
    for (int i = 0; i < 3; i++)
    {
        if (field[getNumberFromXY(2 - i, i)] == token)
            cpuTokenCount++;
        else if (field[getNumberFromXY(2 - i, i)] == 0)
            spareCell = getNumberFromXY(2 - i, i);
    }
    if (cpuTokenCount == 2 && spareCell != -1) result++;

    return result;
}

EDIT4:根据 soandos 修复了错误，并更新了 EDIT 3 中的代码，现在它完美运行了!

Answer 1

我不确定这是最优雅的方法，但这是查看 fork 的两步方法。

如果计算机无法在下一回合获胜，并且不是第一回合或第二回合，则可能会出现 fork (这不涉及为 fork 创 build 置，只是找到 fork )。

对于每个空的单元格，填充它，然后运行您的第 1 步函数(查看是否有两个连续的单元格)。如果它找到两个地方，恭喜，你有一个 fork 。如果没有，你就没有。