國際象棋將死算法複雜

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（雖然棋盤的大小也會影響這個），所以我猜測線性複雜度是可行的。