A Machine Has Figured Out Rubik’s Cube All by Itself

Megalith

24-bit/48kHz
Staff member
Joined
Aug 20, 2006
Messages
13,000
They seem to be getting smarter every day: one deep-learning machine has managed to teach itself to solve a Rubik’s Cube, proving that humans aren’t the only ones capable of tackling complex problems. Stephen McAleer and colleagues from the University of California, Irvine made it possible with a new kind of deep-learning technique called “autodidactic iteration.”

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.
 
Rubiks cube today, efficient killing machines tomorrow. Robots are going to kill us all..........
 
Last edited:
Great, robots are suppose to exist so I can play more games, not the other way around.
 
Great, robots are suppose to exist so I can play more games, not the other way around.
I mean watching other people play videos games is a big thing these days, not that I understand it but maybe the robots are onto something. ;)
 
IMHO this is a lot less impressive than it seems. The deep learning algorithm will just memorize the possible configurations without really learning much.
 
Yeah? Peel off two of three stickers on a corner and swap them. Let's see it autodidact it's effing iteration out of that!

(Yes, this is standard mod to any relative's rubik cube...without their knowledge...)
 
IMHO this is a lot less impressive than it seems. The deep learning algorithm will just memorize the possible configurations without really learning much.

That isn't how deep learning works.

In either case this is far less of a challenge/far less exciting than AlphaGo.
 
Autodidactic iteration does this by starting with the finished cube and working backwards to find a configuration that is similar to the proposed move


so your just throwing a shit ton of processor cycles at a problem, brute force solving. doesnt sound all that impressive.
 
so your just throwing a shit ton of processor cycles at a problem, brute force solving. doesnt sound all that impressive.
Brute forcing in this problem would typically mean trying every possible combination without discrimination until the solution is reached. This is not what this sounds like.
 
There is an important bit of information missing here.

Did it actually figure out the cube, or did it just figure out how to solve it after being shown the end goal?

The first would be impressive, the latter, not that much. The first could actually be called intelligence, the latter is just a blind tool that solves a mathematical problem trough iteration.
 
There is an important bit of information missing here.

Did it actually figure out the cube, or did it just figure out how to solve it after being shown the end goal?

The first would be impressive, the latter, not that much. The first could actually be called intelligence, the latter is just a blind tool that solves a mathematical problem trough iteration.
What do you mean by "figure out the cube" and "figure out how to solve it"?
 
Brute forcing in this problem would typically mean trying every possible combination without discrimination until the solution is reached. This is not what this sounds like.


but thats EXACTLY what they are doing.. simply in reverse. They are starting with a completed cube, then working in reverse trying all combinations until one matches what it sees as its current state, then uses that set of paths to "complete" the cube.
 
but thats EXACTLY what they are doing.. simply in reverse. They are starting with a completed cube, then working in reverse trying all combinations until one matches what it sees as its current state, then uses that set of paths to "complete" the cube.
In brute force for this problem it's irrelevant whether you start solved or start with the mixed up cube. A solved rubik's cube (all sides the same color) is nothing special, it's just a particular combiantion of squares on the cube. It's no more special than any other particular combination of the cube. It's just easier for humans to see the goal, but from a computational point of view which parctiular combination you are trying to reach on the rubik's cube is irrelevant. The total solution space doesn't change, so switching them around doesn't give you anything. I have tried to solve a rubik's cube brute force. By the 7'th or 8th possible rotation things slow down..... A LOT (there are about 15 or so possible rotations you can try at each iteration, 2 faces rotate on 3 separate dimensions, each face can rotate clockwise, counterclockwise, or 180degrees, you can ommit a move which will return you to the last known state). You need to be able to perform 26 moves to solve any rubik's cube.

They are starting from a solved cube and mixing it up to give the AI an idea of what "progress" might look like. The AI can now use this to evaluate any particular set of moves that it does on the mixed cube.

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.

Once you have a good "progress" function, the rest basically is very similar to brute force. Just try combinations that give you better "progress", build onto each previous combination that had the most "progress" until you solve.

edit: My own brutceforce method, btw, may not be the most efficient, as my method actually visits some states multiple times. There are a ttotal of 4.3e19 cube states for a 3x3x3 cube, if you could test each state in a single 1ghz clock cycle that would take you 10^-9*4.3e19= 4.3e10 seconds = 1300 years to test every state. Divide that by half is probably the average amount of time to brute force it.
 
Last edited:
The argument has been made that that in fact is how deep learning works.

https://arxiv.org/abs/1611.03530

That paper is in no way going into whether deep-learning creates all possible solutions then uses that to come up with answers. (which deep-learning does not do)

Put simply: There are more moves in Go than atoms in the universe. It is literally impossible for AlphaGo to know every single move in Go. We - the human race - have not manufactured enough storage and in no way could all the processors in the world combined consider that data in a timely fashion.

What that paper focuses on is the difficulty of creating generalized AI from specialized datasets and a way to measure the difference. They do mention that the power of some AI approaches could allow them to completely memorize the dataset but it is not explicitly proven that they do.


https://arxiv.org/pdf/1611.03530.pdf said:
In this work we presented a simple experimental framework for defining and understanding a notion of effective capacity of machine learning models. The experiments we conducted emphasize that the effective capacity of several successful neural network architectures is large enough to shatter the training data. Consequently, these models are in principle rich enough to memorize the training data. This situation poses a conceptual challenge to statistical learning theory as traditional measures of model complexity struggle to explain the generalization ability of large artificial neural networks. We argue that we have yet to discover a precise formal measure under which these enormous models are simple. Another insight resulting from our experiments is that optimization continues to be empirically easy even if the resulting model does not generalize. This shows that the reasons for why optimization is empirically easy must be different from the true cause of generalization.
 
Last edited:
You guys don't get it!

It's sitting there thinking, "this is your skull,....this is what I am going to do to your skull" while it is manipulating the cube!!!!! It's a freaking Siberian Tiger playing with his food!!!!!! WAKE UP, OR THEY WILL KILL US ALL!!
 
Back
Top