「100×100×100のルービックキューブがどんどん解かれていく映像」は本物か


一面が100×100で構成されたルービックキューブが解かれていく動画というのが紹介されていました。


ネタ元になった動画はこれ。同じ作者の方が80×80×80版も公開しています。


BGMというか、サウンドトラックが変というか、そこでAチームかよ！というつっこみはともかく。これが本当にぐちゃぐちゃの状態からコンピュータが解法を見つけて解いているのか、それとも揃った状態からぐちゃぐちゃになるまで適当に回したムービーの逆再生なのか、という問題。Youtubeのコメント欄でも「Reverse Scramble」という単語が何度も出てきますが、逆再生であって、解いてるわけじゃないという指摘ですね。



動画を見た上で、私としてはこれは逆再生だろうと思います。何故か。



3×3×3の普通のルービックキューブの解き方として代表的なものにLBL（Layer by Layer）というものがあります。まず1段目を揃え、次に2段目を揃え、最後に3段目を揃えるというものです。各階層の揃え方はそれぞれ違うのですが、それぞれの階層を揃える中での手順というのは、よく似たパターンの繰り返しになります。


以前に少し書きましたが、ルービックリベンジの解法の場合は、まずセンターの４ピースを揃え、次に各辺の中２ピースを揃えることがスタートになります。これができてしまうと、後は3×3×3と同じ状況になるので、解けてしまう……ことがあるというのは以前書いた通り。実際には各辺の中２ピースというのが、3×3×3ではあり得ないパターンを取る場合があるので、ここからもう一工夫無いと完全に解けたということにはなりません。私はここで詰まっています。ちくしょー。


どちらの場合も、どの局面でも基本戦略は同じです。

  1. 揃えやすいところをまず揃える。
  2. 既に揃えた部分に影響を与えないように次に揃えやすいところを揃える。


要するにこれだけです。あるピースを欲しい場所に動かす手順というのは、それだけなら割に少ないものです。それを実行する中で動いてしまう部分と動かない部分があります。だから必要なのは、影響されたくない部分は影響されない場所に避けておいて、目的のピースを移動し、避難した部分を元に戻す、という流れになります。3×3×3の場合でこのための手順が、短いもので3手くらい、長いものだと6手くらいかな。これを繰り返して徐々に揃えていくことになります。


この一組の手順の長さがあまりに長くなると、人間にとっては厳しいことになります。何を避けて、何を動かそうとしていたのか途中で分からなくなってあーもーということになるわけです。


で、問題の動画なんですが、見ている限り、目的を持った個々の手順の繰り返しという特徴的なパターンがありません。4分あまりの動画のほとんどは、特に変化が見られない程混沌とした状況が続き、最後の数十秒で一気に揃う様は圧巻ではあるのですが、全て揃う直前になっても非常に中途半端なブロックが揃った状態です。


コンピューターが解くと言っても解き方を考えるのは人間なわけですから、解かれていく様にはある程度の秩序が現れるはずだというのが、私の感想です。コンピューター化して有利になるのは、上述の組み手の長さが長くなっても、コンピューターならなんとかなるだろうというあたり。例えば、各階層が上から下に揃っていくとか、中心から外側に向けて同心円状に揃っていくといった動画であれば、もう少し信用する気になったかもしれません。



ただし、コンピューターには人間の真似の出来ない解き方があるのも確かです。つまり、総当たり、ごり押し、出たとこ勝負。可能なありとあらゆる動作を繰り返して、後は野となれ山となれ、いつかは全面揃う日がくるだろうという方法です。百万匹の猿に百万台のタイプライターを百万年叩かせれば、いつかはシェイクスピアの戯曲を書き出すだろうというあれです。または九千億の神の御名。


この方法を部分的に採用したアプローチについては、以下のような記事があります。


3×3×3の最低手順数の証明で使用されたのがこの総当たり方式だったようですが、「実証は、7テラバイトのディスクをRAMの拡張として使用し、秒間1億回のシミュレーションが可能なコンピュータで行ったとのこと」。それなら3×3×3の全てのパターンを網羅できそうなものですが、さにあらず。3×3×3の全てのパターンというのは、

このパズルで考えられる配置は (8!×38-1)×(12!×212-1)/2 = 43,252,003,274,489,856,000(4,325京2,003兆2,744億8,985万6千) 通りである。


ということで、秒速1億回だとしても4325億秒＝1万4千年弱かかることになり、つまり、全てのパターンを総当たりしたわけでは無いということです。実際には人間の考えた解法である程度進めた状態にしておいて、残りの部分を総当たりで解いたようです。


今回の場合は、最低手順数の証明というわけではありませんから、ここまでの網羅性や最適化は必要ないでしょうが、それにしても100×100×100を総当たりで解ける程の計算能力はまだ我々は手にしていないのだろうというのが、総当たりで解いているわけでもなさそうだという私の感想です。




.