国际象棋将死算法复杂

Question

我想知道图表搜索算法的复杂性是什么，以确定一个国际象棋在大O符号的将军。

Answer 1

答案是算法会解决剩下的棋子（N）所有可能的移动。因为只有复杂度是O（N）（线性），它才会穿过每一块。

Answer 2

每边8件。第一招只有16个可能性，另外4个为骑士，第二部电影的数量相同。在此之后，可能性列表会增长到一个无争议的级别。

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

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

“艾利斯还估计出的博弈树的复杂性为至少10123，‘基于平均支化35因子和80的平均游戏长度’为。一个比较，经常比较的可观测宇宙中的原子数估计在4×1079到1081之间。“

Answer 3

国王最多有8次移动。并且需要一段时间来验证国王在每次移动后是否受到威胁。再加上国王留下的情况（和另一片移动）。所以这是不变的时间。

Answer 4

如果你只是想检查，如果给定的电路板包含一个击破，那么你可以做这样的事情：

1. 确定（国王）的广场设置你的国王可以移动到（8在各个方向 - 由你自己的棋子占领的场地 - 场地边界）
2. 迭代所有敌人的棋子并确定他们攻击的棋子。如果有任何这些方块在你的王座中，请将它们移除。维护一个布尔值来表明你的国王是否受到攻击。
3. 将死，如果你的kingset变成空和王受到攻击

件数确实起到了作用，所以如果你有一个任意大小的电路板与n个，的确很重要。在这种情况下，瓶颈将是检查所有棋子是否攻击某个位置，因为另一块棋子可能会阻止攻击。一个简单的实现可以在二次时间内完成。 通过维护一个集合中的棋子位置并优化它的add（）和contains（），你可以得到这个线性n（虽然棋盘的大小也会影响这个），所以我猜测线性复杂度是可行的。