genetic algorithm for 3x3 rubik's cube

[Invité]

Hi!

I would like to implement a genetic algorithm for solving the rubik's cube and therefore would like to test a bit with the code you have written.

Is it possible to send me your source code / source files?

I will of course let you know about my progress.

Please send to matadormix[le fameux a cerclé]gmx.de

thank you!

[cyril]

Hi,
My code is written in fortran with a bunch of comments in French. Hope you can make something out of it ...
I do not have the sources with me right now, but I will dive into my old computer and eventually find them and send them to you...
Thanks for your interest

[Invité]

Hi!

Thanks very much!

Je peux aussi parler un peu le francais.

So reading your comments should work

When do you think is it possible to dive into your old computer? You are on a trip to Asia or something, right?

best regards

[newbeer]

Sorry I wasn't logged in. To be exact I mean trip to Nepal according to your signature.

Greetz

[cyril]

Hi again,
I just added the source code to the download page. Good luck !

PS : I am back from the Nepal trip

[Invité]

Hi!

I am progressing with the genetic solver.

I have written you an email to your caramail adress with some questions


Best Regards!

[deadalnix]

I think you should ask your questions here. This way, everybody will be able to read the answer

[cyril]

Hi cyrilca!

It's been a while since our last contact. Some weeks ago, I asked for the genetic algorithm source code. I downloaded it from your page and I analized it. It was quite hard, because my French is not the best, and I did not know fortran, but now I think I really understood it

I think the way to go through the two-generator subgroup is really the only way to solve the cube using a genetic algorithm, because without this step in between no fitness function will work since there is no other fitness to look at than the stickers of the same color on the same side.

Do you have any idea how I could extend or improve the genetic solver?

I was thinking about dividing the solution steps into smaller parts and optimizing the parts using a genetic algorithm knowing the maximum length. For example a solution of 30 steps could be devided into 3 * 10 steps. For each of the parts you know a better solution must be smaller than 10 steps.
But again using the same algorithm would probably be longer because of the two-generator step in between. And only searching for stickers of the same color on the same side probably doesn't solve because it destroys good stickers at about 40 stickers you wrote on your website.

So do you have ideas for improvement or extension?

Besides the question of improvement or extension I would like to reimplement your code in JAVA. Do you think this is possible using the given source code? Because I still have not found out what things like "use dflib" or "use dfport" mean. Maybe these are essential libraries so that it cannot be reimplemented in JAVA?

Best greetings!

Frank

Hi Frank,
I do not read my caramail address anymore, you were right posting something here... As requested by Deadalnix, I think it is a good advertisement for my/your solvers to answer your questions here...

First of all, well done for diving into the code and understanding it ! Fortran is quite straightforward, but that is a pretty lengthy code. I do not agree with your statement when you say the 2-gen part is the only way to solve the cube with a genetic algorithm. See for example Per's comments on the genetic alg page. Other ideas for improving the solver would be to explore other steps, for instance solving everything but 3 corners in the 2-gen part (what Per calls a skeleton, then inserting a 3-cycle solving those corners (you may even create a table of a few corner 3-cycles for each cube orientation and use brute force to solve the last 3 corners by inserting the 3-cycles between each move of the skeleton solution).

I do not get your idea with the 3*10 steps. I implemented solution stages I could "easily" describe with fitness functions : 2x2x3, 2-gen subgroup, solved. The first two are pretty close to optimal I think, but there is room for improvement in the 2-gen. You may want to work on this part first...

Finally, dflib and dfport are two standard libraries included in the "Hello World" project that served as a basis to build my code. I think I do not use any complicated function from these libraries in my program, so there should not be any problem in JAVA.

Good luck !

[Invité]

Hi Cyril,

Ok, I will post my progress here in this thread.

One question that came to my mind:
Does it make sense to test different kinds of recombination methods?
There are a lot in theory, from single point crossover to multipoint crossover, roulette wheel selection and so on...
From what I see from the code, there ist just a random point crossover. The second half of the gene string, that is added to the first half of another gene string is in my point of view as senseful as a random sequence of moves. This is because the added second half depends in performance on what was its former first half.
So for example there are genestrings 1 and 2. from 1 you pick the first half of the moves sequence and from 2 the second half and you combine it to a new string. then the added second half does not make more sense than a random sequence because its performance depends on its former first half. the first half of gene 2.
So I think it is just the same as adding a random sequence of moves to a good string 1 and so the whole recombination thing does not have a higher probability in creating better solutions than combining a good string with a random string. Or am I wrong? Hope you get my point.


Greetings,

Frank

[cyril]

You are perfectly right.
The only smart thing in my crossover operator is that I cut the sequence "at the best place", as you probably found out when you looked at the code (compute the fitness function after each move as long as the sequence is doing something useful, then cut before it adds more randomness than we want).
Wait, apparently it seems that I abandoned this idea and just chose to randomly cut the sequence. You may want to change that back to cross = perfo(p1, 2) (remove the commenting !)

!Choix du gène de cross-over appartient à {1, ..., long_code-1}
!ALEATOIRE
call random(x0)
cross = (size(pop,2)-1) * 0.9999* x0 + 1 !pour le cas foireux ou x0 ==1 pile
!OU : APRES LE 1ER MAX DE FOBJ pour le premier parent
!cross = perfo(p1, 2)

What I fill the rest of the gene with after that is just as good (or as bad) as random moves, as you say. It works quite well for the 2-gen group though, and not too bad for the small optimal sequences for the first two substeps.

The problem with the rubik's cube is that it is much more challenging as the travelling salesman concerning mutations and crossover operators : switching two moves results in a mess on a rubik's cube ! Working on these operators is definitely an area where you could improve my code a lot. I do not think multipoint crossover would be the solution, I already use kind of roulette selction (rank-weighted selection in my case).
A best crossover operator might be to randomly add stuff like RUR'U' or commutators in the sequences instead of mixing two genes: they would introduce fewer randomness than the butchery in my code.

Well... these were my thought about that !
You will find very interesting information in a quite theoritical paper by Whitley, and a more practical one by Eiben et al. They are way above our needs, but they gave me lots of tricks and ideas.
Good luck !

[newbeer]

Bonjour,

is there any test, whether the genetic algorithm always gives a correct solution?
Or did you somewhen got a wrong result? If not the algorithm should be correctly working.

I tried it out with some small and some big scrambles.
Sometimes the solution was right, sometimes it was wrong, but maybe it was my fault to not correctly turn the cube in the "turn the whole cube phase".

Sometimes I had to not regard the second line of the solution in the *.txt file and then it was the correct answer. a bit confusing

[newbeer]

Hi cyril!

I am really good progressing with the solver. Theres only one thing left.

I don't get how your solver tries to find out, whether the corners are correctly positioned to be in the 2gen group.
To be exact, I dont get these lines of your code:

!print*, "corners positions", corners_pos

!on doit passer en scalaire pour le select case
co = 100000*corners_pos(1)+10000*corners_pos(2)+1000*corners_pos(3)+100*corners_pos(4)+10*corners_pos(5)+corners_pos(6)
select case(co)
case(12201,1221,11022,12120,10212,102210,110220,100122,102021,101202,210021,221001,211200,210102,212010,21102,2112,22011,21210,20121,120012,112002,122100,120201,121020,201120,220110,200211,201012,202101)
is2gen = 1
case default
return
end select

Before this, you create some kind of codeword (the ones containing the 0,1 and 2s) (are you sure, that with the 2^x+... notation for example:
corner_temp(1) = 2**cube(6)+ 2**cube(36)+2**cube(53) is always a different number than for example the next line: corner_temp(2) = 2**cube(8)+2**cube(38)+2**cube(24) )
and you then test this codeword using the code posted above. I know this has to do with the proof from Sebastian Dumitrescu on his website. But I dont get how you come to these 30 code combinations from the proof. And you do this twice. First "!checks the position of the corners: 1st test (link 5-1, 6-2, 3-4 and observe the pattern)" and second: " !2nd test (link 5-2, 6-4, 3-1 and observe the pattern)". Shouldn't be there 5 tests, because Sebastian uses 5 pictures with different states of the corners positions ( http://www.geocities.com/portoseb/cube/ ... ation.html ) ?

Best regards and happy christmas, Frank!

[cyril]

Tiens, vu que c'est la rentrée des classes : voici le résultat sous forme d'un article. Attention, c'est pas exactement du Sciences & Vie Junior
C'est très joli, très inspiré par mes idées au niveau de la structure du programme, mais immensément plus propre et joli (je l'ai déjà dit ?).
Frank (devenu apparemment Markus ou Christian d'après le papier...) m'a envoyé une version sous forme de .jar que l'on peut exécuter en local. Les intéressés peuvent le contacter via l'adresse donnée dans premier post, probablement avec plus de succès par email que par MP.

Je prévois un intérêt marginal pour mon post, mais je miserais mes économies sur Deadal et WydD

PS : Il s'agit d'une bonne lecture pour comprendre la différence entre un algorithme et un algorithme...

[WydD]

Oh le joli techreport Merci pour le lien cyril je l'ajoute à ma bibliothèque.
Pour info, dans ses slides ya une photo de doudou (ainsi que la grenouille qui cube de BenJ).

[ottoitti]

hi mr Cyril
there are some things I still do not understand.
some of them are fobj, solve_twogen_bourrin, and perfo. what are they? what can I do with them? what their position ?
and the two-gen things that testing the cube by linking the 1-5, 3-4, 6-2 corners + the second test linking the 5-2, 6-4, 3-1 corners. why there must be some tests? is it not enough just to check its course from the edges? why there should be a second test?


This time it's all I want to ask
sorry if it should make you recall the past