はじめに
まずは動くものを観察してもらうのが早いかと。
https://rubiks-cube.oboe-cor-anglais.net/
ID:QiitaGuest
Pass:QiitaCube
※動かしてるのが私の私物PCな都合で、繋がったり繋がらなかったり、動いたり動かなかったりします。目に留まったときにメンテします。
※誰かがプログラム的に大量リクエストを送ってきたりしたら閉じます。
GPGPUでルービックキューブの最短解探索
ルービックキューブの最短解探索は単純で、IDA＊アルゴリズムを実装すればOKです。ただし、単純すぎる全探索では探索しきれない物量があるので、いわゆる枝刈り用の距離関数を実装する必要があります。この枝刈り用の関数はルービックキューブの部分的な答えにたどり着くための辞書で、ルービックキューブの状態をできるだけたくさん表現できると高い性能が出ます。極論を言えば、ルービックキューブの全ての状態に対して、解までの手数を全て網羅できるならばそれで良いのです。ただ、実際は記憶しておく領域が足りないので、全網羅は妥協して、足りない分はIDA＊アルゴリズムに手伝ってもらうわけです。
距離関数の網羅性は、単に領域をたくさん使う方法と、数学的に広げる方法の2通りの方向性があります。例えば、左右の対称性を利用すれば、実際に使うメモリ量は表現できる量の半分で、残りは計算しましょう、とかできるわけです。
ところで、GPGPUでこの探索が早くなるのかどうか、という検証をしたいとき、邪魔な要素があります。この数学的な対称性を実装すると、必然的にメモリを参照する回数が増えてしまい、GPUが得意ではない問題に寄ってしまうのです。CPU実行をGPU実行に載せ替えたときに、対称性を考慮しないパターンでどのくらい早くなるのかは確認しておきたいものです。
私はこれを学士論文のテーマとして、2013年に発表しました。メモリを3GBくらい使う実装で、CPU1個（4core）に対して、GPUが5倍くらい仕事をしてくれる、という実験結果を華やかに発表したのです。
しかしながら、このときに作成したソルバーは実用的な性能ではありませんでした。ランダムなキューブに対して、平均35秒ほどの実行時間を要したのです。この当時、数学的な対称性を考慮して距離関数の性能を高めたソルバーでは、ランダムなキューブは3秒ほどで解けていたのです(God's Number is 20)。
では、同じ距離関数を用いたプログラムがGPGPUで早くなるかと言えば、xyzのそれぞれの軸で対象な8分類で試したところ、うまくいかなかったのです。この事実は当時の成果としてはおもしろくなかったのでそっ閉じして卒業しました。
GPU性能の強烈な進化
ここ10年の間で、最近のAIやら何やらの流行りで、GPGPUの性能が信じられないくらい伸びました。私が学生時代に作ったプログラムも微調整で動かすことができ、かつ、GPU使用率が100%に張り付くので、個人用のベンチマーク的に使っており、新しいGPUを購入する度に遊んでました。
今回はRTX 4090を試したのですが、なんとランダムキューブが平均1秒を切ったではありませんか。20手かかる有名なSuperFlipも25秒で解けてしまいます。CPUはRyzen 3950xの16コアCPUを使っているのですが、16コアCPUの20倍以上の性能になったのです。
10年前の実験では、CPUの5倍くらいで喜んでたのですが、CPUの20倍の性能になってしまいました（100万円とかする一部の愛好家向けのCPUには触れないでください）。
私は、個人的にはCPUもGPUも似たような感じで性能が伸びてゆくと想像していたのですが、GPUの性能向上は想像を超えてきました。
GUIとの結合
ルービックキューブは「解を求める問題」と「UIをつくる問題」がかけ離れており、かつ、両方とも簡単な課題ではないので、ソルバーだけだったり、UIだけ、という作品がインターネット上にたくさん転がっています。また、ソルバーとUIを作っても、それぞれの実装の内部構造をうまく受け渡す仕組みがないと繋げることができません。
私も過去にルービックキューブのGUIを作りましたが、ソルバーと繋げる作業は最近やりました。大学生のときにソルバーを作ったわけですが、やはり両者を結合するのはそこそこ大変なのがわかっていたのでサボっていたのです。
では、なぜ今更ソルバーとUIを結合したのかと言えば、ソルバーの性能が面白いことになってきたのでUIを付けたくなったのです。いままではCUIで「解けたよ」と文字列が出てくるだけだったものが、GUIとして目の前で動いたときは感動しました。
ソースコード
GUIは最近の作品ですが、ソルバーは学部生の頃に作ったものに手を入れただけなので、作り直したいところではあるのですが、そんな時間はありません。
UI
ソルバー
※UIとソルバーが合体してるコードは公開していません。