In 1974, an architecture professor named Erno Rubik built a movable piece of art to help his students understand three-dimensional problems. Though his own creation took him more than a month to solve, it soon became an iconic puzzle game, the Rubik’s cube.
The goal of the game is to re-arrange the faces of a cube decorated with 54 multi-colored squares so that each face shows a solid block of color. There are 43 quintillion potential ways to arrange the squares but only one solution. Those numbers make the game one of the most challenging so-called combinatorial puzzles for people and for artificial intelligence (AI).
“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,” University of California, Irvine, computer scientist Pierre Baldi said in a press release.
Now Baldi and his team say they have created an AI that can solve the Rubik’s cube. The researchers say the work is a step toward making an AI capable of higher-level thinking.
“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.
Self-Taught Skills
Baldi and team developed an artificial intelligence called DeepCubeA. The AI learns to solve the Rubik’s cube by starting at the goal state – a finished puzzle – and then working backward. The AI makes random moves as it works in reverse but incorporates what it learns from each attempt into figuring out the next best move. The end result is an AI that can solve combinatorial puzzles without relying on human knowledge.
“It learned on its own,” Baldi said.
Minimum Moves
The researchers then challenged DeepCubeA to solve 1,000 virtual Rubik’s cube problems. And they made it difficult. The researchers scrambled the puzzle 1,000 to 10,000 times and even included a few puzzles that require the most number of moves to solve. The AI passed every test with flying – er, solid – colors. DeepCubeA found a solution 100 percent of the time the researchers report this week in the journal Nature Machine Intelligence. And it used the least number of moves to solve the puzzle for more than half the trials.
“Our AI takes about 20 moves, most of the time solving it in the minimum number of steps,” Baldi said. Some of the best human Rubik’s cube solvers need 50 or so moves to solve the game. DeepCubeA performed just as well on other popular combinatorial puzzles like sliding tiles, Lights Out and Sokoban the team found.
Despite the accomplishment, Baldi sees bigger things ahead for AI. “These systems are not really intelligent; they’re brittle, and you can easily break or fool them,” he 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.”
