米ノースイースタン大学のコンピュータ科学部のGene Cooperman教授と大学院生のDan Kunkle氏が、3×3×3のルービックキューブをどのような状態からでも26手以内で揃えられることを証明した。これまでは27手以内が証明されている最少のソリューションだった。

3×3×3のルービックキューブ

「ルービックキューブは、SearchとEnumerationの問題に結びつく研究題材である」とCooperman氏。ルービックキューブのソリューションを導きだす過程は、AIからオペレーションに至るまで、様々な分野において異なったメソッドを比較検討する機会になるという。両氏は、大規模なテーブルを展開するために、7テラバイトの分散ディスクをRAMの拡張として利用。その上でルービックキューブのすべてのコンフィギュレーションをセット化し、1つの動きが全てのセットに与える結果を調べた。そのデータを基に、1秒あたり100,000,000回のシミュレーションが可能なコンピュータを用いて、26手以内のソリューションにたどり着いた。

ルービックキューブのソリューションについては1997年にカリフォルニア大学ロサンゼルス校のRichard Korf教授が、最少で18手以内、多くとも20手以内で解けると発表した。ところが実証できずに、長い間27手以内が最少のソリューションと見られていた。従来の研究についてKunkle氏は、「Korf氏はルービックキューブの1つ状態から最適なソリューションを導き出すプログラムづくりに時間をかけていた」と指摘。「われわれのプログラムは先に大規模な予測計算を行い、その結果ルービックキューブをどのような状態からでも26手以内に揃えられるソリューションを、およそ1秒程度のスピードで見つけ出せる」という。

ルービックキューブは6色に色分けされた立方体のパズルで、一面が3×3に分割されている。キューブを回して色をバラバラにし、それを再び揃えるというシンプルなパズルだが、4300京通り以上の状態が考えられるという奥深さがマニアを作り出している。現在では基本の3×3×3以外にも、4×4×4や5×5×5など、より高度なソリューションが必要なキューブが登場している。