ルービックキューブを解くAIを作ってみた
こんにちは、にゃにゃんです。
この記事はSpeedcubing Advent Calendar 2021の19日目の記事です。
18日はSinpei Arakiさんの地域団体についてでした。
20日はタニシさんのFB100本ノックです。
ルービックキューブを解くプログラムを主に"AI"の視点から解説し、私独自のアルゴリズムを紹介し、最後に性能を見てみます。
技術的な話はなるべく平易に書きました。気楽にお読みください。
はじめに
ルービックキューブを解く"AI"と言えば、機械学習を使った有名なものにはDeepCubeAがあります。
そして、古典的(？)な"AI"を考えれば、min2phaseやkociembaなどの現在よく使われるアルゴリズムがあります。
DeepCubeAの特徴
機械学習を用いてルービックキューブを解くプロジェクトとしてDeepCubeAを紹介しました。もう少し詳しく見ていきましょう。
DeepCubeAは主に2つの技術によってできています。1つ目は「探索」、2つ目は「機械学習」です。探索についてはあまりこの記事の本質ではないので割愛して、機械学習について軽く解説します。
DeepCubeAの機械学習は、簡単に言うとルービックキューブの面の状態を入力するとその状態から完成までの手数を推測してくれるAI(*1)を作ることを目指します。このAIを使って探索を行い、解までの手順を導きます。
人間の私は多くの場合について、ルービックキューブをぱっと見て「うーん、これは〇〇手で揃うな～」などとはわかりません(*2)が、それをAIにやってもらおうというのです。
"AI"と聞くとなんだか人知を超越したもののように感じますが、中身を知れば大したことはありません。簡単に解説すると、今良く言われる"AI"は多くの場合、動物の脳を模したモデルを用いて所望を達成します。
もう一度繰り返します。AIは動物の脳を模したものです。
そして、人間の多くはルービックキューブを渡されて「これは○○手で揃いそうだな」などとは多くの場合、わかりません。
つまり、DeepCubeAのAIがやろうとしていることはかなり難しいのです。人間の脳になかなかできないことを脳を模したモデルで行おうとしているのですから。
DeepCubeAではこの難しさを、とにかく大きなモデルを使うことで解決しました。脳細胞の数自体が多ければ頭が良くなりそうですよね。そういうことです。
大きなモデルを使うと問題が生じます。手数の推測にかかる計算の回数が単純に増えるので、それに応じて計算時間が増えてしまうのです。他にも問題があります。ルービックキューブを見て頓珍漢な手数を推測する状態から、いい感じの手数を推測する段階まで訓練するのが大変なのです。
実際にDeepCubeAの論文やプログラムを読んでみたり自分で手を動かしてどんなものかを確認してみたのですが、DeepCubeAは計算力の暴力で全てを解決している印象を受けました。
(*1)わかりやすく(？)AIと書きましたが、この文脈ではニューラルネットワークのことを指します。
(*2)PLLとかZBLLとかコミュテータならわかるかもしれませんが、ランダム状態のルービックキューブを渡されて確率的に手数を当てる(ルービックキューブは18手で揃う場合が最頻です)以外のことは通常できないと思います。
その他のルービックキューブを解くプログラム
min2phaseやkociembaのアルゴリズムでは探索部分はDeepCubeAとある程度似ていますが、DeepCubeAでAIを使って行っていた「あと何手で揃いそうか」を求める部分を、精度は低いものの簡単な関数で行っています。機械学習は使っていません(私が知る限り)。
例えばルービックキューブを揃えるにあたって、コーナーとエッジの2種類のパーツがありますが、コーナーを無視してエッジだけを揃える最短手数を考えると、実はうまく条件をつけると全パターン前計算できます。同様にエッジを無視してコーナーだけを揃える場合を計算して、ルービックキューブの状態についてこの2つの値の大きな方を残り手数の推定値として使います(*3)。
そして、この推定値の精度や回転処理の都合でルービックキューブを解くという行為を2つの段階に分けて行います。こうすることで高速に動作させることが可能になります。
(*3)実際にはルービックキューブを揃える過程を2段階に分けて行うので、1段階目ではEOとCO、そして一部のEPを、2段階目では残り、つまりEPとCPを揃えるので書き方に語弊がありますが、イメージとしてはこんな感じです。
私が考えた新たなアルゴリズム
さて、本題です。私は紹介した2つの系統のアルゴリズムをまとめて新たにルービックキューブを解くアルゴリズムを考えてみました。
DeepCubeAではAIを使うことで任意のルービックキューブの状態において残り手数を予測していましたが、これが難しいのが難点でした。ということで、既存のアルゴリズムと同じように2段階に分けてルービックキューブを解くことにしました。こうすることで残り手数の推定がぐんと簡単になります。
既存の手数推定関数よりも精度が良くてそれなりに高速な新たな手数推定関数を考えたのです。
手数推定関数の入力にはDeepCubeAと同じようにステッカーの状態を使う他、追加で既存アルゴリズムの手数推定関数に使われるパラメータも使いました。
これを機械学習にかけてみると、悪くはない結果になりました。ということで、この私が考えた手数推測関数を使ってルービックキューブを解いてみます。
実際に新手法と既存手法を比べてみた
比較として探索アルゴリズムは全く同じ(*4)で既存の手数推測関数を使った結果も載せます。
テストのスクランブルには以下を使いました。
L U2 F2 R' U2 B2 R' D2 L2 F2 U2 D R' F' D' F2 R B2 U
新手法
scramble: L U2 F2 R' U2 B2 R' D2 L2 F2 U2 D R' F' D' F2 R B2 U
start!
phase0 176 solutions found; visiited 2666 nodes
phase1 searched; length 21; visiited 5242 nodes
7908
solved in 305 ms
length 21
solution: D R F' B2 D R D R2 U L' D2 L2 U' R2 B2 U' D' L2 U' R2 U既存手法
scramble: L U2 F2 R' U2 B2 R' D2 L2 F2 U2 D R' F' D' F2 R B2 U
start!
phase0 64 solutions found; visiited 7104 nodes
phase1 searched; length 21; visiited 28738 nodes
35842
solved in 313 ms
length 21
solution: D L' U D' L U2 F' B' U2 B F2 L2 U' D2 L2 D' B2 R2 L2 D F2出力した解は違いますが、どちらも21手でこのスクランブルを解いてくれました。
もっとたくさんのスクランブルで実験してみましょう。ルービックキューブを完成状態から100回ランダムに回した状態をそれぞれのプログラムに100回ずつ解かせました。0.2秒程度の時間をいっぱい使ってなるべく手数の短い解を出力させてみます。
新手法
found 100 solutions 100.0 persent
avg_len 22.54 moves
avg_vis 5452.56 nodes
avg_tim 0.21835403442382811 second既存手法
found 100 solutions 100.0 persent
avg_len 21.71 moves
avg_vis 25569.07 nodes
avg_tim 0.21729260921478272 secondavg_lenが解の平均手数です。うーん、既存手法の方が性能が良い(短い手数を出力している)ですね…
ということで、結局既存手法が強いということがわかったというのがオチです…悲しい…
余談ですが、今回の既存手法のプログラムは既存手法に若干不利な書き方になっています(*5)
(*4)探索アルゴリズムは既存手法で一般的なIterative Deepening A*アルゴリズムではなく、DeepCubeAで使われたBatch Weighted A*アルゴリズムを使いました。Batch Weighted A*は一般的に訪問ノード数が少なくなるものの、最短ルートを出力する確率は低くなります。
(*5)既存手法はルービックキューブの状態をインデックス化して回転処理を高速にしますが、今回は新手法との比較のためにそれをしていません。それでも既存手法の方が高性能なので、残念ですね……
新手法の良いところ
一応新手法の良いところを言うと、「とりあえず一つ解を見つける」プログラムで100回計測すると、以下のようになります。
新手法
found 100 solutions 100.0 persent
avg_len 23.63 moves
avg_vis 5705.28 nodes
avg_tim 0.3171394348144531 second既存手法
found 100 solutions 100.0 persent
avg_len 22.58 moves
avg_vis 34700.42 nodes
avg_tim 0.48162040948867796 second解の手数は既存手法の方が短いですが、avg_visという項目が新手法は既存手法の16%程度になっています。これはルービックキューブの状態を検査した回数なので、新手法の方が少ない検査回数でルービックキューブを解けていることになります。これは、細かい話を置いておくと新手法の手数推定関数が既存手法の手数推定関数よりも性能が良いことを表します。そして、計算環境によってはこの良さが優位になって性能が良くなる可能性があります(*6)。まあ、一応なのですが…
(*6)計算資源の乏しい環境で、うまく機械学習したモデルをチューニングすると少しだけ既存手法よりも性能が上がりそうなことを確認しました。
余談です。時間いっぱい使って解を探索する方が一つだけ解を見つけるのよりも高速になっていて不思議ですが、そういうことはアルゴリズムの性質上大いに考えられます。あとは、後者については私のパソコンで機械学習をしながらベンチマークを取ったのでそれで遅くなっている気がします(おい)
なんでもAIに任せるな
今回、実際に手を動かして実験してみたところ、結局既存手法の方が性能が良さそうというオチになってしまいました。
なんでもAI(*7)に任せるな
AIに頼ればあまり頭を使わずに問題を解決できることが多々あります。しかし、人間が頭を捻って考えたアルゴリズムがあるのであれば、それを使うのは賢い選択であることが多いです。
もちろん、AIに任せることでプログラムの作者が該当の問題に詳しくなくてもある程度のパフォーマンスを出せることもあります。ルービックキューブではありませんが、私が自分自身知識に乏しいオセロAIで、機械学習を使って世界1位を取れたこともこのためです。
AIを使えば解決できそうな問題については、本当にAIが有効な手段なのかを考えたほうが幸せになれるような気が私はしています(*8)。
(*7)ここでは狭義に機械学習とします。AIという言葉は定義が曖昧で難しいです…
(*8)AIを使うことがそのプログラムのパフォーマンス以外に利点がある場合、それも加味すべきなのでますますややこしいです。
余談
もしこの記事を書くのに使ったコードを見たい方がいらっしゃいましたらこちらのtwo_phaseディレクトリをご覧ください。
https://github.com/Nyanyan/ShallowCubeA
実は1段階でうまく解けないかをone_phaseディレクトリで模索していたのですが、だめそうでした…
この記事は半分くらいネタ記事です。ベンチマークの測定が超絶適当なので、気が向いたら真面目に計測します。
ということで、ここまで読んでくださってありがとうございました！