神のアルゴリズム
パズルやゲームをできるだけ少ない手順で解くアルゴリズム

神のアルゴリズムとは、ルービックキューブパズルの解法に関する議論から生まれた概念である[1]が、他の組み合わせ パズルや数学ゲームにも適用できる。[2]これは、可能な限り少ない手数で解を導き出すアルゴリズム（つまり、解く側がこれ以上の手数を必要としないアルゴリズム）を指す。この神への言及は、全知の存在であれば、与えられた構成から最適な手順を知ることができるという考えに基づいている。

範囲

意味

この概念は、有限個の「配置」を取り得るパズルに適用される。これらの「配置」には、比較的少数かつ明確に定義された「動き」があり、これらの動きは複数の配置に適用可能であり、新たな配置へと導く可能性がある。パズルを解くということは、指定された「完全な配置」、単一の配置、あるいは複数の配置の集合のうちの1つに到達することを意味する。パズルを解くには、任意の初期配置から始めて、一連の動きを適用する必要がある。

解決

アルゴリズムは、任意の初期配置を入力として受け取り、最終配置（その初期配置からパズルが解ける場合、そうでない場合は解くことが不可能であることを示す）に至る一連の動作を出力する場合、そのようなパズルを解くことができるとみなされます。動作のシーケンスが可能な限り短い場合、解は最適です。すべての初期配置の中でこの最大値は、神の数[ 3]または、より正式にはミニマックス値[4]として知られています。したがって、神のアルゴリズムは、特定のパズルに対してパズルを解き、最適な解のみを生成するアルゴリズムです。

デイヴィッド・ジョイナーのような一部の著述家は、アルゴリズムが「神のアルゴリズム」と正しく呼ばれるためには、実用的であることも必要だと考えている。つまり、アルゴリズムが膨大な量のメモリや時間を必要としないということだ。例えば、初期設定によってインデックス付けされた巨大なルックアップテーブルを使用すれば、解を非常に速く見つけることができるが、膨大な量のメモリを必要とする。[5]

完全な解を求める代わりに、初期配置（最終配置ではない）から、ある最適解の最初の手となる単一の手を求めることも可能です。単一の手による問題に対するアルゴリズムは、報告された各手を繰り返し現在の配置に適用し、最終手に到達するまで繰り返し実行することで、元の問題に対するアルゴリズムに変換できます。逆に、元の問題に対する任意のアルゴリズムは、出力を最初の手まで切り捨てることで、単一の手による問題に対するアルゴリズムに変換できます。

例

この説明に当てはまる有名なパズルとしては、ルービックキューブ、ハノイの塔、15パズルなどの機械式パズルがあります。また、一人用ゲームのペグソリティアや、宣教師と人食い人種問題などの多くの論理パズルも取り上げています。これらのパズルに共通するのは、配置が頂点、動きが弧となる有向グラフとして数学的にモデル化できる点です。

機械式パズル

n-パズル

フィフティーンパズルは、最悪でも80回の単牌手[6]、または43回の多牌手[7]で解くことができます。nパズルを一般化すると、最適解を求める問題はNP困難[ 8]であるため、実用的な神のアルゴリズムが存在するかどうかは不明です。

ハノイの塔

ハノイの塔パズルでは、任意の数のディスクに対して神のアルゴリズムが知られている。移動回数はディスクの数に応じて指数関数的に増加する（） 2 n − 1 {\displaystyle 2^{n}-1} 。[9]

ルービックキューブ

スクランブルされたルービックキューブ

ルービックキューブを解くための最小移動回数を決定するアルゴリズムは、1997年にリチャード・E・コーフによって発表されました。[10]最悪のケースにおける解の最小移動回数の下限は20回であることは1995年から知られていましたが、トム・ロキッキは2010年に、どの構成でも20回以上の移動は必要ないことを証明しました。[11]したがって、20回は最適解の長さの明確な 上限です。数学者のデイビッド・シングマスターは1980年に、この数が20回であると「軽率に推測」していました。 [4]

未解決のゲーム

非常に限定された単純なルールと手順を持つ有名なゲームの中には、勝利戦略のための神のアルゴリズムが解明されていないものもあります。例としては、ボードゲームのチェスと囲碁が挙げられます。[12] どちらのゲームも、一手ごとに局面の数が急速に増加します。可能な局面の総数は、チェスで約5×10の44乗[13]、囲碁では（19×19の盤上で）約10の180乗[14]で、現在のコンピュータ技術では力ずくで解くには大きすぎます（現在、非常に困難を伴って解けたルービックキューブがわずか約10の180乗であるのと比較してください）。チェスのコンピュータは人間の最高のプレイヤーにさえ勝てるようになっているが、ゲームを最後まで計算しているわけではない。例えば、 ディープ・ブルーは11手先までしか探索せず（各プレイヤーの1手は2手として数える）、探索空間をわずか10の17乗まで減らした。 [ 16]その後、ディープ・ブルーは 人間のプレイと経験から得られたルールに従って、各ポジションの優位性を評価しました。

この戦略さえも囲碁では不可能です。評価すべき局面がはるかに多いことに加え、チェスのように局面の強さを評価するための単純なルール群を囲碁で構築することに成功した人は、これまで誰もいません。しかし、強化学習によって訓練されたニューラルネットワークは、人間の能力を超える局面評価を提供できます。[17] 評価アルゴリズムは初歩的なミスを犯しやすいため[18]、最強の暫定局面を見つけることを目的とした限定的な先読みでさえ、囲碁では神のアルゴリズムは実現不可能です。

一方、ドラフト（チェッカー）は、その専門家によって「プレイアウト」されていると長い間疑われてきました。[19] 2007年にシェーファーらは、 10個以下の駒を持つすべてのポジションのデータベースを計算し、すべてのドラフトの終盤ゲームのための神のアルゴリズムを提供することで、これが事実であることを証明しました。このアルゴリズムは、完璧にプレイされたすべてのドラフトゲームが引き分けで終わることを証明するために使用されました。[20] しかし、10個以下の駒を持つドラフトは、5 × 10 20ポジション[21]およびそれ以下の3.9 × 10 13は、データベース[22]では、ルービックキューブと同程度で、解くのがはるかに簡単な問題です。

パズルの配置の集合の大きさは、神のアルゴリズムが実現可能かどうかを完全に決定するものではありません。既に解かれたハノイの塔パズルは任意の数のピースを持つことができ、配置の数は指数関数的に増加します。しかしながら、この解法アルゴリズムはあらゆるサイズの問題に適用可能であり、実行時間は に比例します。[23] 3 n {\displaystyle 3^{n}} 2 n {\displaystyle 2^{n}}

参照

注記

  1. ^ ポール・アンソニー・ジョーンズ『ジェドバラの正義とケンティッシュ・ファイア：10のフレーズと表現における英語の起源』ハシェットUK、2014年ISBN 1472116224。
  2. ^ 例: Rubik's Cubic Compendium by Ernö Rubik、Tamás Varga、Gerzson Kéri、György Marx、Tamás Vekerdy (1987、Oxford University Press、ISBN)を参照 0-19-853202-4）、p. 207：「…ピラミンクスはマジックキューブよりもはるかに単純です…ニコラス・ハモンドは、神のアルゴリズムは最大21回の移動（4つの単純な頂点移動を含む）であることを示しました。[最近では、3人が神のアルゴリズムを発見しました。最大移動回数は15回（4つの頂点移動を含む）です。]」
  3. ^ ジョナサン・フィルデス（2010年8月11日）「ルービックキューブの高速解法の探求は終わりを迎える」BBCニュース。
  4. ^ ab シングマスター、311ページ、1980年
  5. ^ ジョイナー、149ページ
  6. ^ A. Brüngger、A. Marzetta、K. Fukuda、J. Nievergelt、「並列検索ベンチZRAMとその応用」、Annals of Operations Research 90 (1999)、pp. 45–63。
  7. ^ Norskog, Bruce; Davidson, Morley (2010年12月8日). 「15パズルは43手で解ける」. Cube Forumのドメイン. 2022年3月15日閲覧。
  8. ^ Daniel Ratner, Manfred K. Warmuth (1986). 「15パズルのN×N拡張に対する最短解を見つけることは困難である」. Proceedings AAAI-86 . National Conference on Artificial Intelligence, 1986. pp. 168–172.
  9. ^ ルエダ、カルロス (2000 年 8 月)。 「ハノイの塔パズルの最適解」。Universidad Autónoma de Manizales [マニサレス自治大学]。マニサレス、コロンビア。 2004 年 6 月 5 日にオリジナルからアーカイブされました。2022 年3 月 15 日に取得。
  10. ^ Richard E. Korf、「パターンデータベースを使用したルービックキューブの最適解の検索」、Proc. Natl. Conf. on Artificial Intelligence (AAAI-97)、プロビデンス、ロードアイランド、1997年7月、700–705頁。
  11. ^ ロキッキ、トーマス、コシエンバ、ハーバート、デイビッドソン、ジョン・デスリッジ (2010). 「神の数字は20」. Cube20.org . 2022年3月15日閲覧。
  12. ^ ローテンバーグ、11ページ
  13. ^ John Tromp. 「チェスのポジションランキング」GitHub。
  14. ^ バウム、199ページ
  15. ^ シングマスター、1981年
  16. ^ バウム、188ページ
  17. ^
    • バウム、197ページ
    • モハメディアン、11ページ
  18. ^ バウム、197ページ
  19. ^ フレイザー＆ハンナ、197ページ
  20. ^ ムーア＆メルテンス、第1章3節「神とチェスをする」
  21. ^ シェーファー他、1518ページ
  22. ^ ムーア＆メルテンス、「第1章の注釈」
  23. ^ ルエダ

参考文献

  • バウム、エリック・B.『思考とは何か？』MITプレス、2004年ISBN 0262025485。
  • デイビス、ダリル・N.、チャラビ、T.、バーバンク＝グリーン、B.、「人工生命、エージェント、そして囲碁」、マソウド・モハマディアン著『計算知能とその応用の新境地』、125～139ページ、IOS Press、2000年ISBN 9051994761。
  • フレイザー、ロバート（編）；ハンナ、W.（編）、『ドラフト・プレイヤーズ・ウィークリー・マガジン』第2巻、グラスゴー：JHベリー、1885年。
  • ジョイナー、デイヴィッド（2002年）『群論の冒険』ジョンズ・ホプキンス大学出版局、ISBN 0-8018-6947-1。
  • ムーア、クリストファー、メルテンス、ステファン、『計算の性質』オックスフォード大学出版局、2011年ISBN 0191620807。
  • ローテンバーグ、ガディ『触媒、神のアルゴリズム、そして緑の悪魔』アムステルダム大学出版局、2009年ISBN 9056295896。
  • シェーファー, ジョナサン; バーチ, ニール; ビョルンソン, イングヴィ; 岸本, 明宏; ミュラー, マーティン; レイク, ロバート; ルー, ポール; サトフェン, スティーブ (2007年9月14日). 「チェッカーは解ける」(PDF) . Science . 317 (5844): 1518– 1522. Bibcode :2007Sci...317.1518S. doi :10.1126/science.11​​44079. ISSN  0036-8075. PMID  17641166.
  • シングマスター、デイヴィッド『ルービックキューブのノート』ペンギン社、1981年ISBN 0-907395-00-7。
  • シングマスター、デイヴィッド、「ハンガリーの『マジックキューブ』の教育的価値」、第4回国際数学教育会議議事録、カリフォルニア州バークレー、1980年8月10～16日、pp. 307～312、バークハウザー・ボストン社、1983年ISBN 978-0-8176-3082-9。


「https://en.wikipedia.org/w/index.php?title=God%27s_algorithm&oldid=1314267534」より取得