artificial-intelligence - ボードゲーム「囲碁」NPは完了していますか？

Question

周りにはたくさんのチェスAIがあり、明らかに、世界で最も優れたプレーヤーの何人かを打ち負かすのに十分なものもあります。

ボードゲーム「囲碁」で成功するAIを書くために多くの試みがなされてきたと聞いていますが、これまでのところ、平均的なアマチュアレベルを超えるものは考えられていません。

Goで任意の時点で最適な動きを数学的に計算するタスクは、NP完全問題である可能性がありますか？

Answer 1

Chess と Go はどちらもEXPTIME completeです。IIRC、囲碁はより多くの可能な動きがあるので、チェスよりもその複雑さのクラスの倍数が高いと思います。ウィキペディアには、Go の複雑さに関する優れた記事があります。

Answer 2

Go が単に入っているだけでも、どこにスペースの数があり、(大きな) 固定数であるかのPように恐ろしいものになる可能性があります。入っていても、計算するのに合理的なものにはなりません。O(n^m)nmP

Answer 3

チェス AI も囲碁 AI も、動きを決定する前にすべての可能性を完全に評価しません。

チェス AI は、さまざまなヒューリスティックを使用して検索スペースを絞り込み、ボード上の特定の位置がたまたまどの程度「良い」かを定量化します。これは、14 ～ 15 移動先の可能なボード位置を評価し、適切な位置につながるパスを選択することで、再帰的に実行できます。

ボードの位置を定量化する方法にはちょっとした「魔法」があり、トップ レベルでは、AI は単純に Move A > Move B に進むことができるため、Move A を行います。定量化可能な値「十分な」アルゴリズムを実装できます。

しかし、プログラムが Go で考えられる 2 つのボード位置を評価し、A > B の計算を行うのは非常に難しいことが判明しました。その重要な部分がなければ、残りの AI を機能させるのは少し難しくなります。