UC Irvine Deep Learning Machine Teaches Itself To Solve A Rubik's Cube
Anyone who has lived through the 1980s knows how maddeningly difficult it is to solve a Rubik's Cube, and to accomplish the feat without peeling the stickers off and rearranging them. It's not just challenging for humans, either. Apparently the six-sided contraption presents a special kind of challenge to modern deep learning techniques that makes it more difficult than, say, learning to play chess or Go. That used to be the case, anyway. Researchers from the University of California, Irvine, have developed a new deep learning technique that can teach itself to solve the Rubik's Cube.
What they come up with is very different than an algorithm designed to solve the toy from any position. It's easy enough to take such an algorithm and then automate the process, but that kind of solution is limited in scope and utility. What computer scientists have struggled with is how to enable a machine to solve a problem like the Rubik's Cube on its own, and the UCI researchers found their answer in a technique called autodidactic iteration.
Let's back up a moment. Deep learning machines that play games like chess and Go typically use a self-teaching method that is based on a rewards system. It is a big part of the process—researchers feed the machine the rules of the game, and then it uses a rewards process to determine if a move was a good one or a bad one, toward the desired outcome of winning the match.
Solving a Rubik's Cube is more challenging. When a machine makes a random move on the six-sided cube, it's difficult to determine if the new position is any closer to a solution, and therefore it's not easy to apply a rewards system similar to other games. On top of that, a machine could spend a long time making moves without solving the cube, making a reward based on actually solving it a rare occurrence.
Stephen McAleer and his colleagues from UC Irvine developed the autodidactic iteration to get around that limitation. How it works in this case is it works backwards from a solved Rubik's Cube to find a configuration of squares that is similar to the machine's proposed move. Using this method, a machine can reasonably determine if one type of move is better than the other.
It's not a perfect solution to the problem, but is flawless in terms of accuracy. "Our algorithm is able to solve 100 percent of randomly scrambled cubes while achieving a median solve length of 30 moves—less than or equal to solvers that employ human domain knowledge," McAleer and his team said.
This is a big deal because it has implications that extend beyond solving a 1980s toy. McAleer and his team say they want to build upon the autodidactic iteration technique to "find approximate solutions to other combinatorial optimization problems such as prediction of protein tertiary structure." Ideally, it could lead to finding cures for diseases, if the method is able to work as well on such things as it does with solving a Rubik's Cube.
Top Image Source: Pixabay via Pexels
