ルービックキューブにおけるGod's Number解明までの歴史 さわりだけでも理解したい！
まえがき
こんにちは、煎茶と申します。
初めての方、はじめまして。
去年も見ていただいた方、ありがとうございます。
この記事はアドベントカレンダー 14日目の記事となります。
前日はNokiさんの ユリノキのパーフェクトすきゅーぶ教室
翌日は葉っぱの大学生さんの 場所法で手順を覚えてみた(Square-1 EP編) になります。
God's Numberとは何か
ルービックキューブを用いた競技としてもっともメジャーなのはどれだけ「速く」揃えることができるかというものですが、世の中にはどれだけ「短い手数で」揃えられるかという競技に取り組んでいる人々がいます。
その競技に関連して長いこと考えられてきた疑問が、「ルービックキューブを毎回最小手数で揃えられるとして、もっとも大変な場合は何手かかるのか？」というものです。全ての状態から最短で揃える全知全能の神というイメージから、この問題にはGod's Numberという名前が付けられていました。
最終的に、2010年になってルービックキューブはいくら大変でも20手以内に揃えられるということが明らかになり、この問題は終わりを迎えました。(God's Number = 20.) ネット上のメディアなどで取り上げられていたので、記憶にある方もいるかもしれません。
God's Numberは数学的な考え方と、計算機を用いた問題解決という2つの分野が混ざっているとても面白い問題です。 実際20手というのは、証明方法の改善と計算機の性能向上両方が合わさって達成された数字です。
実際20手の証明ってどんな感じだったのか？というのをなんとなく知ってもらうため、この記事では証明までの歴史および、おそらく公開されている中で最も古い証明方法の紹介を行います。
なお古い証明方法は「God's Numberは52手よりは少ない」というものであり、20手についての解説はこの記事では詳細には行いません。ご了承ください。(僕が説明できません)
この問題の面白さを知るきっかけになれれば嬉しいと思います。
補足: 「1手」とは？
今回扱うGod's Numberでは、HTM(Half Turn Metric)という基準で手数をカウントしています。HTMでは90°回転だけでなく180°回転も一手として扱います。
180°回転を2手として扱う指標はQTM(Quarter Turn Metric)と呼ばれておりQTM基準でのGod's Numberは26であるということが示されましたが、今回は扱いません。
また、M2などの中層を回す操作はL2 R2のように分解されて二手扱いされます。
God's Numberの歴史
20手の証明をしたグループが証明の概要およびそれ以前の20手への漸近の記録をドキュメントとしてまとめてくれています。 (http://cube20.org/)
このドキュメントには20手の証明の概要、過去に公開されたGod's Numberに関する年表、実際に20手かかるパターンはどれほどあるかといった統計資料などが乗っています。
年表を見ていきましょう。
God's Number 下界と上界
表のLower bound(下界)とUpper Bound(上界)という部分に注目してみます。
God's Numberは上界と下界から挟む形で求められました。
下界は比較的簡単なようで、早い段階で20手が下界ということがわかっていたようです。例えば初期は18手と言われていましたが、これは実際に18手以上かかる盤面を構成することでOKになります。(後々20手かかるパターンが見つかる)
一方で上界は全ての盤面が20手以下であると言わなければいけないので、難しいです。「今のところ見つかっていません」だと、まだあるかもしれないという不安が付きまといます。
それでは、上界を示すにはどうすれば良いのでしょうか？一番簡単な方法は、ルービックキューブのあり得る状態を全部試すことです。
探索の先駆け: Thistlethwaite
Thistlethwaiteは上記の年表に引用されている中でもっとも古く40年も前の文献ですが、20手に漸近していくまでの証明の根幹となる考え方が含まれています。
今でこそ52手というのは全く遠く思えますが、(おそらく)計算機を活用した方法を初めて発表したということで、大きな貢献だったのではないでしょうか。
以下に続く章では、計算機でルービックキューブをシミュレーションするというのはどういうことなのか、40年もかかるほどそれは難しいのか、そしてThistlethwaiteがどのように一歩目を切り開いたか、ということについて説明していきたいと思っています。
それではまず前提として、計算機でのシミュレーションに広く用いられる「探索木」という概念を、簡単な○×ゲームを題材に説明します。見たことある話だなと思う方は飛ばしてもらっても構いません。
○×ゲームの探索木
○×ゲームはお互いに最善な手を取れば必ず引き分けで終わりますが、本当かどうかを自分で確かめようとしたことがある方もいるのではないでしょうか？ 確かめる方法は簡単で、あり得る全部の分岐を試すのが良いです。
紙の上であり得る○×ゲームの試合を書き並べてダメかあと確認する代わりに、計算機の上でそれを行うための一つの手法が探索木という概念です。流れを以下に示します。
ゲームの任意の時点で切り取った盤面を一つの「状態」とします。(○を半分だけ書いたところ、とかはちょっと勘弁してくださいね)
具体例はこんな感じ。
注意点として、○の数が多すぎたり、ゲームが過去に決着している場合など不可能な状態もあります。また、どういうルートで盤面にたどり着いたかは無視してください。
ある状態からは、可能な手(遷移)を打つことによって次の状態を得ることができます。
以上を用いて、初期状態から遷移する9パターンを得る、得られた状態からさらに複数の遷移をして... という風に、手が打てなくなるまで場合わけを広げていくと、○×ゲームで起こりうる全ての状態を得ることができます。
それぞれのノードからエッジが枝分かれしているように見えるので、探索木と呼ばれています。
埋まっているマスが減ることはないのでこの探索技は不可逆で、いつか全てのノードが終了ノードにたどり着きます。 この網羅された探索木を使うことで、お互い引き分けに持ち込めるなどの○×ゲーム全体の性質を掴むことができます。 (探索木を用いたゲーム攻略は、例えばmin-max法やα-β法といった広がりがあります。)
この探索木はそのままオセロ、チェス、将棋、囲碁などにそのまま応用できます。(遷移は単純ではないですが)
しかし、まだ世の中には将棋や囲碁で100%勝てるプログラムは開発されていません。どうしてなのでしょうか？この話は後々説明します。
ルービックキューブの探索木
○×ゲームで考えた状態および遷移という考え方はルービックキューブにも同じように適用することができます。HTMでカウントされる任意の操作が「遷移」、そして0回以上の操作を加えたルービックキューブがそれぞれの「状態」を持っています。
ということで完成状態を根として探索木を広げていきたいのですが、ルービックキューブは○×ゲームと違って終わりがありません。そこで、今まで通過した状態を全て記録し、既に見たことがある状態にたどり着いた場合はそこで打ち切りをすることにします。 今回探索木を作る目的なのはできるだけ短い手数なので、深い側にある方の頂点を遠回りとみなしてカットしてしまいましょう。
キューブの状態数は有限なので、この方針で全ての状態を網羅できそうです。 完成した探索木の最大の深さを調べれば、それがそのままGod's Numberになります。
素直な探索木の限界
さて、探索木を用いてシミュレーションをすることでGod's Numberを求められることがわかりました。おめでとうございます。
ところで、ルービックキューブのとりうる状態数ってどれくらいあるんでしょうか？ 答えは4325京2003兆2744億8985万6000通りです。指数表記ではおおよそ4.3 * 1019通り。
愚直にシミュレーションをしようとすると、これが大問題になります。
計算機には実は計算できる量に限りがあり、現在の一般的なPCだとおおよそ 109回/秒 程度の四則演算ができるようです。本当は回転をシミュレートしたり新しく発見した状態を記録したりする必要があるので無理なのですが、最大限楽観的に考えて1秒につき109通りの状態を新しく発見するとしましょう。すると網羅にかかる時間は...おおよそ1万年ほどでしょうか。
2100通りとかさらに無理な量の計算をやらせようとすることを俗に「宇宙滅亡」とかいう形で揶揄することがあるのですが、それに比べれば案外現実味のある数字に見えなくもないです。
もし現在もGod's Numberが解明されていなくて誰も解法を思いつけないのであれば、未来の人類に託してプログラムを回しておくのも一つの手です。今日やりましょう。
まあでも、自分が生きているうちに終わって欲しいですよね。そういう場合は別の手法をとる必要があります。
また、実は計算時間以外にも大きなネックになる部分があり、それは記憶容量です。 これも最大限楽観的に考えて、1つの状態を記憶するのに1bitしか使わないと仮定した上で大体40E(エクサ)byteくらいですか？個人の資産ではちょっと厳しそうですね。
将棋や囲碁で(今のところ)必勝法が見つかっていないのも、大体こういうことです。 理論的には最適な手を指すことができるが現実的には無理なため、様々な工夫によって勝てそうなルートを探索していくということです。
52手解法の説明
さて、この辺りから先述のドキュメントの内容に入っていきます。
まずは、どの流れで説明するか悩むので、概要を全て書き記します。ある程度知っている人であればここでわかるかもしれないですが、詳しい説明は後々続けていくので大丈夫です。簡単に目を通しながらスクロールしてください。
Thistlethwaiteのアルゴリズム
概要説明ここから
解法に先んじて、使用可能な回転の集合によってルービックキューブの状態を定義する表記について説明する。
例えば、<R>は完成状態、そこからR, R2, R'の4種類の状態の集合を表す。
同様に<L, R>なら3 * 3 + 1(完成状態)の10種類の状態の集合を表す。
筆者は、以下の4種類の状態を定めた。添字が大きい集合は、添字が小さい集合のsubsetになっている。
G_0 = <L, R, F, B, U, D>
G_1 = <L, R, F, B, U2, D2>
G_2 = <L, R, F2, B2, U2, D2>
G_3 = <L2, R2, F2, B2, U2, D2>
G_4 = I (完成)
先の章で述べた「ルービックキューブのパターン全部網羅」というのはG_0からG4への遷移を全て見つけることに等しい。
この解法では問題を以下の4つに分割することで、それぞれの問題のパターン数を減らし、現実的な計算時間で網羅することを可能にした。
G_0 -> G_1 EOを揃える 2,048通り
G_1 -> G_2 側面ステッカーを揃える 1,082,565通り
G_2 -> G_3 対面色のみにする 29,400通り
G_3 -> G_4 完成まで 663,552通り
それぞれの部分問題で、最も手数がかかったパターンを足すと、
7 + 13 + 15 + 17 = 52
よって、最悪でもルービックキューブは52手以内に完成する。
概要説明ここまで
改めて説明: 分割ステップその①
先ほどの省略しまくりの概要説明のことは忘れてもらって大丈夫です。
さて、探索木の問題は、枝分かれが多すぎる、深すぎる、そして埋めなければいけない状態数が多すぎることにありました。
というわけで少し天下り的なのですが、まずは一旦問題を簡単にして考えることにします。
ルービックキューブに、各面180°ずつしか回転をできないという縛りを加えたら問題はどう変化するのでしょうか？ とりあえずある状態から1手進め時の枝分かれが6通りに減ります。直前にあった動作はするだけ無駄なので、実質5通り。なんとなく木がすっきりしそうな感じはします。
180°の回転で得られる状態はどれも、「どのステッカーについても、同じ色もしくは対面色のセンターがある面に必ずいる」という特徴があります。(対面色...緑⇆青, 白⇆黄, 赤⇆橙。実際に何回か回してみるとわかるかと思います。)
このように対面色同士しかないキューブの状態全部をひっくるめた集合を、<L2, R2, F2, B2, U2, D2> と呼ぶことにします。<>に含まれる動作の組み合わせでたどり着ける物全部、という意味です。またこの集合にG_3という名前を付けます。何で3からなん？という点については後述します。
G_3は全部で663,552通りの小さな集合になり、全通り探索するという力技を行うことができます。(60万は元の1019通りから見ればとても小さいです。)
Thistlethwaiteさんはこの小さな問題を探索しきり、G_3からであればどれだけ遠くても17手で完成状態からどの状態にでも行けることを示しました。(実際にはコーナーを解いてからエッジを解くというふうにさらに分割していますが、詳細は省きます。)
めでたしめでたし。
問題を分割することの嬉しさ
さて本題より小さな問題は無事に解けたわけですが、これで何が嬉しいのか、ということを考えていきます。
ここまでで、G_3(「対面色同士しかない状態」の集合)に含まれる状態であれば、どこからでも(17手以内で)完成状態にたどり着くことがわかりました。
ということは、本題を「G_3に含まれるどこかにたどり着けばOK」ひいては「3色しかないルービックキューブだと思って全通りを探索できればOK」と言い換えることができます。(お手持ちのキューブで緑のステッカーを青に、黄色を白に、橙を赤に貼り替えてみてください。)
このように大きな問題を問題Aと問題Bに分けることで、Aのことを考えている間はBのことを忘れBのことを考えている間はAのことを忘れることができるというのがこの手法の大きな利点です。
最終的にThistlethwaiteのアルゴリズムでは全体を4つのステップに分割しています。
分割ステップその②
後ろ側(G_3 -> G_4)から説明を始めたので、次は(G_2 -> G_3)のステップについて説明します。
G_2はG_3と比較して、LおよびRの90°回転が解禁されました。 中層にあるエッジたち(UF/FU, UB/BU, DF/FD, DB/BD)は中層同士しか行き来できませんが、側面にあるエッジおよびコーナーは「元々側面のステッカーが側面を向いたまま」という縛りの中でどこにでも配置することができます。
このような状態は全部で29,400通りです。(ステップ①を既に行っているので、対面色は同じ色だと思って考えています。)
探索の結果、15手以内にこのステップの全パターンにたどり着けることがわかっています。
側面に接しているエッジやコーナーはどんな配置になっていても最悪17+15手で揃えられるので、同じ色(黒で表記しています)だと思ってしまっても大丈夫ですね。これで残った問題がまた簡単になりました。続きます。
分割ステップその③
続いて、G_1 にあって G_2にないパターンを探索していきます。 G_1 = <L, R, F, B, U2, D2> にできない操作は U, U', D, D'のみで、かなり自由度が高いです。
実際G_1でできないことは、「EOを変化させること」のみです。 EOの変化とは簡単にいうと、1つのパーツについている2つのステッカーを変換することです。
・コーナーパーツ/側面エッジパーツ/中層エッジパーツ同士を区別しない(G_2以降で揃えるので)
・全てのEOが正しい(G_1の条件)
を満たすのは全部で1,082,565通り、最長で13手かかります。
分割ステップその④
というわけで残った作業G_0 → G_1は「全てのパーツのEOを正しくする」です。 2,048通りで、7手以内で完了します。 ちなみに、このパートは人力でも慣れればできます。
Thistlethwaiteのアルゴリズム まとめ
というわけで、それぞれの分割問題が無事解けました。あとはそれぞれの問題を繋げれば、当初の問題であった「シミュレーションでルービックキューブの全パターンを網羅したい！」という問題の解になります。
G_0→G_4になるように辿れば、実際に崩れたルービックキューブを揃えていくことができます。
おさらいですが、
G_0 -> G_1 EOを揃える
G_1 -> G_2 側面用のステッカーを側面へ
G_2 -> G_3 前後/上下面のステッカーを対応するグループに
G_3 -> G_4 完成まで
となり、最悪でも 7 + 13 + 15 + 17 = 52 手です。
Thistlethwaite's 52-move algorithmには、実際に各ステップで全パターンを網羅したことの証明としてある状態からどう操作すれば完成状態に持っていけるかが列挙されています。(ただし、リストの解読が非常に難しいため実際にはほぼ無理かと思います。)
God's Number問題の発展
まえがきにも記した通り、この解法を発展させることでGod's Numberは20手に近づいていきます。 とりあえずというか、問題の分割を
G_0 = <U, F, R, L, B, D>
G_1 = <U, R, F>
G_2 = <U, R2, F2>
G_3 = I
のようにすることで39手まで縮まるようです。(http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__new_upper_bound.html)
またその後も、同様に問題を分割してルービックキューブを解くTwo-Phase Algorithm を発展させて... というふうにして手数は縮んでいきます。自分の理解がたらずこれ以上は説明できないのですが、興味があればぜひ cube20.org を覗いてみてくださいね。
なお、Two-Phase Algorithmについては今年のアドカレ2日目で2006NISH01さんが解説されています。ぜひ読んでみてください。
あとがき
ここまでお読みいただいたみなさま、ありがとうございました。
今更になって謝罪しなければいけないのですが、今回に自分の記事は結構不完全な可能性があります。
cube20.org の存在を知り、これ面白そうだから他の人にも知ってもらいたい！！という思いとともに勢いで登録をしたものの、思ったより読解と整理が進まずギリギリ提出クオリティになってしまった... というのが私の言い訳になります。
また、ルービックキューブは計算機科学だけでなく数学、特に群論のテーマとして扱われることが多く群論の知識があればもっと簡潔かつ正確な説明ができたのではないか... とも思っています。
ということで、間違いを発見したり違った視点による理解をお持ちの方がいればバンバン指摘していただければ...と思います( )
最終的に言いたいのは、God's Numberの話題ってすごく面白い！！しかも文献にアクセスすることができる！というのを皆さんに知ってほしかったです。今日の話は全部忘れても、cube20.org の存在は覚えて帰っていただければ幸いです。
(おまけ: この記事があがる一週間ほど前に、キューブ系YouTuberである J Perm がGod's Numberに関する動画をアップロードしていました。自分は彼のファンなのですが、今回ばかりはタイミングの悪さに涙を流しています。)
それでは、これで本当に終わりとなります。繰り返しになりますがお読みいただきありがとうございました。また機会があればどこかで。
