A deep-learning technique that can learn a so-called “fitness function” from a set of sample solutions to a problem has been devised. This technique was initially trained to solve the Rubik’s cube, the popular 3-D combination puzzle invented by Hungarian sculptor Ernő Rubik.
The aim was to use machine learning to learn to solve the Rubik’s cube. Rubik’s cube is a very complex puzzle, but any of the vast numbers of combinations is at most 20 steps from a solution. So the approach here is to try and solve the problem by learning to do each of those steps individually.
The technique 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. This structure means that each step of the solution is much easier. So, firstly a method was devised that can estimate how jumbled up the cube is by simulating jumbling up the cube many thousands of times.
After it estimates how jumbled up a Rubik’s cube is, a deep neural network recognizes 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.
Evaluation of the technique 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. This 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, this stepwise learning technique has only being used 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.