ボードゲーム「Go」NP完成ですか？

Question

チェスAIの周りにはたくさんのものがあり、いくつかの世界の偉大な選手たちを打ち負かすのに十分なものもあります。

私は、ボードゲームGoの成功AIを書くために多くの試みがなされてきたと聞いてきましたが、平均アマチュアレベルを超えて何も考えていませんでした。

Goの任意の時点で最適な移動を数学的に計算するタスクは、NP完全な問題ですか？

Answer 1

チェスとゴーはともにEXPTIME completeです。 IIRC、Goにはより多くの動きがあり、チェスより複雑なクラスの倍数だと思います。 Wikipediaには、Goの複雑さに関するgood articleがあります。

Answer 2

GoはPに過ぎない場合でも、それはまだnはスペースの数であるとmは、いくつかの（大）固定数であるO(n^m)のような恐ろしい何かである可能性があります。 Pであっても、計算するのに妥当なものはありません。

Answer 3

チェスまたはゴーAIは、移動を決定する前にすべての可能性を完全に評価しません。

チェスAIは、さまざまな経験則を使って探索空間を絞り込み、ボード上の所定の位置がどのように「良いか」を定量化します。これは、可能なボード位置14-15の移動を評価し、良好な位置につながる経路を選択することによって再帰的に行うことができる。

ボードの位置がどのように数量化されているかにはちょっとした魔法があります。そのため、AIは単純にMove A> Move Bに移動できるため、Move Aを実行できます。ただし、彼らはすべて、定量化可能な値を持っています。「十分に良い」アルゴリズムを実装することができます。

しかし、プログラムがGoで2つの可能なボード位置を評価し、そのA> B計算を行うことはずっと難しくなっています。この重要な部分がなければ、残りのAIを動作させるのは少し難しいです。