algorithm - 如何在 m,n,k 游戏(广义井字棋)早期有效地检测平局？

Question

我正在实现一个 m,n,k-game ，井字棋的通用版本，其中 m 是行数，n 是列数，k 是玩家需要连续放置才能获胜的棋子数。我已经实现了对胜利的检查，但我还没有想出一种令人满意的方法来在棋盘装满棋子之前进行检查，如果没有玩家可以赢得比赛。换句话说，棋盘上可能有空位，但不能以一个玩家获胜的方式填充它们。

我的问题是，如何有效地检查这个？以下算法是我能想到的最好的算法。它检查两个条件:

A. 遍历所有 4 个方向(从上到下、从右到左和两个对角线方向)的所有棋盘位置。如果说 k = 5，并且发现 4 (= k-1) 个连续的空槽，则停止检查并报告“无平局”。这不考虑例如以下情况:

OX----XO    (Example 1)

其中 a) 在两个 - 之间的某处有 4 个空的连续插槽 ( X ) 's, b) 接下来是 O轮到了，c) 棋盘上的其他空位少于四个，没有玩家可以通过向这些位置放置棋子来获胜，并且 d) 除了在所示插槽中的水平方向之外，也不可能在任何其他方向上获胜。现在我们知道这是平局，因为 O最终会阻止最后一次获胜的可能性，但错误地尚未报告，因为有四个连续的空位。那没问题(但不是很好)。当检查算法通常较早地发现这种情况时，检查这种情况会在开始时提供良好的加速，但随着更多棋子放在板上，它会变慢。

B. 如果不满足这个 k-1-consecutive-empty-slots-condition，算法将在所有 4 个方向上再次连续检查插槽。假设我们目前正在从左到右检查。如果在某个时候 X遇到了，前面是 O或 - (空槽) 或板边框，然后开始计数连续X的数量。 's 和空槽，计数在这第一次遇到 X .如果可以数到 5，就知道 X 是可能的获胜，并报告“没有平局”。如果 O前面是 X在连续 5 次之前遇到 X的，然后 X从我们开始计数的地方开始，从左到右的 5 个位置无法获胜。例如:

X-XXO    (Example 2)
12345

在这里，我们从位置 1 开始检查，数到 4，遇到了 O .在这种情况下，我们将从遇到的 O 继续。以同样的方式，试图找到 5 个连续的 O 's 或这次空插槽。计数时的另一种情况X的或空插槽，一个 O在计数到 5 之前遇到一个或多个空槽位。例如:

X-X-O    (Example 3)
12345

在这种情况下，我们将再次从 O 继续在位置 5，但将 O 之前的连续空槽的数量添加到新计数器(连续 O 或空槽) ，这里是 1，这样我们就不会错过这个可能的获胜位置:

X-X-O---X    (Example 4)

这样，在最坏的情况下，必须遍历所有位置4次(4个方向，当然长度小于k的对角线可以跳过)，运行时间为O(mn)。

我能想到的最好方法是一次性完成这两个描述的检查，A 和 B。如果检查算法通过所有方向的所有位置而没有报告“无平局”，则报告平局。

知道您可以通过检查添加运行时间的最后一块附近来检查胜利 O(k) ，我想知道是否有更快的方法来提前检查领带。不必渐近地更快。我目前将这些碎片保存在二维数组中。是否有一种数据结构可以进行有效的检查？一种方法:在进行任何平局检查之前，可以等待玩家进行的移动的最高阈值是多少？

Stack Overflow 上有很多相关的问题，例如 this ，但我能找到的所有讨论要么只指出明显的平局条件，即移动的次数等于棋盘的大小(或者他们检查棋盘是否已满)，或者只处理棋盘的特殊情况是正方形:m = n。例如 this answer声称在恒定时间内检查平局，但仅在 m = n = k 时有效。我有兴趣尽早报告平局以及一般的 m、n 和 k。此外，如果该算法适用于两个以上的玩家，那就太好了。

Answer 1

我会减少确定与更简单的子问题的关系的问题:
玩家 X 还能赢吗？

如果所有玩家的答案都是“否”，则为平局。

要确定玩家 X 是否可以获胜:

用虚拟的“X”片填充所有空白

任何地方都连续有 k 个“X”件吗？

如果没有 --> 玩家 X 不能获胜。 return false .

如果有，请找出虚拟棋子数最少的 k 行棋子。计算其中的虚拟件数。

计算玩家 X 剩余的移动次数，与所有其他玩家交替，直到棋盘完全填满。

如果移动次数少于获胜所需的虚拟棋子数量，则玩家 X 不能获胜。 return false .

否则，玩家 X 仍然可以获胜。 return true .

(该算法将报告玩家 X 可能获胜，即使在 X 的唯一获胜 Action 会让另一个玩家首先获胜的情况下，但没关系，因为这也不会是平局)

如果，如您所说，您可以通过检查添加运行时间 O(k) 的最后一块附近来检查获胜。 ，那么我想你可以在O(k * Number_of_empty_spots)中运行上面的算法:添加所有虚拟 X 棋子，注意添加的棋子附近的任何获胜组合。

空位的数量可以很大，但只要至少有一个大小为 k 的空行，并且玩家 X 还剩下 k 步直到棋盘被填满，你就可以确定玩家 X 仍然可以获胜，所以你不需要运行完整检查。

这应该适用于任意数量的玩家。