Research press release


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 関連誌のハイライトを皆様にお届けいたします。