algorithm - 在 Connect 4 中检测早期领带

Question

我正在寻找一种算法来检测 Connect 4 游戏中的早期平局。截至目前，我已经检查了棋盘是否已满并且未检测到任何胜利，但我想尽快知道比赛是否可以推断为平局。

例如，考虑这个游戏，玩家 B 刚刚在位置 Row-5, Column-0 玩:

    |
    v
5 | B |   |   |   |   |   |   |
4 | A | B | A | B | A | B | A |
3 | A | B | A | B | A | B | A |
2 | B | A | B | A | B | A | B |
1 | B | A | B | A | B | A | B |
0 | A | B | A | B | A | B | A |
    0   1   2   3   4   5   6

然后，游戏不被视为平局，因为玩家 B 仍然有办法获胜。尽管如果玩家 A 在 Row-5, Column-1 玩:

        |
        v
5 | B | A |   |   |   |   |   |
4 | A | B | A | B | A | B | A |
3 | A | B | A | B | A | B | A |
2 | B | A | B | A | B | A | B |
1 | B | A | B | A | B | A | B |
0 | A | B | A | B | A | B | A |
    0   1   2   3   4   5   6

在这一点上，任何一位玩家都没有办法获胜:这将是平局。我希望算法立即将此通知用户。

Answer 1

检查棋盘上所有可能的 4-in-a-row 运行，水平、垂直和对角线。如果它们都包含至少一个 A 和至少一个 B，那么这将是平局。如果甚至有一个由空和 A 或空和 B 的组合组成(假设没有行 4 行 A 或 4 行 B，在这种情况下你已经赢了)，那么 A 或 B 仍然有可能赢。

您可能已经有了检查获胜的代码，所以只需调整它以检查 A 的 4 行或空，或 B 的 4 行或空而不是 4 行-A 的一行，或 B 的一行 4。如果它未能检测到可能的胜利，那么平局是不可避免的。

一个问题是棋盘上有少量空白区域。在这种情况下，您需要计算出 A 和 B 的剩余移动次数，并且只允许它们在计算中有那么多的空位，例如检查 A 的 4 行和最多 2 个空的。例如，如果还剩 5 个空位，轮到 B 了，那么 A 还剩 2 步，B 剩下 3 步。

它无法处理的一种情况是，如果只剩下一个空列 - 可能有足够的空间让一个玩家连续堆叠 4 个，但他们不能，因为玩家必须交替。