A machine has figured out Rubik’s Cube all by itself | Intelligent Machines - MIT Technology Review

Unlike chess moves, changes to a Rubik’s Cube are hard to evaluate, which is why deep-learning machines haven’t been able to solve the puzzle on their own. Until now, as MIT Technology Review reports.

Photo: MIT Technology Review

by Emerging Technology from the arXiv June 15, 2018 

Yet another bastion of human skill and intelligence has fallen to the onslaught of the machines. A new kind of deep-learning machine has taught itself to solve a Rubik’s Cube without any human assistance.

The milestone is significant because the new approach tackles an important problem in computer science—how to solve complex problems when help is minimal.

First some background. The Rubik’s Cube is a three-dimensional puzzle developed in 1974 by the Hungarian inventor Erno Rubik, the object being to align all squares of the same color on the same face of the cube. It became an international best-selling toy and sold over 350 million units.

The puzzle has also attracted considerable interest from computer scientists and mathematicians. One question that has intrigued them is the smallest number of moves needed to solve it from any position. The answer, proved in 2014, turns out to be 26. 

Another common challenge is to design algorithms that can solve the cube from any position. Rubik himself, within a month of inventing the toy, came up with an algorithm that could do this.

But attempts to automated the process have all relied on algorithms that have been hand-crafted by humans.

More recently, computer scientists have tried to find ways for machines to solve the problem themselves. One idea is to use the same kind of approach that has been so successful with games like chess and Go.

In these scenarios, a deep-learning machine is given the rules of the game and then plays against itself. Crucially, it is rewarded at each step according to how it performs. This reward process is hugely important because it helps the machine to distinguish good play from bad play. In other words, it helps the machine learn...

Enter Stephen McAleer and colleagues from the University of California, Irvine. These guys have pioneered a new kind of deep-learning technique, called “autodidactic iteration,” that can teach itself to solve a Rubik’s Cube with no human assistance. The trick that McAleer and co have mastered is to find a way for the machine to create its own system of rewards.
Read more... 

Additional resources  
Ref: arxiv.org/abs/1805.07470 : Solving the Rubik's Cube Without Human Knowledge
 
Source: MIT Technology Review