3

我有一个完整的井字游戏板。它是 3 x 3。我并不是真的要代码（尽管这会有所帮助），但是什么算法最适合查看谁赢了？另一种表达方式是，我应该研究哪些算法来查看谁赢了？

唯一真正想到的是蛮力。只是测试所有的可能性，但我知道必须有更好的方法。

4

7 回答 7

13

我最近（重新）学到的重要一课：当搜索空间足够小时，只需使用蛮力。

在 3x3 棋盘上，有八种可能的获胜顺序（行、列和对角线）。这为您提供了 24 次比较，以验证一个人在所有 it 单元格中是否具有相同的玩家标记。即使在非常慢的计算机上，24 次比较也完全不需要时间。

于 2012-03-19T16:14:57.987 回答
3

这里是最好的，聪明的，最优的算法：（这是一个众所周知的技巧，所以我不吹嘘，只赞美算法）

定义： 细胞命名如下：

A31  A32  A33
A21  A22  A23
A11  A12  A13

碎片是W（hite）或B（lack）。有 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 都为空，则游戏为平局。

于 2012-03-20T09:09:48.383 回答
2

只需使用地图diagonal -> number of checks in that diagonal。

当其中一个条目等于三时，您就有了获胜者。

于 2012-03-19T16:08:55.290 回答
0

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

这是一个蛮力和直接的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());

于 2022-02-16T19:47:02.980 回答
0

井字游戏的轻微优化来自于知道在第 5 步之前不可能有赢家。因此，如果您的游戏保持移动计数，您可以减少检查整个棋盘状态的次数。

另一个优化是知道，如果您的算法找到任何包含 X 和 O 的行、列或对角线，那么它永远不会成为赢家。您无需再次检查。您可以从搜索空间中弹出那些无法获胜的东西。

上述优化的一个副作用是，在搜索空间变空的情况下，它可以让您在等待棋盘填满之前更快地检测到平局。

于 2022-02-16T03:30:56.923 回答
-1

如果你必须在每一步之后检查游戏是否结束，你可以缓存临时结果。

对于每一行、每一列和对角线，存储每个玩家的标记数。在每一步之后增加适当的值。如果数字是 3，则您有赢家。

于 2012-03-20T08:52:27.377 回答
-2

如果不检查整个董事会状态，就无法确定获胜者。如果您想在每轮结束时执行检查，请遍历每一行、每一列和两条对角线，检查是否相等（例如：board[0][0] == board[1][0] == board[2][0]等等）。如果您想在玩井字游戏的同时跟踪棋盘状态，您可以使用动态编程，尽管这有点矫枉过正。如果您使用异常大的板，否则动态方法将很有用，否则需要大量步骤才能找到赢家。还值得注意的是，标准井字游戏足够小，有效的算法不会对性能产生丝毫影响。

于 2012-03-19T16:16:26.140 回答