AI solves Rubik’s cube

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.