井字棋完美AI算法: 更深入的"制造分支"步骤

Question

井字棋完美AI算法: 更深入的"制造分支"步骤

17

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

如果玩家选择以下表格中优先级最高的移动，则可以玩完美的井字游戏[3]。

1) 获胜: 如果您有两个相邻的棋子，下一步请下第三个以获得连成三个棋子。

2) 阻止对手获胜: 如果对手有两个相邻的棋子，下一步请下第三个来阻止他们获胜。

3) 产生分支: 创造一个可以用两种方式赢得胜利的机会。

4) 防止对手产生分支:

选项1: 创建两个相邻的棋子，迫使对手进行防守，只要这不会导致对手产生分支或获胜。例如，如果“X”占据一个角落，“O”占据中心，“X”也占据相反的角落，“O”必须不下角落才能获胜。(在这种情况下下角落会为“X”创造一个赢的机会。)

选项2: 如果存在对手可以产生分支的情况，请阻止该分支。

5) 中心: 下中心棋格。

6) 对角线: 如果对手在一个角落里，下相对的角落。

7) 空角落: 下一个空角落。

8) 空边: 下一条空边。

我按照这些步骤操作，电脑从未输过。然而，它的进攻方式并不完美。因为我不知道如何进行第三步。在第三步中，我会扫描每个单元格，检查是否放置标记在该单元格上会创建一个叉子，然后将其放在那里。

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;
    }

}

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

编辑1：countFork将计算计算机有多少个叉子（计算机的令牌为2，玩家的令牌为1，因为我也在第4步中使用了该方法，所以countFork函数中有一个令牌参数）。

编辑2：我说它不完美的原因是这样的（CPU先走，它的单元格是蓝色的，人类单元格是红色的）。 enter image description here

正如您所看到的，如果我放在顶部单元格中，计算机就会赢。但是，如果我把它放在右侧单元格中，那么就是平局，尽管计算机仍然可以赢。

编辑3：不知道为什么，但我注释掉了第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;
}

编辑4：根据soandos的建议修复了错误，并在编辑3中更新了代码，现在它完美地工作了！

- Luke Vo

1

看起来合理。你为什么觉得它不起作用？countFork的第二个参数是什么？ - Matthew Strawbridge

@MatthewStrawbridge 已编辑以回答您的问题。感谢您的回复。 - Luke Vo

零是玩家，还是零未使用？ - soandos

错误：它没有检查一行中是否有两个单元格，第三个单元格是否可用。 - soandos

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- soandos · Accepted Answer

我不确定这是否是最优雅的方法，但下面是查看分叉的两个步骤。

如果电脑在下一轮无法获胜，并且不是第一或第二轮，那么可能存在一种分叉的可能（这不涉及创建分叉设置，只是找到分叉）。

对于每个空单元格，填充它，然后运行第1步函数（查看是否有两个相邻）。如果找到两个位置，则恭喜你，你有一个分叉。如果没有找到，则没有分叉。