I've been busy lately building a digitalized version of Rubik's Cube in Matlab. Up untill now, I mainly worked on the appearance and interactibility of the program, but ofcourse I want to solve it eventually...or rather let it solve itself. Since I don't know anything about solving Rubik's cube, I thought of writing a genetic algorithm. When I googled this to see if anyone had ever thought of this before (which ofcourse was the case), I came across your blog. Unfortunately you haven't posted anything about this problem after March 2010, so I was wondering if you ever came up with an effective algorithm. Mine is able to come halfway in solving the cube, but after that, almost every sequence of moves destroys the relatively 'fit' state it was in. Are you interested in the algorithms I'm using (evolution, fitness-function)? I would love to hear your thoughts on this subject!
Kindest regards,
Joren
Hello, yeah unfortunately I didn’t bother implementing this. I was going to and at the time it seemed cool but then I was busy with something and forgot about it.
Now that I have a little more sense and have worked on things like this (http://g23.co/visualize.html) it seems that a genetic algorithm might have difficulty solving this for exactly that reason. It gets “close” but really it’s just landed on a local minimum and it may in reality be far from the solution. That’s not to say don’t do this with a genetic algorithm, just know that GA’s are good at finding things close and for things that don’t have easy to see mathematical models (otherwise a gradient descent would be an excellent choice).
One way that may help with the GA is to see if it can solve the case where 2 layers are already solved and it just has to do the last layer. There should be fewer local minima with only a single layer remaining and then it may be able to solve it. If that works you could maybe do something where it’s “more fit” to solve one layer first, then the next, then the last. That seems like it might work. If you have any other questions or thoughts email me at gfunchess @t gmail d0t com (not that bots aren’t going to get my email anyway).
