Researchers at the University of California, Irvine, created an artificial intelligence system that can solve a Rubik’s Cube faster than most humans, according to a new study published in Nature Machine Intelligence.
The deep learning algorithm, known as DeepCubeA, learns how to solve increasingly difficult states in reverse from the goal state without the need for any specific domain knowledge or coaching from humans.
While there are some incredibly talented people that are capable of solving a Rubik’s Cube in a matter of seconds, most people attempting to solve a cube in a hurry require about 50 moves to complete the puzzle. In comparison, the AI system developed by the UCI researchers only needs around 20 moves to finish.
“Our AI takes about 20 moves, most of the time solving it in the minimum number of steps,” said the study’s senior author, Pierre Baldi, UCI Distinguished Professor of computer science.
“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.”
It’s not an easy task for an AI system to complete considering there are literally billions of different completion paths for a Rubik’s cube to reach its goal state – each of the cube’s six sides must display a solid color.
According to the abstract of the study, DeepCubeA was able to solve 100% of all test configurations, finding a shortest path to the goal state 60.3% of the time.
The algorithm also works for other combinatorial games.
“DeepCubeA generalizes to other combinatorial puzzles and is able to solve the 15 puzzle, 24 puzzle, 35 puzzle, 48 puzzle, Lights Out and Sokoban, finding a shortest path in the majority of verifiable cases,” the abstract said.
Pierre Baldi said:
“Artificial intelligence 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.
“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.”
Journal Citation
“Solving the Rubik’s cube with deep reinforcement learning and search”
Forest Agostinelli, Stephen McAleer, Alexander Shmakov & Pierre Baldi
Nature Machine Intelligence (2019)
DOI: https://doi.org/10.1038/s42256-019-0070-z
Interesting related article: “What is an algorithm?“