AI solves Rubik's Cube in 1.2 seconds (that's three times slower than a non-AI algorithm)

Even so, human nerds are left in the dust and this neural net can be used for other tricks

A new neural-network can solve a Rubik’s cube twice as fast as the fastest human – though roughly three times slower than the fastest dumb algorithm – according to research published in Nature Machine Intelligence on Monday.

Though the AI approach is not a nippy as the fastest traditional computational method, specifically the world-beating min2phase algorithm out of MIT, it has promise beyond old-school playground puzzles: for one thing, it could be put to better use studying proteins.

People have been fascinated by the popular toy since it was created in the late 1970s. The World Cube Association, an organization focused on combination puzzle games like the Rubik’s Cube, run several competitions every year to challenge fans to solve it as fast as they can. People who enter these contests are known as speedcubers, and the current world record belongs to Yusheng Du, a Chinese speedcuber that cracked the puzzle in just 3.47 seconds.

But Du is probably no match for machine learning software like DeepCubeA. The system developed by a team of researchers at the University of California, Irvine (UCI), made up of a deep neural network can solve a Rubik’s Cube in an average of 28 moves in 1.2 seconds, Forest Agostinelli, first author of the paper and a PhD student at UCI, told The Register.

That's fast, but not as fast as the robotic system using the min2phase algorithm developed by researchers at MIT last year.

Min2phase doesn't have a neural network, isn't trained, and doesn't use any machine learning techniques: it's programmed purely to solve cubes and that's all it can do (and it does it extremely quickly), whereas DeepCubeA has the potential to do more. On the one hand, it's obvious why Min2phase should be faster, though on the other hand, we've seen AI code operate faster on basic data structures than traditional dumb algorithms.

The number of God

DeepCubeA was trained using reinforcement learning. Starting with a random combination of the puzzle, it has to find a strategy that will minimize its “cost-to-go-function”, which calculates the cost - or amount of moves - to reach a perfect solved state. The goal is to keep the function as low as possible so the game can be cracked as quickly as possible.

You need to perform a specific sequence of moves in order, considering there are 43,252,003,274,489,856,000 – about 43 quintillion possible combinations, it’s not feasible to let DeepCubeA start randomly. So, the researchers trained it in reverse. It is put in one of the special states in the sequence that will lead to it being solved and asked to start from there.

The researchers trained DeepCubeA over two days with 10 billion different Rubik’s Cube combinations and tasked it to decode all of them within 30 moves. It was tested on 1,000 puzzles and managed to solve all of them, and did it in the fewest moves possible 60 per cent of the time. It has been mathematically proven that starting from any state, the Rubik’s cube can be cracked in 20 moves or fewer, a figure known as God’s Number.

DeepCubeA isn’t perfect and doesn’t quite reach God’s Number. The shortest path it takes is on average 21 moves. Since that's challenging, it takes the software about 24 seconds to complete the puzzle. Top speedcubers are also far from God’s Number, and take about 50 moves to solve the cube in about four seconds for top players.

“A common algorithm for humans is to get the cross on the top, then the top corners, then second layer, then bottom layer,” Agostinelli explained to The Register.

"This is a relatively simple procedure to follow, however, it is far from the shortest path. To solve it in the fewest number of moves possible requires much more thought. This concept is also at play for the machine. Finding shorter paths will, generally, take more time."

Toys with a purpose

Although the Rubik’s Cube is a mere toy, the AI algorithms used to solve it can be applied to a number of other problems. The researchers are interested in predicting the structure of proteins to help pharmacists design drugs to target specific bodily functions.

“The structure of proteins, like the Rubik's Cube and other puzzles investigated in this paper, have many possibilities but only a few, often times only one, of these possibilities are considered to be a solution," said Agostinelli. "We would like to modify the DeepCubeA algorithm to do protein structure prediction."

“More generally, 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. An algorithm like DeepCubeA is able to learn to solve this path finding problem in environments that have 10¹⁹ to 10⁶²; possible states and could be generalized for other path finding tasks,” he concluded.

The code for DeepCubeA can be found here. ®