Building a Rubik's Cube with a genetic algorithm online without SMS

While I was getting ready for lunch, my co-worker Dave called out to me: “Hey, Alex, and you don't want to work on improving your programming skills?”. I thought. It was an interesting proposal, but I was inclined to refuse: “Now I am engaged in developing speaking skills in languages, my friend!”. Okay, just kidding. The morning began with the fact that I got to the post office and got into the hands of a penny Chinese Cube, randomly ordered to Ali. By lunchtime, I studied the assembly manual and updated my muscle memory, and by the evening it came to the realization that I had played enough. The future of the cube was clear: it will gather dust on the shelf, once or twice a week, maybe I will collect it to put my thoughts in order or distract myself, but no more. Competition in mechanical assembly speed? Non merci, it's better to do birdhouses ...

The situation, as always, saved the thought of automation. After a brief study, I learned the recognition. To begin with, the number of God has long been found and is equal to 20. True, the assembly task does not simplify because use the shortest path graph for all possible configurations of the cube is not very sporty and a little expensive in terms of resources. The algorithm of God presupposes a certain reasonable amount of used memory, and at the same time is obliged to ensure the minimum possible number of modifications. So, there is no such algorithm yet. There are a number of algorithms that allow a noticeable speed up of the assembly compared to traditional template methods, but it seemed to me boring to repeat the path already laid (mathematically) by someone. If anyone is interested, here is a good analysis. Then there are traditional sample methods. The idea here is a layered assembly from bottom to top using formulas. A formula is a sequence of modifications of the Cube, resulting in such and such targeted modifications, and such and such side effects. Accordingly, side modifications almost always fall on layers that have not yet been assembled. Template methods differ in the level of template detailing. Any kind of speedcoolers knows all conceivable patterns for a large number of special cases, which allows you to play an extra 0.1 seconds from each modification in competitions. An example of what else you can spend your life .
')
So, I gradually formed a task for myself. As a result, it is formulated in the following way: in the shortest real time, it is necessary to write a solver for the Rubik's Cube.

What do we know about the cube? The number of its states is described as

(8! × 3 ^ 7) × (12! × 2 ^ 11) / 2 = 43 252 003 274 489 856 000

.
It is this number that imposes restrictions on the use of the shortest path graph. What do we know about his rules? The fact that each specific element (side or corner) must stand exactly in its place. What is the exact place? For a side element, this is the correspondence of both its colors to the colors of the central elements, for a corner element - the correspondence of the three central elements to the three colors of this corner element.



Thus, at any moment in time, we can simply answer the question: “Is this element worth it in its place?”. The second aspect that we know is that the cube can be assembled in layers, whereby each layer is assembled gradually. And that means ... pa-para-param! Gradient heuristics needed. It remains only to choose the method of implementation. I did not begin to consider algebraic methods, since I wanted to get some kind of solution, easily generalized to a similar class of problems. (What I got is not difficult to summarize up to 11 * 11 * 11, for example) There was also an option: to detail the mask templates and formulas for them, simply by automating any of the articles in Google “Rubik's Cube”. But for obvious reasons, except for anguish, this option brought nothing.

There was a bust. Despite the full possible number of states, iteration seemed to me the simplest solution. It remained to find out the details of the implementation. Intuition told me that some kind of competitive environment of possible options would be needed so that from the presented options it was faster to find the transition to the next level of assembly. In general, the variant of the genetic algorithm began to dominate by itself.

By the execution environment, I decided to choose an ordinary modern browser, since This thing perfectly fulfilled the requirement of speed implementation. I shared an idea with a friend who was busy at that moment grazing geese in Belarus, or something like that. Dima picked up the proposal, we started to look at ways of parallel efforts. I quickly found collabedit.com , which allowed writing JavaScript code to several people at the same time. I threw html on hosting with

<script src = " collabedit.com/download?id=svxve "> </ script>
<script src = " collabedit.com/download?id=s8xkv "> </ script>

And we set about. It seemed meaningless and much more complicated to store a cube as a description of a physical object than storing and bundling individual 6 planes consisting of arrays of 9 elements. I sat down to write the UI and render the cube, Dima sat down to describe the cube object and its modifications. In order to perform absolutely any set of actions on a cube, you need to be able to perform 3 operations:
1. Rotation of the cube to the left
2. Rotation of the cube up
3. The rotation of the frontal plane clockwise

I think it makes no sense to prove the statement, it is quite intuitive.

When rotating the cube, for example, upwards, it is necessary to cyclically swap 4 arrays of planes, rotate the left and right sides against and clockwise, respectively, and also reflect the back plane along the horizontal axis. The next morning, I killed almost 2 hours of time to realize the last fact, getting after the rotations of the virtual and real cubes a divergence in symmetry. The cube has learned to support commands from the standard formula record (Right, L eft, U pper, D own, F ront) through the .modify method, as well as their counter-hourly modifications with an apostrophe. Next, I wrote a runSequence function that allows you to perform a formula entirely on a given cube. Part of the preparation of the interpreter was almost complete. The last stroke I did was the shuffle function with the output of a new random formula for shuffling a cube, and just in case I checked the result of the interpreter and the real cube. Now everything, the routine part is over.

The society of Cubes, in which there is no color differentiation, is devoid of purpose.

I thought. Each member of the Cuban Population, each small Cubic, must represent how close he is, as a person, to the Highest Cuba. Otherwise, this social group is obviously stuck in chaos and modification excesses. First of all, I sat down at the description of the fitness function. It was obvious that simply counting the number of identical colors on each of the planes, erecting them, say, in a square, and adding them up is desirable, but impossible. Otherwise, the Cuba population will never be selected from the nearest local maximum. A ray of hope must be more focused. I described the function in accordance with the classical methods of assembly - in layers. Moreover, each next layer, and each next element of the current layer, gave a tangible increase in fitness, which made it possible for the more adapted newly emerged Kubobogami to quickly dominate the population.

 function calcTargetStickers (cube, side, cells) {
     var target = cube.get (side, 4);
     cells = cells ||  [0, 1, 2, 3, 4, 5, 6, 7, 8];
     var count = 0;
     for (i = 0; i <cells.length; i ++) {
         count + = cube.get (side, cells [i]) == target?  ten;
     }
     return count;
 }

 ...
         var crossCoincidence = 0;
         / * [side1, cell_side1, front_cell] * /
         $ .map ([[1, 5, 3], [0, 7, 1], [3, 3, 5], [4, 1, 7]], function (el, i) {
             var p = calcTargetStickers (cube, el [0], [el [1]]);
             if (p && calcTargetStickers (cube, 2, [el [2]])) {
                 crossCoincidence ++;
             }
         });        
         points + = crossCoincidence * crossCoincidence * 50;
        
         var anglesCoincidence = 0;
         / * [side1, cell_side1, side2, cell_side2, front_cell] * /
         if (crossCoincidence == 4)
         $ .map ([[1, 2, 0, 6, 0], [0, 8, 3, 0, 2], [3, 6, 4, 2, 8], [4, 0, 1, 8, 6]], function (el, i) {
             if (calcTargetStickers (cube, el [0], [el [1]]) && calcTargetStickers (cube, el [2], [el [3]]) && calcTargetStickers (cube, 2, [el [4]])) {
                 anglesCoincidence ++;
             }
         });
         points + = anglesCoincidence * anglesCoincidence * 100;        
       
        
         var layer2Coincidence = 0;
         / * [side1, cell_side1, side2, cell_side2] * /
         if (anglesCoincidence == 4 && crossCoincidence == 4)
         $ .map ([[1, 1, 0, 3], [0, 5, 3, 1], [3, 7, 4, 5], [4, 3, 1, 7]], function (el, i) {
             if (calcTargetStickers (cube, el [0], [el [1]]) && calcTargetStickers (cube, el [2], [el [3]])) {
                 layer2Coincidence ++;
             }
         });
         points + = layer2Coincidence * layer2Coincidence * 200;
        
        
         var layer3Coincidence = 0;
         / * [side1, cell_side1] * /
         if (layer2Coincidence == 4)
         $ .map ([[1, 3], [0, 1], [3, 5], [4, 7]], function (el, i) {
             if (calcTargetStickers (cube, el [0], [el [1]])) {
                 layer3Coincidence ++;
             }
         });
         points + = layer3Coincidence * layer3Coincidence * 300;
        
        
          var layer3Angles = 0;
         / * [side1, cell_side1, side2, cell_side2] * /
         if (layer3Coincidence == 4)
         $ .map ([[1, 0, 0, 0], [0, 2, 3, 2], [3, 8, 4, 8], [4, 6, 1, 6]], function (el, i) {
             if (calcTargetStickers (cube, el [0], [el [1]]) && calcTargetStickers (cube, el [2], [el [3]])) {
                 layer3Angles ++;
             }
         });
         points + = layer3Angles * layer3Angles * 400;
         if (layer3Angles == 4)
             solved = true; 

Each level contains a check of four elements, side or corner, whether these elements are in place. If all 4 elements are in place, we can proceed to the next level. This ensures smooth segregation of the entire population.

Next came the genetic algorithm itself. Obviously, the genome is some kind of template modification of Cuba. Genome - the entire set of modifications that led to the current state. What is the result of crossing cubes? Nothing, they are all same-sex and multiply by budding. In each round of evolution, all genomes mutate by adding genes to an already existing genome. Another parameter of the mutation is the value of geneMaxAppendCount - the maximum possible number of genes that will be added during the next mutation. This is an important number that regulates how complex a modification a cube can generate at one time. After a mutation, Cuba is considered its fitness, and then all other cubes. Then the average temperature in the hospital is considered, and on the basis of it, how widely the genotype of a particular Cuba will now spread in the population:

             var poluttionCount = Math.floor ((1) * (curFitness / averageTemperature - 1));
             poluttionCount * = poluttionCount;
             poluttionCount--;

Further, this stronger Cube removes a few weaker Population Cubes, and the next evolutionary turn begins.



Hooray! It is working.
The main problem I encountered was in the very last stage of the assembly: 2 levels were fully assembled, the sides were right on the 3rd level, and even in their places are the corners - all that was left was to turn a few corners in an anti-clockwise direction and now fully finished Cube ... But, this stage keeps a trick: during the final rotation of the corners, and they are always either 0 or 2 or more - all the two lower layers of the cube are destroyed until all the upper corners are turned to the correct position , yes, and so that all modifications and must be carried out with one and the same plane, but in the end, in addition to properly align along a horizontal plane all 3 fully assembled Cube layer. And despite the fact that even a two-year-old child will intuitively cope with the latest action, I didn’t want to put some special cases into the fitness function. The task of the evolutionary algorithm by any means is to skip the hole, which is necessary for the intermediate assembly of the final part. For this, I did two things:

1. In the set of formulas, I added the formulas for the rotation of the angle in the repetition of 2x and 4x, so that the angle turns against or clockwise for 1 gene, respectively. This increases the likelihood of performing most of the operation in one mutation.
2. Introduced the value of geneMaxAppendCount and included it in the fitness function: points + = cube.geneMaxAppendCount * 30; . The fact is that usually Cubes start from the maximum value of 4 or 5. At the very beginning, when improving Cuba is easy, it occurs after 1 or 2 genes, Cubes with short genetic transitions start to dominate the population. At the very last stage, such a strategy no longer passes, and we should encourage individuals who are trying to find more complex solutions, but so that the growth of geneMaxAppendCount does not become an end in itself of the population.

These two tricks allowed to solve any Rubik's Cube on average for 300 operations (excluding the rotation operations of the whole Cuba). Sometimes the process is delayed at the last stage, until the random mutation survives the hole temporarily destroying the Cube. Manually, according to the most primitive algorithm, I collect the cube for an average of 170 operations. But I think for the re-selection algorithm this is quite a reasonable number, and besides, the population can be given the task of reducing the length of the genotype, which will drastically reduce the required number of operations.

Further, on a lower-level solution.

As possible genes, the program uses a set of formulas that I copied from a random article on the Internet.

 var formulHigh = [
     "U", "D", "<", "^", ">", "v", "<", "^", ">", "v", 
     "R 'D' R D",  
     "U 'L' ULUFU 'F'", "FRUR 'U' F '", 
     "RUR 'URUU R'", "URU 'L' UR 'U' L", "U 'L' URU 'LU R'",
     "R 'D' RDR 'D' R D", "R 'D' RDR 'D' RDR 'D' RDR 'D' R D"
 ]; 

I thought, is it possible to solve the problem completely cleanly, using only rotation operators and basic modifications?

  var formulLow = [
     "U", "F", "<", "^", ">", "v", "R", "L", "D",
     "R 'D' RDR 'D' R D", "R 'D' RDR 'D' RDR 'D' RDR 'D' R D"
 ]; 

The formulas for turning the corners seemed to be absolutely necessary for me, otherwise the prefinal hole seems to be insurmountable for a reasonable period of time.

I was faced with the following problem: even small fossa had already been overcome with difficulty. Due to the complexity of the order of the way to a useful modification, Cuba is very difficult to survive periods of temporary destruction. It was necessary in some way to ensure the patronage of some brave Cubes, gone in search of the best form. I decided to introduce a policy of concessional lending to the population. In the case when there were no significant improvements in fitness over the last 100 rounds of evolution, occasional Cubes were credited without interest for 30 rounds with additional fitness. But they could not use their credit, so that only at the expense of it to rise above the entire population and breed. They received temporary protection from more currently adapted Cubes in order to have more chances to reach the next winning configuration.

The idea, in my opinion, is not bad, but apparently I did not tighten the settings, so I did not get a strong efficiency gain.



Probably, a “clean” solution requires a large population by several orders of magnitude, in which the space of available options will dramatically expand. By the way, in Chrome, the code runs noticeably faster than my FF.

What a result I can take. This is my first use of the genetic algorithm, and, fortunately, successful. The goal has been achieved, with the least resistance. I give the baton to you, habrovchanin, maybe you can get the population to come to a decision "clean".

Online demo: http://misc.motogipsy.ru/cube/
Archive with code: http://misc.motogipsy.ru/cube/cube.zip
Code with collabedit: http://misc.motogipsy.ru/cube/index_net.html