This AI Can Solve Rubik Cube Faster Than Any Human
Researchers and mathematicians at the University of California (UCI), Irvine have developed an artificial intelligence (AI) algorithm that can solve the Rubik’s Cube in just over a second.
Dubbed as DeepCubeA, this deep reinforcement learning algorithm can solve the Rubik’s Cube in a fraction of a second “without any domain knowledge or in-game coaching from humans,” according a press release from the university.
DeepCubeA, the subject of the study, was published in Nature Machine Intelligence on July 15, 2019.
“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 distinguished Professor of Computer Science at UCI, said in a statement.
“This work presents an AI system that can automatically learn how to solve the iconic Rubik’s Cube and other problems characterized by a vast number of possibilities and a very small number of solutions, and where random moves are unlikely to lead to a solution,” Baldi added.
“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.
In the study, the researchers demonstrated that DeepCubeA solved 100% of all test configurations and found the shortest path to the solution about 60 percent of the time, where all six sides displayed a solid color.
The algorithm also works on other combinatorial games such as the sliding tile puzzle, Lights Out and Sokoban, say the researchers.
What makes this AI special is that it learned how to solve the Rubik on its own. Researchers were interested in understanding how and why the AI made its moves and how long it took to perfect its method.
They 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,” Baldi noted.
Even some people, particularly teenagers, who can solve the Rubik’s Cube in a hurry, take about 50 moves.
“Our AI takes about 20 moves, most of the time solving it in the minimum number of steps. 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,” he added.
According to Baldi, the ultimate goal of projects such as this one is to build a new generation of AI deep-learning systems, which are more advanced than those used in commercially available apps such as Siri and Alexa.
“But these systems are not really intelligent; they’re brittle, and you can easily break or fool them. 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.”