Researchers' deep learning algorithm solves Rubik's Cube faster than any human

UCI researchers' deep learning algorithm solves Rubik's Cube faster than any human
The fastest people need about 50 moves to solve a Rubik's Cube. "Our AI takes about 20 moves, most of the time solving it in the minimum number of steps," says the study's senior author, Pierre Baldi, UCI Distinguished Professor of computer science. "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." Credit: Steve Zylius/UCI

Since its invention by a Hungarian architect in 1974, the Rubik's Cube has furrowed the brows of many who have tried to solve it, but the 3-D logic puzzle is no match for an artificial intelligence system created by researchers at the University of California, Irvine.

DeepCubeA, a learning algorithm programmed by UCI scientists and mathematicians, can find the solution in a fraction of a second, without any specific domain knowledge or in-game coaching from humans. 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.

For a study published today in Nature Machine Intelligence, the researchers demonstrated that DeepCubeA solved 100 percent of all test configurations, finding the to the goal state about 60 percent of the time. The algorithm also works on other combinatorial games such as the sliding tile , Lights Out and Sokoban.

"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," said senior author Pierre Baldi, UCI Distinguished Professor of computer science. "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."

The 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.

There are some people, particularly teenagers, who can solve the Rubik's Cube in a hurry, but even they take about 50 moves.

"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."

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 every day through apps such as Siri and Alexa and recommendation engines working behind the scenes of their favorite online services.

"But 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."


Explore further

Professional speedcuber breaks world record on Rubik's cube

More information: Forest Agostinelli et al. Solving the Rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence. 2019.
DOI: 10.1038/s42256-019-0070-z
Journal information: Nature Machine Intelligence

Citation: Researchers' deep learning algorithm solves Rubik's Cube faster than any human (2019, July 15) retrieved 25 August 2019 from https://techxplore.com/news/2019-07-deep-algorithm-rubik-cube-faster.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
220 shares

Feedback to editors

User comments

Jul 16, 2019
"But these systems are not really intelligent; they're brittle, and you can easily break or fool them,"

...how is this different from humans?

(Yes, I know AI is not comparable to human intelligence. That both have the moniker "intelligence" is just a coincidence. I just came back from a deep learning conference, so I'm well aware how these buggers work)

The difference in AI to humans is (currently) the rigid value judgement (loss function) based on which neural networks learn. This is perfect for games or rigidly regulated systems (like traffic) where such a fixed goal can be easily defined. In the case of a game it's "win" (although a better goal is "not lose" - which is a stronger strategy than "win", and also the strategy professional human players employ.)
In the case of traffic it's already quite a bit more complex because there are various goals (at its simplest: "get to destination" and "not crash" - which may be mutually exclusive)

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more