AI solves Rubik’s cube
Nature Machine Intelligence
July 16, 2019
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
Research highlights
-
May 24
Biotechnology: Tomatoes engineered to produce vitamin DNature Plants
-
May 20
Conservation: Web of unmonitored global arachnid trade revealedCommunications Biology
-
May 20
Psychology: People with neutral attitudes towards vaccines are closer to anti-vaccine viewsScientific Reports
-
May 19
Climate change: Tree deaths increasing in AustraliaNature
-
May 18
Evolution: A middle Pleistocene hominin molar from LaosNature Communications
-
May 18
Biotechnology: Contact lens measures pressure and delivers glaucoma drugNature Communications