AI の本の 1 つで、よく知られている「15 パズル」を解決するために、シミュレーションやゲームでパスを見つけるための一般的なアルゴリズム (A-Star、Dijkstra) も使用されていることを読みました。
これらのアルゴリズムの1つを適用できるように、15パズルをノードとエッジのグラフに縮小する方法について、誰かが私にいくつかの指針を与えることができますか?
グラフの各ノードをゲームの状態として扱うとしたら、そのツリーは非常に大きくなりませんか? それとも、それはそれを行うための方法ですか？
Google で簡単に検索すると、これについて詳しく説明している 2 つの論文が見つかります。1 つはParallel Combinatorial Searchで、もう 1 つはExternal-Memory Graph Searchです。
アルゴリズムの問題に関する一般的な経験則:誰かがあなたより前にそれを行い、その結果を公開している可能性があります。
これは、A *アルゴリズムの使用について詳細に説明されている8パズルの問題の割り当てですが、かなり簡単です。
http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html
問題を解決するためのグラフ理論的な方法は、ボードのすべての構成をグラフの頂点として想像し、ボードのマンハッタン距離のようなものに基づいた剪定を伴う息優先検索を使用して、開始点からの最短経路を導き出すことです。ソリューションへの構成。
このアプローチの問題点の 1 つは、ゲーム スペースが非常に大きくなり、アクセスした頂点を効率的にマークする方法が明確でないn x nボードであるということです。n > 3言い換えれば、ボードの現在の構成が、他のパスをたどって以前に発見されたものと同一であるかどうかを評価する明確な方法はありません。もう 1 つの問題は、グラフ サイズが非常に急速に大きくなりn(約(n^2)!)、パスの数が計算上通過できなくなるため、総当たり攻撃には適していないことです。
Ian Parberry によるこの論文- パズルのリアルタイム アルゴリズムでは(n^2 − 1)、最初の行、次に最初の列、次に 2 番目の行を完了することによって反復的に解に到達する単純な貪欲なアルゴリズムについて説明しています...ほとんど即座に解に到達します、しかし、解決策は最適とはほど遠いです。基本的に、計算能力を一切活用せずに人間が行う方法で問題を解決します。
この問題は、ルービック キューブを解く問題と密接に関連しています。すべてのゲームのグラフは、強引に解決するには大きすぎると述べていますが、器用な人間が約 1 ~ 2 分でキューブを解決するために使用できるかなり単純な 7 ステップの方法があります。もちろん、このパスは最適ではありません。一連の動きを定義するパターンを認識することを学習することで、速度を17 秒まで下げることができます。しかし、ジリのこの偉業はどこか超人的です！
Parberry が説明する方法では、一度に 1 つのタイルのみを移動します。ジリの器用さを利用し、一度に複数のタイルを移動することで、アルゴリズムをより良くすることができると想像できます。これは、Parberry が証明するように、パスの長さを から減らすことにはなりませんがn^3、主項の係数を減らすことになります。
A* は問題空間を検索し、ヒューレスティクスで定義された目標への最も可能性の高いパスをたどることを覚えておいてください。
最悪の場合にのみ、問題空間全体を塗りつぶさなければならなくなります。これは、問題に対する実際の解決策がない場合に発生する傾向があります。
ゲームツリーを使用するだけです。ツリーはグラフの特殊な形式であることを忘れないでください。
あなたの場合、現在のノードで利用可能な動きの1つを行った後、各ノードの葉がゲームの位置になります。
また。少なくとも、A-Star アルゴリズムでは、可能な次のステップが次のステップよりも最終ルートに近いかどうかを判断するために、許容できるヒューリスティックを見つける必要があることに注意してください。