一个查看谁赢得井字棋游戏的最佳算法

Question

我有一个完成的井字棋游戏板。它是3 x 3的。我不是真的在问代码（虽然那会有所帮助），但是什么算法最适合确定谁赢了？换句话说，我应该研究哪些算法来确定谁赢了？

唯一想到的就是暴力枚举。测试所有可能性，但我知道肯定有更好的方法。

- user489041

---

循环遍历行，然后循环遍历列，最后检查对角线。 - Danny

你是在问人工智能方面的问题吗？比如在极小化极大树上的Alpha-Beta剪枝算法？或者是井字棋游戏矩阵中的模式搜索？ - Adrian

更像是静态搜索。这个游戏已经完成了，存储在一个文本文件中。我从文本文件中读取数据，并需要确定谁赢了。但必须尽可能地优化，所以不需要确定最佳下一步或类似的内容。 - user489041

请记住，标准算法执行24个操作。动态解决问题可能会导致内存分配延迟，从而阻止理论时间复杂度在小数据集上实验更有效（例如，归并排序）。我们真的在为井字游戏的优化技术争论吗？ - xikkub

你为什么说有更好的方法？ - Philip

是的，我认为有一种比不断的蛮力法更优的方法来确定井字棋游戏是否有赢家或者是平局。请看下面我的答案。 - devdanke

Answer 1

我最近重新学到的一个重要课程是：当搜索空间足够小时，就使用暴力解法。

在一个3x3的棋盘上，有八种可能的获胜序列（行、列和对角线）。这给了你24个比较来验证是否有相同玩家标记在所有单元格中。即使在非常慢的计算机上，进行24次比较也不需要任何时间。

- Shay

---

...并且：“小”通常出乎意料地大。 - Philip

Answer 2

这里是最好的、聪明的和最优算法：（这是一种众所周知的技巧，所以我不夸耀，只赞扬这个算法）

定义：单元格如下命名：

A31  A32  A33
A21  A22  A23
A11  A12  A13

这些棋子分为W(白色)和B(黑色)两种。有8种获胜组合：[A11,A12,A13]，[A11,A21,A31]，[A13,A22,A31]等。给每个组合起一个名字：C1..C8。

C1 =def= [A11,A12,A13]
C2 =def= [A21,A22,A23]
C3 =def= [A31,A32,A33]
C4 =def= [A11,A21,A31]
C5 =def= [A12,A22,A32]
C6 =def= [A13,A23,A33]
C7 =def= [A11,A22,A33]
C8 =def= [A13,A22,A31]

将单元格划分到一组获胜组合中：

A11 --> C1,C4,C7
A12 --> C1, C5
A22 --> C2, C5, C7, C8

所以每个单元格A都指向那些包含A的组合。

为双方玩家保留可能获胜的组合集合。一开始，两名玩家都有8个组合。

Poss_W = C1, C2, C3, C4, C5, C6, C7, C8
Poss_B = C1, C2, C3, C4, C5, C6, C7, C8

当W在某个单元格A中下棋时，从B中删除相应的获胜组合。例如，当白色落在A12时，从黑色可能的获胜组合列表中删除C1、C5。

游戏结束后，拥有非空可能获胜组合集的玩家获胜。如果Poss_W和Poss_B都为空，则平局。

- Ali Ferhat

---

该算法不依赖于移动的顺序；如果您愿意，可以等待游戏结束。如果您愿意，您可以先“玩”所有黑棋步骤，然后再进行所有白棋步骤。您可以获取完成的棋盘并以任何顺序读取单元格值（B或W），如果您愿意，可以应用这些步骤。该算法适用于正在进行中和已经结束的游戏。 - Ali Ferhat

嗯，这与我的方法并没有太大的区别。 - akappa

也许这个算法在井字棋这样的简单游戏中并不太出彩。然而，它是一个非常强大的想法（显式枚举“解决方案”并将元素映射到解决方案集），可以在更复杂的游戏和谜题中使用。让我们玩一个游戏，在棋盘上放置俄罗斯方块，并且第一个无法移动的人输了。该算法可以被修改为快速查看一系列移动是否导致终端棋盘位置。（元素：单个方块的放置；组合：所有元素的集合；即每个放置都会使其他放置变得不可能） - Ali Ferhat

Answer 3

只需使用一个地图 对角线 -> 在该对角线上的检查次数。

当其中一个条目等于三时，您就有了赢家。

- akappa

Answer 4

井字棋的一个小优化是知道在第五步之前不可能有赢家。因此，如果你的游戏保持着移动计数，你可以减少检查整个棋盘状态的次数。

另一个优化是知道，如果你的算法找到任何一行、列或对角线包含X和O，那么它永远不可能成为赢家。你不需要再次检查它。你可以将这些无法获胜的情况从搜索空间中排除。

上述优化的一个副作用是，在搜索空间变为空的情况下，它可能让你更早地检测到平局。

- devdanke

Answer 5

简单的问题最好用简单的代码解决。

这里是一个直接而直截了当的JavaScript ES6解决方案。

const tictactoeBoard = ['x', 'o', 'x',
                        'o', 'x', 'o',
                         '', 'o', 'x'];

const winningCombinations = [
    /// horizontal
    [0, 1, 2],
    [3, 5, 6],
    [6, 7, 8],
    /// vertical
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    /// diagonal
    [0, 4, 8],
    [6, 4, 2],
];

const checkForWinner = () => {
    for (const c of winningCombinations) {
        const fieldsToCheck = [
            tictactoeBoard[c[0]],
            tictactoeBoard[c[1]],
            tictactoeBoard[c[2]]
        ];
        /// check if every fields holds a trueish value and
        /// is the same value across the array aka won the game
        if (
            fieldsToCheck.every(f => f && f === fieldsToCheck[0])
        ) {
            return fieldsToCheck[0]
        }
    }
    return
}

console.log(checkForWinner());

- arthurDent

Answer 6

如果您需要在每个步骤之后检查游戏是否结束，那么可以缓存临时结果。

对于每一行、列和对角线，存储每个玩家的标记数量。在每个步骤之后增加相应的值。如果数字为3，则有一个赢家。

- Karoly Horvath

Answer 7

在检查整个棋盘状态之前，没有办法确定获胜者。如果您想在每个回合结束时执行检查，请迭代每行、每列和两个对角线，检查是否相等（例如：board[0][0]==board[1][0]==board[2][0]等）。如果您想在玩井字游戏时跟踪棋盘状态，可以使用动态规划，尽管这是极度过度的。如果您正在使用异常大的棋盘，否则需要大量步骤才能找到获胜者，则动态方法将非常有用。值得注意的是，标准井字游戏足够小，高效的算法对性能没有影响。

- xikkub

---

请提供建设性的批评意见？ - xikkub