DeepCubeA, a deep reinforcement learning algorithm created by a team of scientists at the University of California, Irvine, can find the solution for the Rubik’s cube in a fraction of a second. The algorithm solved 100% of all test configurations, finding the shortest path to the goal state 60.3% of the time. It also worked on other combinatorial games such as the sliding tile puzzles (the 15 puzzle, 24 puzzle, 35 puzzle and 48 puzzle), Lights Out and Sokoban.
The fastest people need about 50 moves to solve a Rubik’s cube. Image credit: Steve Zylius / University of California, Irvine.
“Artificial intelligence (AI) can defeat the world’s best human chess and Go players, but some of the more difficult puzzles, such as the Rubik’s cube, had not been solved by computers, so we thought they were open for AI approaches,” said Professor Pierre Baldi, a researcher in the Departments of Computer Science and Statistics at the University of California, Irvine.
“The solution to the Rubik’s cube involves more symbolic, mathematical and abstract thinking, so a deep learning machine that can crack such a puzzle is getting closer to becoming a system that can think, reason, plan and make decisions.”
Professor Baldi’s team was interested in understanding how and why the AI made its moves and how long it took to perfect its method.
The scientists started with a computer simulation of a completed puzzle and then scrambled the cube.
Once the code was in place and running, DeepCubeA trained in isolation for two days, solving an increasingly difficult series of combinations.
“It learned on its own,” Professor Baldi noted.
There are some people, particularly teenagers, who can solve the Rubik’s cube in a hurry, but even they take about 50 moves.
“Our AI takes about 20 moves, most of the time solving it in the minimum number of steps,” Professor Baldi said.
“Right there, you can see the strategy is different, so my best guess is that the AI’s form of reasoning is completely different from a human’s.”
The team’s work was published in the journal Nature Machine Intelligence.
_____
Forest Agostinelli et al. Solving the Rubik’s cube with deep reinforcement learning and search. Nature Machine Intelligence, published online July 15, 2019; doi: 10.1038/s42256-019-0070-z
