Solving the rubik's cube with a genetic algorithm
ASolving the rubik's cube using genetic programming : reactions after the second post
from : Michiel van der Blonk :
--- "Cyril Castella" <cyrilca@c...> shouts:
> 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
I don't think either one of us is 'more correct' on the topic. I chose the word pair because that is what it is: a pair
of facelets. It's not a pair in the way we form F2L using 'pairs' which are always pairs of an aligned edge and corner.
In fact in my program, such a pair can be described just as easily as a collection of 'simple pairs'.
> the moment is really using only Darwin's laws, and Darwin did not know a single Rubik's cube alg ;-)
But I think if he did he'd be a darned good speedcuber.
> Elitist GA
I usually use this one too.
> each individual is a string of 30 integers representing a solution
how?
> A crossover is a gene exchange with crossover point at random location, a mutation is the replacement of a gene by
another random one.
How is a gene defined?
> 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 …
It's new to me. I usually use mutation only.
> and post my FORTRAN codes once they are more presentable
FORTRAN! That's a golden oldy. I might still have my GA library in Pascal somewhere. My most fun GA used to be one that
wrote a program for getting out of a maze. But the cube is more fascinating.
BTW: how many times does it find a solution, and in how many generations? Does it need a lot of processing power?
I'm looking forward to seeing it.
Michiel
My answer to Michiel's questions :
Hi michiel,
just some more comments :
Of course I did not meant that "my" definition of a pair was more clever than "yours", I just wanted to point out that
in my case a Corner-Edge pair is a "F2L corner-edge pair". I really think it is more efficient for converging to the
solved 2x2x3 or whole cube.
A gene is an integer representing a move : 0-5 = FURBDL, 6-11 = F2... L2, 12-17 = F'...L'. An individual is therefore
a sequence of 30 moves. But the fitness function is not necessarly defined for the whole sequence, but at the best point
(see the definition of Jmax in the pseudo-code I gave in my last post). That really makes a difference, IMH... I use a
"trim function" to remove cancelling moves and add random moves at the end of a trimmed individual after crossover or
mutation processes.
To obtain the whole solution, I used about 3 hours computing time. About 12 x 10'000 generations (12 x 3 minutes) for
finding a good 2x2x3, then about a minute to find a good way to get into 2-gen group, then ~2 hours to solve the 2-gen
group. I only tested a few scrambles, but it seems to be reliable (it found a nice 23 moves solution for #58 2-gen FMC)
Cheers !
Cyril
from : Sebastian Dumitrescu :
Cyril Castella wrote :
> 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)
Hi Cyril and others!
I'm very glad that I could contribute with something for this, but I still don't understand the main idea of genetic
algorithms. I won't try to understand the FORTRAN code or any other code, I just want somebody to explain the extra-basic
idea of the GA. Can it be mathematically represented as a function or as a composition of functions? How can it be
associated with the cube moves?
I know that this has been explained, but I would really like to understand this better.
Thanks,
Sebastian
from : Lars Petrus :
I don't know much about genetic programming, and I probably did that part mediocrily at best, but I have a bit more
ambitious fitness function than what I've heard mentioned so far. By fitness function I mean something that measures how
close a position is to the solved state.
First consider the "Connectivity Number", which I'll define as the number of formed pairs. There are 24 such
corner/edge pairs and 24 center/edge pairs. One move can only change either number by 4 or less. You can use this for
"backtracking" problems (when you want to trace back n moves) since you know that when there are x moves left, each
Connectivity Number has to be at least 24 - (4 * x).
The advanced part is to take into account that unformed pairs can be more or less close to being formed. A corner/edge
pair can be up to 3 moves from being joined, while a center/edge pair is at most 2 moves away. So for each corner/edge
pair you have a number from 0 to 3, and for each center/edge pair a number from 0-2. In total that gives a corner number
from 0 to 72 and a center number from 0 to 48.
Having watched the program trying to solve using this metric it's not hard to get more ideas on how to refine it.
Lars
Comments on Lars' idea by Gilles Roux :
--- Lars Petrus <lars@l...> wrote:
> The advanced part is to take into account that unformed pairs can be more or less close to being formed. A
corner/edge pair can be up to 3 moves from being joined, while a center/edge pair is at most 2 moves away. So for
each corner/edge pair you have a number from 0 to 3, and for each center/edge pair a number from 0-2. In total that
gives a corner number from 0 to 72 and a center number from 0 to 48.
It's a bit more ambitious, but does it give interesting results? On very easy cases, almost solved, an objective
function based on these criteria looks nice, more powerful. But I think it's still inefficient, because the problem
comes from other global constraints. You can make a pair in 2 moves and another one in 3 moves, but 7 moves are required
if you want both.
When I was young, I was dreaming of such fitness functions. The more I cube, the more I realize how naïve I was. Now
I'm very skeptical :-)
Gilles
from : Stefan Pochmann :
I think the major problem is not the number of states, but that it's hard to find a valid solution at all and mutate
it to another solution.
A traveling salesman instance with let's say 100 cities has far more states but all of them are solutions (well,
unless of course you add restrictions), they just differ in their length. Mutation can be done by simple things like
swapping two cities.
Have you seen Tom's cube contest? The three top solutions used Thistlethwaite, fourth place used large searches, but
fifth place (David Barr's solution) uses a human-like solution and averaged 35.03 moves (though only half of the scrambles
were really random, the others were scrambled with up to three moves only, but then again if the program uses a fixed
order it might still take many moves even for such a scramble... don't know, haven't checked).
http://tomas.rokicki.com/cubecontest/winners.php
Cheers!
Stefan Pochmann
