Solving the rubik's cube with a genetic algorithm
Solving the rubik's cube using genetic programming : reactions after the first post
from : Per Kristen Fredlund :
Hi Cyril!
Interesting post. I know a little about gentic algorithms. Could u describe more how ur approach works. How do u
evaluate good and bad "species"? More specifically how do u define fitness functions? And how do u perform crossover
and mutation? Do u at all have some built-in "cube-knowledge" in ur code?
U also mention some approaches solving cube effciently and "human-like". Can't see that u have listed the popular
approach to FMC, namely blockstyle. For blockstyle beginning u have many alternative
paths to take. After say 2x2x2 and 2x2x3 u can either:
- do f2l, then rest by OLL + PLL (or replace OLL and PLL with an alg that leaves either corner or edge 3-cycle to
be inserted ... here my planned but not realised alg-insertion program could be handy)
- orient edges and fix corners so that u end up with 2-G finish ... u have already looked at 2-G using GA so this
is maybe a very interesting path for u
- do all edges and finish off with a bunch of corner cycle insertions
- do all corners and finish with some edge-cycle insertions
- do ZBf2l for easier LL
- do f2l minus 1 c/e pair, orient all corners, then rest
Just to mention a few of the most common ones :-)
Cheers!
-Per
from : Michiel van der Blonk :
Hi
Fantastic. I have also been working on a genetic solver for a while now, in a deep secret underground factory,
preparing for world domination. And I have come up with a different technique. I am connecting pairs of cubies and
just optimize that. This is just a first step, and it appears to be a pretty devious problem to tackle.
I hoped to just magically see a solved cube, but... not yet. My program is written in VBA. I will convert it to VB and
then later maybe VB.NET (or even C or Java) for speed.
A solved cube has 72 connected pairs. The program jumps pretty quick from a start of 9 pairs to say 20-30 pairs. That's
when it starts to slow down. 40-50 pairs is usually a solution with only 3 or 4 cubies incorrectly placed or oriented.
My first solver was a python program, but that one was for the 2x2 and didn't use the right search path , so it led to
nothing.
I am willing to share my code and work with others on a better solver, so when I have mine prepared I will post it to
the group. If you like a copy, please email me. It's a self-explaining Excel file with a cube view and a scramble and
solve button.
I really think this kind of program could have a huge potential in looking for a good solution, and maybe even more
human-readable than the brute force programs.
bye
Michiel
from : Lars Petrus :
I spent a weekend a few months back working on something similar. I came up with 3-4 more or less advanced metrics
and tried to weigh them. It got pretty far, but never actually solved the cube.
I'll never finish it, so I'd be happy to work with others as well.
/Lars
from : Charles Tsai :
Oh jeez, all coming out of the woodwork now :)
Cyril, a while ago I was thinking of writing a solver by ending with 2-gen to see what the limits of this method were
but I could never get myself motivated to think and figure it out.. So, good to see you do it! Using this method in the
fmc, i think it's probably around 30, maybe slightly less but not much.. Do one of the 12 2x2x3s, then instead of
immediately getting into 2-gen (which is what I do) do some R,U turns and then flip the edges and fix the corners and then
finish with more R,U turns.
Maybe a program that would use different methods depending on some property of the scramble? You know, if the scramble
had a certain property, use method X, if another property, use method Y. Maybe I should be doing the same thing in FMC,
instead of 2x2x2 then 2x2x3 etc the same way every time. I have no idea what these properties
would be however... ;)
Since we're on the topic of cube programs: I too worked on a cube program in my own ultra-secret underground cave!!!
Back when Per was talking about his alg-inserter, I mentioned that I wanted to write a solver for the 4x4x4. Well, it only
partially solves it: only edges and corners, but not centers. In under 50 moves usually. I've pretty
much abandoned it, I haven't done anything with it for several months now
Charles
from : Gilles Roux :
Building blocks looks nice at first, but you quickly realize that a nice looking pre-PLL cube is still more than 10 moves away from the solution (travelling through positions with much fewer blocks)...
Optimization functions are really hard to find. No surprise, that's why it's so difficult to solve a cube in 20 moves!!
Cyril, tell us more about your algorithms :-)
Gilles.
