月曜日にネイチャー・マシン・インテリジェンス誌に掲載された研究によると、新しいニューラルネットワークは、最速の人間の2倍の速さでルービックキューブを解くことができるが、最速の愚かなアルゴリズムよりはおよそ3倍遅いという。
AI によるアプローチは、MIT が開発した世界最速の min2phase アルゴリズムなどの従来の計算方法ほど速くはありませんが、昔ながらの遊び場のパズルをはるかに超える可能性を秘めています。たとえば、タンパク質の研究により有効活用できる可能性があります。
1970年代後半に誕生して以来、この人気玩具は人々を魅了し続けています。ルービックキューブのような組み合わせパズルゲームに特化した団体である世界キューブ協会は、毎年複数の大会を開催し、ファンにどれだけ速く解けるかに挑戦しています。これらの大会に参加する人はスピードキューバーと呼ばれ、現在の世界記録は中国のスピードキューバー、ユーシェン・ドゥ氏がわずか3.47秒でパズルを解いたものです。
しかし、DuはDeepCubeAのような機械学習ソフトウェアにはおそらくかなわないだろう。カリフォルニア大学アーバイン校（UCI）の研究チームが開発したディープニューラルネットワークで構成されたこのシステムは、ルービックキューブを平均28手、1.2秒で解くことができると、論文の筆頭著者でUCIの博士課程学生であるフォレスト・アゴスティネッリ氏はThe Register紙に語った。
これは確かに速いが、昨年 MIT の研究者らが開発した min2phase アルゴリズムを使用するロボット システムほど速くはない。
Min2phaseはニューラルネットワークを持たず、学習も機械学習技術も一切使用していません。純粋にキューブを解くことだけを目的にプログラムされており、それだけのことしかできません（しかも非常に高速です）。一方、DeepCubeAにはより多くの機能があります。Min2phaseの方が高速である理由は明白ですが、一方で、AIコードは基本的なデータ構造上では従来の単純なアルゴリズムよりも高速に動作することが分かっています。
神の数
DeepCubeAは強化学習を用いて訓練されました。パズルのランダムな組み合わせから始めて、「cost-to-go関数」を最小化する戦略を見つけなければなりません。「cost-to-go関数」とは、完璧な解に到達するためのコスト（つまり移動回数）を計算する関数です。目標は、この関数を可能な限り低く抑え、ゲームをできるだけ早く解読できるようにすることです。
特定の手順を順番に実行する必要がありますが、43,252,003,274,489,856,000通り、つまり約43京通りの組み合わせが存在することを考えると、DeepCubeAをランダムに開始させることは現実的ではありません。そこで研究者たちは、DeepCubeAを逆順に訓練しました。DeepCubeAを、解けるようになる手順の中の特別な状態の一つに置き、そこから開始するように指示するのです。
研究者たちは、DeepCubeAを2日間かけて100億通りのルービックキューブの組み合わせで学習させ、30手以内で全ての解読を要求しました。DeepCubeAは1,000個のパズルでテストされ、全てのパズルを解くことに成功し、60%の確率で可能な限り少ない手数で解読しました。どの状態からでも、ルービックキューブは20手以内で解けることが数学的に証明されており、これは「神の数」として知られています。
ロボットがルービックキューブを637ミリ秒で解く
続きを読む
DeepCubeAは完璧ではなく、神の数には程遠い。最短経路は平均21手で、難易度が高いため、ソフトウェアはパズルを解くのに約24秒かかる。トップスピードキューバーでさえ神の数には程遠く、約50手で約4秒でキューブを解くことができる。
「人間の一般的なアルゴリズムは、一番上に十字を描き、次に上の角を描き、次に二番目の層を描き、最後に一番下の層を描きます」とアゴスティネッリ氏はThe Registerに説明した。
これは比較的単純な手順ですが、最短経路からは程遠いものです。可能な限り少ない移動回数で解くには、はるかに多くの思考が必要です。この概念は機械にも適用されます。一般的に、より短い経路を見つけるには、より多くの時間がかかります。
目的のあるおもちゃ
ルービックキューブは単なるおもちゃですが、それを解くために使用されたAIアルゴリズムは、他の多くの問題にも応用できます。研究者たちは、タンパク質の構造を予測し、薬剤師が特定の身体機能を標的とした薬剤を設計するのを支援することに関心を持っています。
「タンパク質の構造は、ルービックキューブや本論文で検討した他のパズルと同様に、多くの可能性を秘めていますが、そのうち解として考えられるのはほんのわずか、多くの場合はたった一つだけです」とアゴスティネッリ氏は述べた。「DeepCubeAアルゴリズムを改良し、タンパク質構造予測を行いたいと考えています。」
「より一般的に言えば、ルービックキューブは経路探索問題です。A地点からB地点へどうやって移動するか？経路探索はロボット工学の分野における大きな課題であり、特に多くの可能性を持つ大規模な環境では、複雑な判断が求められることがあります。DeepCubeAのようなアルゴリズムは、10の19乗から10の62乗の可能な状態を持つ環境において、この経路探索問題を解くことを学習することができ、他の経路探索タスクにも一般化できる可能性があります」と彼は結論付けました。
DeepCubeA のコードはここにあります。®
