FAIR AND SQUARE
Project developed by UC Irvine researchers masters the challenge without human input.
A machine has learned to solve a Rubik’s Cube on its own, UC Irvine researchers say.
A machine has taught itself to solve a Rubik’s Cube without human assistance, a group of UC Irvine researchers said.
Two algorithms developed by the researchers, collectively called Deep Cube, typically can solve the 3-D combination puzzle within 30 moves, which is less than or equal to systems that use human knowledge, according to the team’s research paper. Less than 5.8% of the world’s population can solve the Rubik’s Cube, according to the Rubik’s website.
“At first I didn’t think it was possible to solve the Rubik’s Cube without any human data or knowledge,” said Stephen McAleer, a UCI doctoral student.
The trick, he said, is to present an advanced computer with a solved Rubik’s Cube and let it unscramble the puzzle bit by bit.
The researchers call this algorithm “autodidactic iteration,” in which the machine works backward to teach itself the moves that solve the puzzle.
In the second algorithm, the trained neural networks use the moves learned in the first algorithm to solve the cube. The machine “plays” with the puzzle and learns how to solve it from any starting point, McAleer said.
McAleer’s teamhas one professor and two other students. They submitted their research in May for consideration for publication at the Conference on Neural Information Processing Systems later this year.
If the group used a reinforcement learning approach, in which the machine was rewarded for every step it took that brought it closer to solving the puzzle, it would be “impossible for neural networks to know when it’s in a good or bad state,” McAleer said.
The group was inspired by a research paper that used neural networks and an advanced method called the “Monte Carlo tree search” to teach artificial intelligence to play the strategy board game Go.
The group launched the project to push artificial intelligence to go beyond pattern recognition and to reason about problems, McAleer said.
“In order to solve the Rubik’s Cube, this artificial intelligence has to reason symbolically,” he said. “It has to think about how it’s going to manipulate this mathematical structure.”
McAleer said the next step is to see how the research could be applied in biology, such as in protein folding, the process by which a protein structure assumes its functional shape or conformation.