Home Science New algorithm solves Rubik’s Cube in just 1 second

New algorithm solves Rubik’s Cube in just 1 second

Solving the Rubik’s cube with deep reinforcement learning and search.

Image: Pixabay

The basic Rubik’s cube has 24 tiles and is shorter than a container of Coke. Originally created by Hungarian sculptor and professor of architecture Ernő Rubik in 1974, the Rubic’s cube has a large state space with a single goal state. The goal state is unlikely to be accessed using sequences of randomly generated moves, posing unique challenges for machine learning.

Recently, scientists at the University of California, Irvine solved the Rubik’s cube in 1 second using DeepCubeA, a deep reinforcement learning algorithm that learns how to solve increasingly difficult states in reverse from the goal state without any specific domain knowledge.

The algorithm can find the solution in a fraction of a second, without any specific domain knowledge or in-game coaching from humans.

Senior author Pierre Baldi, UC Irvine distinguished professor of computer science 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.”

“This is no simple task considering that the cube has completion paths numbering in the billions but only one goal state — each of six sides displaying a solid color — which apparently can’t be found through random moves.”

To understand how and why the AI made its moves and how long it took to perfect its method, scientists begin with a computer simulation of a completed puzzle and then scrambled the cube. When the code was set up and running, DeepCubeA trained in isolation for two days, illuminating an undeniably troublesome series of combinations.

Baldi said, “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.”

The veteran computer scientist said the ultimate goal of projects such as this one is to build the next generation of AI systems. Whether they know it or not, people are touched by artificial intelligence every day through apps such as Siri and Alexa and recommendation engines working behind the scenes of their favorite online services.

The details of the algorithm are published in Nature Machine Intelligence.