Research press release

ルービックキューブを解くAI

Nature Machine Intelligence

AI solves Rubik’s cube

ルービックキューブやその他の組み合わせパズルを解くことのできるディープラーニングアルゴリズムについて報告する論文が、今週掲載される。多数の組み合わせがあるパズルを解くアルゴリズムは、タンパク質の折りたたみなどの科学的問題を解決する仕組みに関する洞察をもたらす可能性がある。

組み合わせパズルの最短解を発見することは難しい。一般に、そうしたパズルの解は、ランダムな手では発見できない。伝統的なアルゴリズムでも組み合わせパズルを解くことはできるが、そのために必要とされる計算量とメモリーの大きさは、規模の大きいパズルをこの方法で解くことを非現実的なものにしている。

今回、Pierre Baldiたちは、自身の前回のプロジェクトDeepCubeからDeepCubeAを開発した。DeepCubeAはゴール状態から出発し、強化学習と経路発見法の組み合わせを用いて逆向きにたどることでパズルを解く。DeepCubeAは、ほとんどの場合、パズルの最短経路を発見することができ、その際に用いるメモリーは従来のアルゴリズムよりも少ない。著者らはこのアルゴリズムが、ルービックキューブ、ライツアウト、倉庫番、および48枚のタイルからなるスライドパズルなど、より規模の大きい問題を解けることを示している。

著者たちは、同じアプローチを用いて広範なゲームを解けたことから、このアプローチをより規模の大きい問題に適用して最適に近い解を発見できる可能性があると示唆している。

A deep-learning algorithm that can solve the Rubik’s Cube and other combinatorial puzzles is published this week in Nature Machine Intelligence. Solving puzzles that have a large number of combinations can provide insights into how scientific problems are solved, such as protein folding.

Finding the shortest solution for a combinatorial puzzle is hard. Solutions to such puzzles generally cannot be found by making random moves. Traditional algorithms can solve combinatorial puzzles but their computational and memory requirements make them impractical for large puzzles.

Pierre Baldi and colleagues developed DeepCubeA from their prior project DeepCube. DeepCubeA starts from the goal state and works backwards using a combination of reinforcement learning and path-finding methods to solve the puzzles. DeepCubeA is able to identify the shortest path for puzzles in most cases and can do so using less memory than traditional algorithms. The authors show that it can solve the Rubik’s Cube, Lights Out, Sokoban and larger problems, including a 48-tile sliding puzzle.

The authors suggest that the wide range of games solved using the same approach means that it could be used on larger problems to find close to optimal solutions.

doi: 10.1038/s42256-019-0070-z

「Nature 関連誌注目のハイライト」は、ネイチャー広報部門が報道関係者向けに作成したリリースを翻訳したものです。より正確かつ詳細な情報が必要な場合には、必ず原著論文をご覧ください。

注目のハイライト

メールマガジンリストの「Nature 関連誌今週のハイライト」にチェックをいれていただきますと、毎週最新のNature 関連誌のハイライトを皆様にお届けいたします。

「注目のハイライト」記事一覧へ戻る

プライバシーマーク制度