Rubik's Cube Solved in 'Fraction of a Second' by Artificial Intelligence Machine Learning Algorithm

Researchers have developed an AI algorithm which can solve a Rubik's Cube in a fraction of a second, according to a study published in the journal Nature Machine Intelligence.

The system, known as DeepCubeA, uses a form of machine learning which teaches itself how to play in order to crack the puzzle without being specifically coached by humans.

"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," Pierre Baldi, one of the developers of the algorithm and computer scientist from the University of California, Irvine, said in a statement.

According to Baldi, the latest development could herald a new generation of artificial intelligence (AI) deep-learning systems which are more advanced than those used in commercially available applications such as Siri and Alexa.

"These systems are not really intelligent; they're brittle, and you can easily break or fool them," Baldi said. "How do we create advanced AI that is smarter, more robust and capable of reasoning, understanding and planning? This work is a step toward this hefty goal."

"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," he said.

Solving a Rubik's Cube is no easy task. In fact, a normal 3x3 cube contains more than 43 quintillion potential avenues toward completing the puzzle—where all sides show the same color. Nevertheless, DeepCubeA "solved 100 percent of all test configurations" using a "deep learning" method, according to the study.

"It is very unlikely that the machine could stumble upon a solution to the Rubik's Cube," Forest Agostinelli, a co-author of the paper from Irvine, told Newsweek. "So, what we did is we started from the goal—all sides having the same color—and worked backward."

"It would be very easy for a machine to learn to solve a Cube that has been scrambled only a few times. After it learns how to solve these relatively easy instances of the Rubik's Cube, it can then learn how to solve harder instances," he said. "We did not tell the machine learning algorithm what was easy and what was hard, instead, we gave it many examples, some easy and some hard, and it learned on its own how to solve them."

Not only was the algorithm consistently able to solve the puzzle, the scientists reported that it found the shortest route toward the goal in around 60 percent of its attempts.

"Our AI takes about 20 moves, most of the time solving it in the minimum number of steps," 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."

At present, this means that the algorithm is roughly on par with the current human record for the fewest number of moves to complete a Rubik's Cube. However, the AI is faster than the quickest human, Feliks Zemdegs, who solved the puzzle in a record 4.22 seconds in 2018.

According to the researchers, the latest results could have implications beyond the world of puzzles.

"Problems with very large state spaces and only a few solutions come up frequently in the natural sciences and robotics—for example, protein structure prediction," Agostinelli said. "The structure of proteins, like the Rubik's Cube and other puzzles investigated in this paper, has many possibilities but only a few—often times only one—of these possibilities are considered to be a solution. We would like to modify the DeepCubeA algorithm to do protein structure prediction."

"Furthermore, the Rubik's Cube is a path finding problem: how do I get from point A to point B? Path-finding is a big problem in the field of robotics and can require one to make complicated decisions; especially in large environments with many possibilities," he said. "An algorithm like DeepCubeA is able to learn to solve this path finding problem in environments that have 10^19 to 10^62 possible states and could be generalized for other path finding tasks."

The Rubik's Cube is the world's top-selling puzzle game with more than 400 million units purchased worldwide, according to an estimate on the official website. It was invented in 1974, by Hungarian architect Ernő Rubik.

This article was updated to include comments from Forest Agostinelli.

Rubik's cube
Rubik's Cube toy on black background with reflection. Andrew Spencer / Getty Images
Rubik's Cube Solved in 'Fraction of a Second' by Artificial Intelligence Machine Learning Algorithm | Tech & Science
{{label}}
{{title}}
EDITOR'S PICK