ルービックキューブの手数

趣

プレスリリースや論文を読んでないので、どういうアルゴリズムで「必ず26手以内」を証明したのか分からないけど、

7テラバイトのディスクをRAMの拡張として使用し、秒間1億回のシミュレーションが可能なコンピュータで行ったとのこと。

ということで、計算資源に物言わせた力技を使ったんだろうなーという印象を受けそうだが、そうでもない。

ルービックキューブ自体は規模はくそでかいとはいえ一応、有限状態機械の決定性問題。43,252,003,274,489,856,000個(!!)の状態からなる状態遷移モデルを作り、初期状態(完成状態)をルートとするスパニングツリーに展開してルートから一番遠いノードまでの距離を求めることで必要最大手数は「計算可能」。なんて富豪的プログラミング。

とはいっても、現在の計算機の力では43,252,003,274,489,856,000個の状態全てを計算することは物理的に不可能なので、なんらかの方法で状態数の圧縮が必要。たぶんそこが、この手の研究の肝。そして、現在の計算機の能力で26手以内を証明できる程度にまで状態圧縮をするアルゴリズムを作ったというところが、この研究の価値なのだ。