「知恵の輪」攻略法、深層学習で自動計算 米研究チームが開発：Innovative Tech

[山下裕毅，ITmedia]

Innovative Tech：

このコーナーでは、テクノロジーの最新研究を紹介するWebメディア「Seamless」を主宰する山下裕毅氏が執筆。新規性の高い科学論文を山下氏がピックアップし、解説する。

　米テキサス大学オースティン校とカナダ・マギル大学による研究チームが開発した「C-Space Tunnel Discovery for Puzzle Path Planning」は、パズル「知恵の輪」の攻略を計算する深層学習フレームワークだ。

知恵の輪の離脱解法をシミュレーション

さらに難解な知恵の輪の離脱解法もシミュレーション

　簡単に外せない2つ以上の物体を脱着して遊ぶ知恵の輪は、シンプルでありながら奥が深いゲーム。今回は、知恵の輪を外すための経路を自動で導き出す解法アルゴリズムを開発した。

　今回のアプローチでは、お互いの形状から解法に関与している可能性の高いポイントを特定し、衝突しないポイント同士の組み合わせペアをセット。このペアを滑らせる際の向きや回転を生成し、それらをつなぎ合わせ一連の経路（スタートからゴールまでの最短経路）を構築する。これらのパイプラインを深層学習ネットワークで訓練する。

　知恵の輪攻略で重要なのは、狭い隙間や薄い部分をどう生かすかにある。今回のアプローチでも、お互いの狭い隙間同士をどの向きでどのように滑らせるか、一方の隙間がもう片方の薄い部分をどう滑らせるかなど、狭い隙間と薄い部分を効率的に発見し、ナビゲートする能力が必要とされる。どれだけ難解であっても、この手法が広く有効であると仮定して計算しているという。

解法のパイプライン

離脱経路をシミュレーションしている様子

　評価実験の結果、難易度の高い問題でも高精度の成功率を示し、これまでの既存方法と比較しても成功率が高く、難解な問題の攻略にも成功したという。