February 26, 2021
feature
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.”
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.
How explainable artificial intelligence can help humans innovate
More information:
Colin G. Johnson. Solving the Rubik’s cube with stepwise deep learning, Expert Systems (2021). DOI: 10.1111/exsy.12665
2021 Science X Network
Citation:
A deep learning technique to solve Rubik’s cube and other problems step-by-step (2021, February 26)
retrieved 27 February 2021
from https://techxplore.com/news/2021-02-deep-technique-rubik-cube-problems.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no
part may be reproduced without the written permission. The content is provided for information purposes only.
