棋盤遊戲「Go」NP完成了嗎？

國際象棋大量存在，顯然有些足以擊敗一些世界上最偉大的球員。棋盤遊戲「Go」NP完成了嗎？

我聽說有很多人嘗試過爲棋盤遊戲Go寫成功的AI，但到目前爲止還沒有人想到超出普通業餘水平。

難道數學計算Go中任何給定時間的最優移動的任務是NP完全問題嗎？

2009-11-12 sharkin

不知道爲什麼你被低估了。這是一個合法的問題。 +1 – mpen 2009-11-12 23:30:57

那麼，目前的蒙特卡洛算法和類似的算法已經把邊界推到了平均業餘水平。尋找的名字包括Zenith，Go的許多面孔，Fuego，Leela等等。 – Svante 2009-11-12 23:34:22

國際象棋和圍棋都是EXPTIME complete。 IIRC，Go有更多可能的舉措，所以我認爲它比國際象棋複雜程度更高。關於Go的複雜性，Wikipedia有一個good article。

2009-11-12 23:28:18 rmeador

+12

你可能想提一下，兩個結果都是針對遊戲的一般版本。具有中等尺寸板的遊戲可以輕鬆地在不變的時間內解決。（雖然目前我們無法處理這個常量，可能也是如此。） – ShreevatsaR 2009-11-12 23:37:08

在理解專家說「國際象棋是EXPTIME完整」的含義時，ShreevatsaR的觀點非常重要。 – PeterAllenWebb 2010-01-07 21:30:48

即使圍棋只是在P它仍然是可怕的東西像O(n^m)其中n是空格數和m一些（大）定數。即使在P也沒有合理的計算。

2009-11-13 04:52:17 BCS

Chess或Go AI都沒有完全評估所有可能性，然後才決定採取行動。

國際象棋人工智能使用各種啓發式方法來縮小搜索空間，並量化棋盤上給定位置的「好」程度。這可以遞歸地通過評估可能的棋盤位置14-15向前移動並選擇導致良好位置的路徑來完成。

關於如何量化棋盤位置有一些「魔力」，所以在頂層，人工智能可以簡單地進行移動A>移動B，因此可以進行移動A.但是由於數量有限並且它們都具有可量化的價值，可以實施「足夠好」的算法。

但是對於程序來說，在Go中評估兩個可能的棋盤位置並進行A> B計算變得困難很多。如果沒有這個關鍵部分，它會讓AI的其他部分工作變得有點困難。

2009-11-28 05:28:53

回答