Loading article…
ルービックキューブの神のアルゴリズムは、ルービックキューブパズルを解く方法についての議論から生まれた概念ですが、 [ 1 ]他の組み合わせパズルや数学ゲームにも適用できます。[ 2 ]これは、可能な限り少ない手数で解けるアルゴリズムを指します（つまり、解く人はこの数以上の手数を必要としないはずです） 。神への言及は、全知全能の存在であれば、与えられた構成から最適な手順を知っているという考えに基づいています。
この概念は、有限個の「構成」を取り得るパズルに当てはまります。パズルでは、構成に適用できる比較的少数の明確に定義された「操作」によって、新しい構成へと移行します。パズルを解くとは、指定された「最終構成」、つまり単一の構成、または複数の構成のいずれかに到達することを意味します。パズルを解くには、任意の初期構成から始めて、一連の操作を実行します。
アルゴリズムがそのようなパズルを解くとみなせるのは、任意の初期構成を入力として受け取り、最終構成に至る一連の移動を出力として生成する場合である（パズルがその初期構成から解ける場合。そうでない場合は、解けないことを知らせる）。移動のシーケンスが可能な限り短い場合、その解は最適である。すべての初期構成の中で、この値が最も高いものは、神の数[ 3 ]、またはより厳密にはミニマックス値[ 4 ]として知られている。したがって、与えられたパズルに対する神のアルゴリズムとは、パズルを解き、最適な解のみを生成するアルゴリズムである。
デイビッド・ジョイナーなどの一部の著者は、アルゴリズムが「神のアルゴリズム」と適切に呼ばれるためには、実用的である必要があり、つまり、アルゴリズムが膨大な量のメモリや時間を必要としない必要があると考えている。たとえば、初期構成でインデックス付けされた巨大なルックアップテーブルを使用すると、ソリューションを非常に迅速に見つけることができるが、膨大な量のメモリが必要になる。[ 5 ]
完全な解を求める代わりに、初期状態（ただし最終状態ではない）からの最初の操作、つまり最適解の最初の操作を求めることもできます。この問題の単一操作版に対するアルゴリズムは、報告された各操作を現在の状態に適用しながら繰り返し実行することで、最終状態に到達するまで元の問題に対するアルゴリズムに変換できます。逆に、元の問題に対するアルゴリズムは、その出力を最初の操作に切り詰めることで、単一操作版に対するアルゴリズムに変換できます。
この説明に当てはまる有名なパズルとしては、ルービックキューブ、ハノイの塔、15パズルなどの機械式パズルが挙げられます。一人用ゲームのペグソリティアや、宣教師と人食い人種の問題など、多くの論理パズルも含まれています。これらのパズルに共通するのは、配置を頂点、移動を弧とする有向グラフとして数学的にモデル化できる点です。
15パズルは、最悪の場合、80回の単一タイル移動[ 6 ]または43回の複数タイル移動[ 7 ]で解くことができます。その一般化であるnパズルでは、最適な解を見つける問題はNP困難[ 8 ]であるため、実用的な神のアルゴリズムが存在するかどうかはわかりません。
ハノイの塔パズルでは、任意の数の円盤に対して神のアルゴリズムが知られています。移動回数は円盤の数とともに指数関数的に増加します（)。[ 9 ]
ルービックキューブを解くための最小移動回数を決定するアルゴリズムは、1997 年にRichard E. Korfによって発表されました。[ 10 ]最悪の場合の解の移動回数の下限が 20 であることは 1995 年以来知られていましたが、Tom Rokicki は 2010 年に、どの構成でも 20 を超える移動は必要ないことを証明しました。[ 11 ]したがって、20 は最適解の長さの明確な上限です。数学者のDavid Singmasterは 1980 年にこの数を 20 であると「軽率に予想」していました。[ 4 ]
ルールと手順が非常に限定された、単純で明確に定義されたゲームの中には、いまだに勝利戦略の決定的なアルゴリズムが解明されていないものもある。例えば、ボードゲームのチェスと囲碁が挙げられる。[ 12 ] これらのゲームはどちらも、一手ごとに局面の数が急速に増加する。可能な局面の総数は、チェスでは約5× 10⁴⁴ [ 13 ] 、囲碁では10¹⁸⁰（19×19盤面）[ 14 ]と、現在のコンピューティング技術では総当たり解法では到底不可能なほど大きい（現在では、非常に困難な作業を経て解決されたルービックキューブの約10⁴⁴と比較せよ）。4.3 × 10 19ポジション[ 15 ] )。したがって、これらのゲームに対する神のアルゴリズムを総当たりで決定することは不可能です。最高の人間プレイヤーにさえ勝てるチェス コンピュータが構築されていますが、それらはゲームを最後まで計算しません。 たとえば、ディープ ブルーは11 手先までしか探索せず (各プレイヤーの 1 手を 2 手として数える)、探索空間を 10 17に減らしました。[ 16 ] その後、人間のプレイと経験から導き出されたルールに従って、各ポジションの優劣を評価しました。
囲碁では、この戦略さえも不可能です。評価すべき局面が圧倒的に多いことに加え、チェスで行われているように、囲碁の局面の強さを評価するための単純なルールをこれまで誰もうまく構築できていません。ただし、強化学習によって訓練されたニューラルネットワークは、人間の能力を超える局面の評価を提供できます。[ 17 ] 評価アルゴリズムは初歩的なミスを犯しやすいので[ 18 ]、最強の中間局面を見つけることを目標とした限定的な先読みであっても、囲碁では神のアルゴリズムは実現できていません。
一方、チェッカー（ドラフツ）は、熟練者によって「攻略法が見つかっている」と長年疑われてきた。[ 19 ] 2007年、シェーファーらは、駒が10個以下のすべての局面のデータベースを計算し、ドラフツのすべての終盤戦に対する神のアルゴリズムを提供することで、このことを証明した。このアルゴリズムは、完璧にプレイされたドラフツのゲームはすべて引き分けで終わることを証明するために使用された。[ 20 ] しかし、駒が10個以下のドラフツでは、5 × 10 20ポジション[ 21 ]さらに少ない、データベースにある3.9 × 10 13は、 [ 22 ]ルービックキューブと同じオーダーで、はるかに簡単に解ける問題です。
パズルの位置の集合の大きさは、神のアルゴリズムが可能かどうかを完全に決定するものではありません。すでに解決されているハノイの塔パズルは任意の数のピースを持つことができ、位置の数は指数関数的に増加します。それにもかかわらず、この解法アルゴリズムはあらゆる規模の問題に適用可能であり、実行時間は次のようにスケーリングする。[ 23 ]
