Machine Figures Out Rubik's Cube Without Human Assistance (technologyreview.com)

An anonymous reader quotes a report from MIT Technology Review: [Stephen McAleer and colleagues from the University of California, Irvine] 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. Here's how it works. Given an unsolved cube, the machine must decide whether a specific move is an improvement on the existing configuration. To do this, it must be able to evaluate the move. Autodidactic iteration does this by starting with the finished cube and working backwards to find a configuration that is similar to the proposed move. This process is not perfect, but deep learning helps the system figure out which moves are generally better than others. Having been trained, the network then uses a standard search tree to hunt for suggested moves for each configuration.

The result is an algorithm that performs remarkably well. "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," say McAleer and co. That's interesting because it has implications for a variety of other tasks that deep learning has struggled with, including puzzles like Sokoban, games like Montezuma's Revenge, and problems like prime number factorization. The paper on the algorithm -- called DeepCube -- is available on Arxiv.

Comments

With one exception; the goal state

[Anonymous Coward]

Someone had to tell it what is a solution. If you give it a solved cube, that's assistance. Is it really that hard not to inflate headlines?

Re:With one exception; the goal state

[PPH]

If you give it a solved cube

And you give it a scrambled cube. The AI shouts "Hey look! Haley's comet!" And while you are looking up, it switches them.

Turing test: Passed.

Re:Wow amazing!

[TFlan91]

Games are easy for "AI" because games have strict rules that a modeler can account for/predict.

Odd definition of "without human help"

[Entrope]

This algorithm was able to figure out how to solve Rubik's Cube with no help from humans other than humans providing the (simulated) cubes, describing what the solution looks like, and designing an algorithm specific to solving Rubik's Cube?

Color me less than impressed.

Re:Odd definition of "without human help"

[gweihir]

Oh, it still is a nice result. But you are describing exactly the core problem with it: Everything was clear and described in simple, clear statements from the start. That is not how a real-world problem presents itself.

Re:Yawn

[infolation]

From TFA:

it has implications for a variety of other tasks that deep learning has struggled with, including... problems like prime number factorization

If it could help with finding the prime factorization of large semi-prime numbers – ie two or more prime numbers that multiplied together result in a target original number - then that would be quite useful.

*cough* cryptography

Re:Yawn

[AHuxley]

Assembling any type of IKEA furniture from the box?

Re:starting with the finished cube

[DontBeAMoran]

The same way rich people "learn" how to become rich.

Actually that's a great idea: knapsack problem

[goombah99]

While Ikea furniture is designed with assembly in mind other things are not. Say for example, an airplane. So the assembly process might not be optimal. Letting the computer look for a more optimal process might be useful.

Or more practically, packing items into a shipping box. the famous knapsack problem.

  I hate these slashdot summaries of algorithms. you end up thinking gosh that's stupid. When it's not. just the description is stupid. like a car analogy

Re:Wow amazing!

[religionofpeas]

Games are easy for "AI" because games have strict rules

Just because the rules are strict (or even simple) does not mean that the game is easy. You can achieve arbitrary complexity by iterating the rules a large number of times. For example, the rules of Go are strict, the question whether a given board position is winning for white is hard. The rules of a programming language are strict. Writing a Linux kernel is hard. The rules of math are strict. Providing a proof for Fermat's last theorem is hard. The rules of physics and soccer are strict. Making a robot that can beat a human at the game is hard.

Something's not adding up

[Dynedain]

Either the article writer didn't understand the whitepaper, or the researchers haven't actually done anything novel.

Having been trained, the network then uses a standard search tree to hunt for suggested moves for each configuration.

This works because the beginning state and end state of a Rubik's Cube are effectively identical. It's the same number of tiles, in a specific arrangement. As humans, we've defined the "solved" state to be all the tiles color-matched to a side. But the "solved" state could just as arbitrarily be any pattern or arrangement of colors across the cube.

Reversing the simulation to work backwards from the "solved" to some specific state of scrambled is exactly the same problem as starting from some specific state of scrambled and trying to get to the solved.