最適な実行時間tic-tac-toeアルゴリズム

完璧なチック・タック・トゥーAI /アルゴリズムは、決して失うことはありませんが、100%勝ち、抽選するだけです。

あなたがそのようなアルゴリズムに対して一度対戦すると仮定し、それが作る次の動きを計算します。

理論的に可能な限り速く、すなわち最小の漸近複雑度でこれを計算できる最適なアルゴリズムがあるか?

ベストアンサー

「漸近的複雑さ」は、無限に増加する可能性のある「問題の大きさ」という概念がある場合にのみ意味をなす概念です。

チック・タック・トーのゲームは、常に3×3のボード上でプレイされ、9回の移動よりも長くかかることはありません。無限に増やすことは何もなく、それに関係する漸近的な複雑さについて尋ねるには意味がありません。

しかし、gomokuのゲーム(ティックタックトーの一般化であり、サイズの異なるボード上でプレイできる can
)は、PSPACE-completeと呼ばれるものです。これは、「決定問題」のためのものです。ここでは、与えられたポジションが第1選手、第2選手、またはどちらの選手であるかを問うことができます。あなたがこれを解決することができれば、「誰が勝つのか?最適な動きを見つけることができれば、ゲームが終わるまで最適な動きをして誰が見えるかを見ることで、(非常に長く動くことができないゲームについては)簡単に決定問題を解決することができます勝った。だから、ここで尋ねられた最適プレイの問題は、PSPACE-complete(ちょっとファッピーに話す;厳密に言えば、これは決定問題にのみ適用される用語です)です。

これは、P = PSPACE(P =
NPより強い主張であり、それ自体は広く考えられていないが、不可能であると証明していない)なら、多項式時間で最適なゴモクの動きを見つけることができるが、P!=
PSPACE広く考えられており、確かに不可能とは証明されていない)、あなたはできません。

もし最適なゴモクの動きが明らかにできるだけ早く見つかったプログラムを持っていれば、P =
PSPACEかどうかの大きな恐ろしい問題を解決するか、あなたのプログラムの最悪の場合の実行時間を取り除いてください(この場合、問題の複雑さについてはほとんど教えてくれません)。

私は個人的には、最適なゴモクの動きを見つけるにはボードサイズの関数として指数関数的な実行時間が必要だと推測しますが、これは単なる推測であり、上記の理由から、近い将来に推測できるものよりも良いとは思いません。確かに、指数関数的に(単独で)より悪くなることはありません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です