Solving the rubik's cube with a genetic algorithm
Description of the project
In my academic work, which is related to medical physics, I have met a tough optimization problem and I am trying to solve it using genetic programming. To be short, genetic programming consists in defining a population of n individuals, then evaluate each individual with a fitness function, and use Darwin's rules of selection, mutation and reproduction to evolve to better individuals at each “generation” and hopefully maximize the fitness function.
How could this be related to FMC ? Actually the progs I developed for my work could easily be translated to this problem, and I chose to adapt Charlie's and Sebastian's approach to solve the cube :
[1] Try to solve the 2x2x3 in Back-Down in fewest moves as possible
[2] Try (1) for the 12 possible 2x2x3 rotations
[3] Get into 2-gen group, using edges orientation check and corners position check (see Sebastian's page)
[4] Solve the cube in the (F,U) group
The question was … was it going to work ? I have no definitive answer, as no “serious” validation was made and there are still lots of parameters I can tune in the genetic alg, but I fed it with #82 FMC scramble and here is I got a really cool 35 moves solution (see details here) not bad for a first try in FMC challenge ;-)
So now … why am I telling you all this ? I thought it would be great to use your experience to improve the performance of the algorithms. The question I am trying to answer is : “what is the best mean to compute short, human-understandable solutions ?”
One of the best approaches to find a short solution (probably the best one ?) is Kociemba's alg, but as we all noticed there is no way one could figure out such a solution …
Lars' general method is good but there is a need to know quite a lot o LL algs to be really efficient in terms of metrics
Fridrich is definitely not a good FM method –I don't think any further discussion about this method is needed :)
Gilles' methods seems very interesting, but I doubt I could implement it easily in my program. The drawback of his approach is the STM optimization … but quite bad in HTM. Actually a “standard” solution (with “normal” opposite 1x2x3 blocks) should not be too hard to program …
“solving all but some edges/corners” should be possible to implement, I will think about that. The point is to define an efficient fitness function for that task. And the alg insertion promise tough problems to solve...
pseudo-moves are quite easy to figure out for a human solver, but apart from trying all 18 possible moves before the scramble (or 18*15 or 18*15*15 or …) I don't see any efficient way to implement it in a genetic alg.
What about other ideas ?
I think I will describe this project more precisely in a few weeks (fitness functions used, performance, …), when the beta version is more ready, and of course let you test the code on random scrambles if you're interested ! The aim of this post is to have some feedback about other FMC techniques I could have missed, I strongly encourage you to reply :) At the beginning (and even now, but with a little less hope …) I thought genetic algs could offer an elegant alternative to kociemba's “brute force” optimal solutions, without any table or known alg, but the whole cube solve seems to be a really tough problem for GA. Let the future answer this question !
Next page : comments and reactions
