Why it matters: Solving a puzzle box is not the only problem autodidactic iteration can solve. The deep-learning algorithms used in Deep Cube can be applied in other fields that require complex computational analysis such as protein folding or cryptography.
In a paper titled "Solving the Rubik's Cube Without Human Knowledge," computer scientist Stephen McAleer and his team of artificial intelligence researchers discuss a technique called "Autodidactic Iteration" that allows a deep-learning computer to teach itself how to solve a Rubik's Cube from any scrambled state.
We have already seen how deep-learning computers can teach themselves and excel at games like Chess, Go, and Shogi. We have also seen machines that can "solve" a Rubik's Cube in the blink of an eye. However, these devices rely on human-created solutions to get to the solved state.
Teaching a computer to solve a Rubik's Cube by itself is significantly more difficult because the deep-reinforcement learning algorithms, such as those used in Deep Blue and AlphaGo, do not offer the same "reward" opportunities when applied to the cube.
According to the researchers, with games like Chess and Go, the evaluation of a move is much more straightforward than it is with the multi-colored puzzle box. Any given move in chess, for example, can be analyzed and determined whether it is closer to a favorable outcome (a win) or further away from the goal. A move with a Rubik's Cube is much more difficult to evaluate in such a manner. This difficulty in evaluation, and therefore reward, is why all the machines that have solved the cube up until now have relied on human-created algorithms.
McAleer explains that with autodidactic iteration the AI, dubbed "DeepCube," can learn to solve a Rubik's Cube 100 percent of the time without human interaction. Solution times average about 30 moves, which is equal to or better than many machines that use human-created solutions.
"Our algorithm is able to solve 100% of randomly scrambled cubes while achieving a median solve length of 30 moves---less than or equal to solvers that employ human domain knowledge," says McAleer.
Training an AI to teach itself how to solve a Rubik's Cube is not all fun and games. The researchers have very practical applications that the technique can be applied to besides a puzzle. For instance, the autodidactic iteration technique used in DeepCube can be applied to working on problems like protein folding.
"We are working on extending this method to find approximate solutions to other combinatorial optimization problems such as prediction of protein tertiary structure," the paper points out.
If you are interested in reading the full paper, it is available on the Cornell University Library website.