Solving the rubik's cube with a genetic algorithm
Some words about the beast
Lots of comments, many thanks to all of you ! It seems that many of us have such a secret dream to become a new
Kociemba :) I had a lot of fun when I noticed that within a few hours your comments were really coming from all parts
of the world (France, USA, No-way, Santa Cruz, …)
I don’t have much time and as told you these are only preliminary results, but here are the facts. The names after
the titles are related to some of your recent posts and questions on that topic.
1) Blocks, facelets, pairs … (Michiel, Gilles)
2) The solving method I implemented (Per, Charles)
3) Fitness functions (Lars, Gilles, Per)
4) Other GA parameters (GA = genetic alg) (Per, Gilles)
1) I first tried the most obvious way : defining a cube as 54 facelets, optimizing the number of facelets matching a solved cube. He he he would say Per ! It is actually possible to converge to about 40 corrects “stickers”, but then impossible to solve the cube quickly, since all incorrect pieces are disseminated on all faces. So I decided to define kind of a “cube entropy”, using that definition : entropy = -(sum[CEp] + sum[ECep]) , where a CEp is a corner-edge pair (WHICH IS REALLY CORRECT, as opposite to Michiel’s more permissive definition, see his post), and ECep is an Edge-center pair. Entropy of a solve cube is –48, entropy of a random cube is … I actually never looked at, but probably around –3 to –6 (?) So in terms of pairs a 2x2x3 is built with 16 “pairs”.
2) Actually I used a block method. I wrote I implemented Charle’s and Sebastian’s way, perhaps I should have been more explicit : I look for a “good” 2x2x3, THEN jump into the 2-gen group THEN try to solve the cube in the 2-gen group. I will think about the other methods you mention after the 2x2x3, but I really want to keep my GA “memory-free”, without using any LL alg or built-in insertion technique. At the moment is really using only Darwin’s laws, and Darwin did not know a single Rubik’s cube alg ;-)
3) THIS IS THE POINT !
What do we all want to do when participating to FMC ? Eventually solve the cube … and minimize the number of moves.
My fitness functions are no less than a mathematical expression of this fact : when evaluating a 30-moves individual
of the population (say for the 2x2x3 stage) I use that procedure :
Nmax = 0, Jmax = 0
For j = 1, 30
Do move j
N = -entropy of the 2x2x3 location (between 0 and 16)
If N>Nmax then Nmax = N and Jmax = j
End for
Fitness = 10Nmax-Jmax
That is, at a given stage of the optimization process, I will allow longer solutions to be well rated, if they build
more pairs than other shorter solutions. The factor 10 is purely empirical :)
For getting into the 2-gen group I decided not to teach the alg any moves sequence. Starting with the 2x2x3 already
built, I simply tell my GA that he can break it … only for a short time : the procedure is exactly the same, except
that N = is2gen + 100is2x2x3, where is2gen is a Boolean variable telling if the edges are correctly oriented AND the
corners correctly positioned to be solvable in the 2-gen group (thanks to Sebastian for the elegant way to define it),
and is2x2x3 is another Boolean variable to tell if the 2x2x3 is still alive. This fitness function makes sure the alg
will not come up with a broken 2x2x3 at the end of the stage, which could be problematic for the edges/corners checks.
Then the 2-gen part is solved using N = -entropy, which still has the bad habit to converge in too many situations to a
value of 42 instead of 48… 2 twisted corners :(
4) Just to be short, I use : elitist GA (best individual of a generation is kept) / pop_size = 51 / mutation
prob = 0.05 / crossover prob = 0.8 / parents selection by rank (best parents are more likely to have children … do not
try to compare with real life …) / each individual is a string of 30 integers
A crossover is a gene exchange with crossover point at random location, a mutation is the replacement of a gene by
another random one.
I played with the idea of “diseases” in the population, and I kill the 5 weakest individuals at each generation and
replace them with random individuals. I’m probably not the first to have that idea …
OK, that’s all folks ! I will make a webpage on my site with all your suggestions and the state of advancement of
this solver, and post my FORTRAN codes once they are more presentable (at the present time it is just a bunch of codes
lines with tons of unnecessary comments !)
