A deep learning technique to solve Rubik's cube and other problems step-by-step

[aum]

A diagram showing how the data that a computer learns from is collected. The program starts from an unscrambled cube, labels that "0", then scrambles it once, labels that "1", and so on. Then the program learns to attach these kinds of labels to cubes that it hasn't seen during the training process. Credit: Colin G. Johnson.

 

Colin G. Johnson, an associate professor at the University of Nottingham, recently developed a deep-learning technique that can learn a so-called "fitness function" from a set of sample solutions to a problem. This technique, presented in a paper published in Wiley's Expert Systems journal, was initially trained to solve the Rubik's cube, the popular 3-D combination puzzle invented by Hungarian sculptor Ernő Rubik.

 

"The aim of our paper was to use machine learning to learn to solve the Rubik's cube," Colin G. Johnson, one of the researchers who carried out the study, told TechXplore. "Rubik's cube is a very complex puzzle, but any of the vast number of combinations is at most 20 steps from a solution. So the approach we take here is to try and solve the problem by learning to do each of those steps individually."

 

The technique devised by Johnson is based on two main approaches: stepwise learning and the use of a deep neural network. When applied to Rubik's cube, the technique tries to unscramble it step by step instead of learning to solve the whole cube at once. In other words, it tries to shift its parts to achieve a simpler configuration, repeating this step several times, until the cube is solved.

 

"Rather than the program trying to learn how to solve the whole cube, it learns how to get it into a simpler configuration, then takes that simpler configuration, and so on until it is solved," Johnson explained. "This structure means that each step of the solution is much easier. So, I first devised a method that can estimate how jumbled up the cube is by simulating jumbling up the cube many thousands of times."

 

Aiagram showing how the deep learning technique developed by the researchers solves Rubik’s cube. It start with lots of copies of the scrambled cube, then finds some simplified versions of those, then some simplified versions of those, and so on until it finds a solution. Then, it works back through these to find the solution pathway. Credit: Colin G. Johnson.

 

After it estimates how jumbled up a Rubik's cube is, the technique created by Johnson uses a deep neural network to recognize a cube that is one step away from being solved, then two steps away from being solved, three, and so on. Finally, it uses the data it has accumulated to solve the cube.

 

Johnson evaluated the technique he developed in a series of experiments, comparing it with a previously developed approach based on a class of algorithms called random forest classifiers, with a baseline approach based on traditional error-based fitness and with other existing computational techniques. His deep learning technique compared favorably with all these alternative methods, while also highlighting the advantages of tackling tasks in a step-by-step way.

 

So far, Johnson has only used this stepwise learning technique to solve Rubik's cube, but it could also be applied to a variety of more complex problems that can be solved step-by-step. In other words, Rubik's cube is merely a simple example of the type of problems that the technique could tackle.

 

"Think about a problem such as removing the noise from an old audio recording like a wax cylinder or early phonograph record," Johnson said. "We need to remove different kinds of distortion—echo, static, variable speeds—but each recording needs a different strategy. If we can learn the idea of what a 'clean recording," a slightly distorted recording, a 'slightly more distorted recording' is, then we can, I hope, solve this kind of problem in this stepwise way."

 

In the future, the stepwise deep learning technique presented in Johnson's recent paper could be used to solve numerous other problems rooted in science and engineering. For example, it could be used to study and better understand the ways in which proteins fold inside biological cells.

 

Source