time-complexity - 国际象棋将死算法复杂度

Question

我想知道在大 O 表示法中确定国际象棋中将死的图形搜索算法的复杂性是多少。

Answer 1

每边 8 片。第一步只有棋子有 16 种可能性，骑士有 4 种可能性，第二部电影有相同的数量。在此之后，可能性列表增长到无法计算的水平。

世界上最好的国际象棋引擎使用“最可能”的图形搜索。

这篇维基百科文章非常有用：http ://en.wikipedia.org/wiki/Game_complexity

“Allis 还估计博弈树的复杂度至少为 10123，“基于 35 的平均分支因子和 80 的平均博弈长度”。作为比较，可观测宇宙中的原子数，它是经常比较，估计在 4×1079 和 1081 之间。”

Answer 2

答案是该算法将通过剩余的棋子（N）解决所有可能的移动。因为它只有在复杂度为 O(N)（线性）时才会遍历每个部分。

Answer 3

如果您只想检查给定的棋盘是否包含将死，那么您可以执行以下操作：

1. 确定您的国王可以移动到的（国王）方格组（所有方向8个-您自己的棋子占据的领域-领域的边界）
2. 遍历所有敌方棋子并确定他们攻击的方格。如果这些方块中的任何一个在您的国王组中，请将它们移除。保持一个布尔值以指示您的国王是否受到攻击。
3. 如果您的国王组空了并且国王受到攻击，则将死

棋子的数量确实很重要，所以如果你有一个任意大小的棋盘，有 n 棋子，这很重要。在这种情况下，瓶颈将是检查所有棋子是否攻击某个位置，因为另一个棋子可能会阻止攻击。一个简单的实现可以在二次时间内完成。通过保持集合中棋子的位置并针对 add() 和 contains() 对其进行优化，您可以将其降低到 n 中的线性（尽管棋盘的大小也会影响这一点），所以我猜线性复杂度是可行的。

Answer 4

国王最多有八步。并且需要不断的时间来验证国王是否在每次移动后受到威胁。加上国王留在原地（另一块移动）的情况。所以它是恒定的时间。