Tic Tac Toe完美的AI算法:更深入的"创建分叉"步骤

Question

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

如果玩家在下表中选择具有最高优先级的移动,则玩家可以玩完美的井字游戏[3].

1)胜利:如果你有两个连续的比赛,打第三个连续三个.

2)阻挡:如果对手连续两次,则发挥第三个阻挡他们.

3)福克斯:创造一个可以通过两种方式获胜的机会.

4)阻挡对手的分叉:

选项1:连续创建两个以强制对手进行防守,只要它不会导致他们创建分叉或获胜.例如,如果"X"有一个角,"O"有中心,"X"也有相反的角,"O"不能为了赢得角落.(在这个场景中扮演角球会为"X"赢得一个分叉.)

选项2:如果存在对手可以分叉的配置,则阻止该分叉.

5)中心:打中锋.

6)对角:如果对手在角落,则对角.

7)空角:打空角.

8)空的一面:空洞的一面.

我按照这一步,计算机永远不会丢失.但是,它的攻击方式并不完美.因为我不知道如何做第3步.这是我在第3步中所做的:扫描每个单元格,检查是否在该单元格上放置标记创建了一个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:计数叉将计算计算机有多少叉(计算机的令牌为2,玩家令牌为1,因为我也使用了该方法用于步骤4,因此在countFork功能中有令牌参数).

EDIT2:我说它不完美的原因是(CPU先行,其细胞为蓝色,人体细胞为红色). 正如您所看到的,如果我放入顶部单元格,计算机就会获胜.但是,如果我放入右侧的单元格,它就是一个平局,虽然计算机仍然可以获胜.

编辑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更新了代码,现在它完美无缺!

Answer 1

我不确定它是最优雅的方式,但这是一个两步查看分叉的方法.

如果计算机无法在下一回合获胜,并且它不是第一轮或第二轮,则可能是分叉(这不涉及为分叉创建设置,只是找到一个分支).

对于每个空单元格,填充它,然后运行步骤1函数(看看是否有两个连续).如果找到两个地方,恭喜你,你有一个叉子.如果没有,你就不会.