 |
| © File Photo / AFP/ Getty Images |
A machine has taught itself to solve a Rubik’s Cube without human assistance, according to a group of UC Irvine researchers.
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 and his team, which includes one professor and two other students, 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 search 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.
