Scientists have developed a machine that can solve Rubik's Cube without assistance

Cal Jeffrey

Posts: 3,662   +1,129
Staff member
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.

Permalink to story.

 

Uncle Al

Posts: 9,329   +8,525
I thought this had already been done a few years ago, in fact I recall seeing it on one of the TV programs showing the solution is mere seconds .... what did I miss?
 

VitalyT

Posts: 6,405   +7,209
This is nonsense. For deep-learning machines today solving the cube is like 2x2 for humans, and to the previous poster, yes, it was solved like 10 years ago, with the neural networks.

Today's deep-learning machines can on-the-fly crack tasks that are 10^3 times in complexity.

What did those "scientists" smoke for the last 10 years?
 

BSim500

Posts: 922   +2,185
I thought this had already been done a few years ago, in fact I recall seeing it on one of the TV programs showing the solution is mere seconds .... what did I miss?
Yeah they've been out years:-

Not to mention software that did a 1,000 x 1,000 x 1,000 theoretical super cube 8 years ago:-
 

Kytetiger

Posts: 48   +14
"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."
-> we inject in the memory of the pc all the formula's to solve the Rubik's Cube

"Teaching a computer to solve a Rubik’s Cube by itself is significantly more difficult because the deep-reinforcement learning algorithms do not offer the same "reward" opportunities when applied to the cube"
-> We let the pc mess around and learn by itself.
 

Trillionsin

Posts: 1,897   +484
Well I mean... first we have to tell it that it's a puzzle that needs solving. so I mean, like there still some assistance there ? lol