How quickly can AI solve a Rubik's Cube?
By PETER HOLLEY | The Washington Post | Published: July 16, 2019
Few things reveal the limits of someone's problem-solving skills faster than a Rubik's cube, the multi-colored, three-dimensional puzzle that has befuddled so many since the 1970s.
Though the cube has furrowed countless human brows over the years, it's not much of a challenge for an emerging group of hyper-intelligent machines, as it turns out.
This week, the University of California Irvine announced that an artificially intelligent system solved the puzzle in just over a second, besting the current human world record by more than two seconds.
That system, known as DeepCubeA - a reinforcement learning algorithm programmed by UCI computer scientists and mathematicians - solved the puzzle on its own, without any prior knowledge of the game or coaching from its human handlers, according to the university.
The feat is even more impressive considering that there are billions of potential moves available to a Rubik's Cube player, with the puzzle's six sides and nine sections, but only a single goal: each of the cube's six sides displaying a solid color.
"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," senior author Pierre Baldi, a professor of computer science, said in a statement released by the university. "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."
Researchers published their findings in Nature Machine Intelligence, noting that their system's algorithm was given 10 billion combinations of the puzzle. The goal, researchers wrote was to solve each combination within 30 moves.
DeepCubeA solved 100 percent of all test configurations, researchers wrote, and located the shortest path to solving the puzzle just over 60 percent of the time. Researchers said the algorithm also works on other similar games such as the sliding tile puzzle, Lights Out and Sokoban.
Highly skilled humans are able to tackle a Rubik's Cube in about 50 moves, but the AI system is able to solve the cube in about 20 moves, usually in the minimum number of steps possible, researcher said.
What makes the UCI algorithm unique, researchers said, is that it doesn't rely on a neural network - a set of algorithms designed to find underlying relationships by mimicking how the human brain processes information. Nor did the algorithm rely on machine learning techniques, a system that allows AI to learn by identifying patterns and using inference with minimal human intervention.
The algorithm was merely programmed to solve the puzzle, leaving researchers with a limited understanding of how it did so. To perfect its abilities, DeepCube trained in isolation for two days, refining its skill as it unpacked the Rubik's Cube.
"It learned on its own," Baldi told the BBC. "My best guess is that the AI's form of reasoning is completely different from a human's."
Human world record holders for solving the Rubik's Cube are down to about 3.5 seconds, more than 15 seconds less than record times in the early 1980s, according to the World Cube Association.
The UCI algorithm is impressive, but it's not the fastest non-human conqueror of the Rubik's Cube around these days. In Germany, researchers built a robot in 2016 named Sub1 Reloaded that solved the puzzle in 0.637 seconds.
Last year, their record was shattered by a pair of American researchers who built a robot that solved the puzzle in 0.38 seconds.