Rubik's cube genetic algorithm solver?

Question

Is it possible Rubik's cube to be efficiently solved by genetic algorithms?

What kind of chromosome encoding should be used? How the crossover and mutation should be done?

I am using this model of the cube:

#ifndef RUBIKSCUBE_H_INCLUDED
#define RUBIKSCUBE_H_INCLUDED

#include "Common.h"
#include "RubiksSide.h"
#include "RubiksColor.h"
#include "RotationDirection.h"

class RubiksCube {
private:
    int top[3][3];
    int left[3][3];
    int right[3][3];
    int front[3][3];
    int back[3][3];
    int down[3][3];

    int (*sides[6])[3][3];

    std::string result;

    void spinSide(RubiksSide side) {
        static int buffer[ 3 ];

        if (side == TOP) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = left[i][2];
            }
            for (int i = 0; i < 3; i++) {
                left[i][2] = front[0][i];
            }
            for (int i = 0; i < 3; i++) {
                front[0][i] = right[3 - i - 1][0];
            }
            for (int i = 0; i < 3; i++) {
                right[i][0] = back[2][i];
            }
            for (int i = 0; i < 3; i++) {
                back[2][3 - i - 1] = buffer[i];
            }
        } else if (side == LEFT) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = down[i][2];
            }
            for (int i = 0; i < 3; i++) {
                down[3 - i - 1][2] = front[i][0];
            }
            for (int i = 0; i < 3; i++) {
                front[i][0] = top[i][0];
            }
            for (int i = 0; i < 3; i++) {
                top[i][0] = back[i][0];
            }
            for (int i = 0; i < 3; i++) {
                back[3 - i - 1][0] = buffer[i];
            }
        } else if (side == BACK) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = down[0][i];
            }
            for (int i = 0; i < 3; i++) {
                down[0][i] = left[0][i];
            }
            for (int i = 0; i < 3; i++) {
                left[0][i] = top[0][i];
            }
            for (int i = 0; i < 3; i++) {
                top[0][i] = right[0][i];
            }
            for (int i = 0; i < 3; i++) {
                right[0][i] = buffer[i];
            }
        } else if (side == RIGHT) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = down[i][0];
            }
            for (int i = 0; i < 3; i++) {
                down[i][0] = back[3 - i - 1][2];
            }
            for (int i = 0; i < 3; i++) {
                back[i][2] = top[i][2];
            }
            for (int i = 0; i < 3; i++) {
                top[i][2] = front[i][2];
            }
            for (int i = 0; i < 3; i++) {
                front[3 - i - 1][2] = buffer[i];
            }
        } else if (side == FRONT) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = down[2][i];
            }
            for (int i = 0; i < 3; i++) {
                down[2][i] = right[2][i];
            }
            for (int i = 0; i < 3; i++) {
                right[2][i] = top[2][i];
            }
            for (int i = 0; i < 3; i++) {
                top[2][i] = left[2][i];
            }
            for (int i = 0; i < 3; i++)
                left[2][i] = buffer[i];
        } else if (side == DOWN) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = front[2][i];
            }
            for (int i = 0; i < 3; i++) {
                front[2][i] = left[i][0];
            }
            for (int i = 0; i < 3; i++) {
                left[i][0] = back[0][3 - i - 1];
            }
            for (int i = 0; i < 3; i++) {
                back[0][i] = right[i][2];
            }
            for (int i = 0; i < 3; i++) {
                right[3 - i - 1][2] = buffer[i];
            }
        }
    }

    void spinClockwise(int side[3][3], int times, RubiksSide index) {
        static int buffer[3][3];
        static int newarray[3][3];

        if (times == 0) {
            return;
        }

        /*
         * Transponse.
         */
        for (int j = 0; j < 3; j++) {
            for (int i = 0; i < 3; i++) {
                newarray[j][i] = side[i][j];
            }
        }
        /*
         * Rearrange.
         */
        for (int i = 0; i < 3; i++) {
            static int cache = 0;
            cache = newarray[i][0];
            newarray[i][0] = newarray[i][2];
            newarray[i][2] = cache;
        }

        spinSide(index);
        memcpy(buffer, newarray, sizeof(int)*3*3);

        for (int t = 1; t < times; t++) {
            for (int j = 0; j < 3; j++) {
                for (int i = 0; i < 3; i++) {
                    newarray[j][i] = buffer[i][j];
                }
            }
            for (int i = 0; i < 3; i++) {
                static int cache = 0;
                cache = newarray[i][0];
                newarray[i][0] = newarray[i][2];
                newarray[i][2] = cache;
            }

            spinSide(index);

            memcpy(buffer, newarray, sizeof(int)*3*3);
        }

        memcpy(side, buffer, sizeof(int)*3*3);
    }

    double euclidean(const RubiksCube &cube) const {
        double difference = 0.0;

        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                difference += abs(top[i][j]-cube.top[i][j]);
                difference += abs(left[i][j]-cube.left[i][j]);
                difference += abs(right[i][j]-cube.right[i][j]);
                difference += abs(front[i][j]-cube.front[i][j]);
                difference += abs(back[i][j]-cube.back[i][j]);
                difference += abs(down[i][j]-cube.down[i][j]);
            }
        }

        return difference;
    }

    double colors(const RubiksCube &cube) const {
        //TODO Change array with STL maps.
        static const double coefficients[7][7] = {
            {0, 0, 0, 0, 0, 0, 0},
            {0, 1, 2, 2, 2, 2, 4},
            {0, 2, 1, 2, 4, 2, 2},
            {0, 2, 2, 1, 2, 4, 2},
            {0, 2, 4, 2, 1, 2, 2},
            {0, 2, 2, 4, 2, 1, 2},
            {0, 4, 2, 2, 2, 2, 1},
        };

        double difference = 0.0;

        /*
         * Count matches for all sides.
         */
        for(int s=0; s<6; s++) {
            for(int i=0; i<3; i++) {
                for(int j=0; j<3; j++) {
                    /*
                     * If colors are equal calculate distance.
                     */
                    difference += coefficients[(*sides[s])[1][1]][(*sides[s])[i][j]];
                }
            }
        }

        return difference;
    }

    double hausdorff(const RubiksCube &cube) const {
        long ha = 0;
        long hb = 0;
        long result = 0;

        for(int m=0; m<3; m++) {
            for(int n=0; n<3; n++) {
                int distances[] = {0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

                for(int i=0, d=0; i<3; i++) {
                    for(int j=0; j<3; j++) {
                        distances[d++] = abs(top[m][n]-cube.top[i][j]);
                        distances[d++] = abs(left[m][n]-cube.left[i][j]);
                        distances[d++] = abs(right[m][n]-cube.right[i][j]);
                        distances[d++] = abs(front[m][n]-cube.front[i][j]);
                        distances[d++] = abs(back[m][n]-cube.back[i][j]);
                        distances[d++] = abs(down[m][n]-cube.down[i][j]);
                    }
                }

                int min = distances[0];
                for(int d=0; d<54; d++) {
                    if(distances[d] < min) {
                        min = distances[d];
                    }
                }

                if(min > ha) {
                    ha = min;
                }
            }
        }

        for(int m=0; m<3; m++) {
            for(int n=0; n<3; n++) {
                int distances[] = {0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

                for(int i=0, d=0; i<3; i++) {
                    for(int j=0; j<3; j++) {
                        distances[d++] = abs(top[i][j]-cube.top[m][n]);
                        distances[d++] = abs(left[i][j]-cube.left[m][n]);
                        distances[d++] = abs(right[i][j]-cube.right[m][n]);
                        distances[d++] = abs(front[i][j]-cube.front[m][n]);
                        distances[d++] = abs(back[i][j]-cube.back[m][n]);
                        distances[d++] = abs(down[i][j]-cube.down[m][n]);
                    }
                }

                int min = distances[0];
                for(int d=0; d<54; d++) {
                    if(distances[d] < min) {
                        min = distances[d];
                    }
                }

                if(min > hb) {
                    hb = min;
                }
            }
        }

        result = std::max(ha, hb);

        return(result);
    }

    friend std::ostream& operator<< (std::ostream &out, const RubiksCube &cube);

public:
    RubiksCube() {
        reset();

        sides[0] = &top;
        sides[1] = &left;
        sides[2] = &right;
        sides[3] = &front;
        sides[4] = &back;
        sides[5] = &down;
    }

    void reset() {
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                top[i][j] = GREEN;
                left[i][j] = PURPLE;
                right[i][j] = RED;
                front[i][j] = WHITE;
                back[i][j] = YELLOW;
                down[i][j] = BLUE;
            }
        }
    }

    double compare(const RubiksCube &cube) const {
        return euclidean(cube);
    }

    void callSpin(RubiksSide side, RotationDirection direction, int numberOfTimes) {
        if (numberOfTimes < 0) {
            numberOfTimes = -numberOfTimes;
            if(direction == CLOCKWISE) {
                direction = COUNTERCLOCKWISE;
            } else if(direction == COUNTERCLOCKWISE) {
                direction = CLOCKWISE;
            }
        }

        numberOfTimes %= 4;

        if (direction == CLOCKWISE) {
            if (side == NONE) {
                /*
                * Do nothing.
                */
            }
            if (side == TOP) {
                spinClockwise(top, numberOfTimes, TOP);
            }
            if (side == LEFT) {
                spinClockwise(left, numberOfTimes, LEFT);
            }
            if (side == RIGHT) {
                spinClockwise(right, numberOfTimes, RIGHT);
            }
            if (side == FRONT) {
                spinClockwise(front, numberOfTimes, FRONT);
            }
            if (side == BACK) {
                spinClockwise(back, numberOfTimes, BACK);
            }
            if (side == DOWN) {
                spinClockwise(down, numberOfTimes, DOWN);
            }
        }
    }

    void execute(std::string commands) {
        for(int i=0; i<commands.length(); i++) {
            callSpin((RubiksSide)commands[i], CLOCKWISE, 1);
        }
    }

    std::string shuffle(int numberOfMoves=0) {
        std::string commands = "";

        for(int i=0; i<numberOfMoves; i++) {
            switch(rand()%6) {
            case 0:
                commands+=(char)TOP;
                break;
            case 1:
                commands+=(char)LEFT;
                break;
            case 2:
                commands+=(char)RIGHT;
                break;
            case 3:
                commands+=(char)FRONT;
                break;
            case 4:
                commands+=(char)BACK;
                break;
            case 5:
                commands+=(char)DOWN;
                break;
            }
        }

        execute(commands);

        return commands;
    }

    const std::string& toString() {
        result = "";

        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(top[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(left[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(right[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(front[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(back[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(down[i][j]) + " ";
            }
        }

        /*
         * Trim spaces.
         */
        result.erase(result.size()-1, 1);
        result += '\0';

        return result;
    }

    void fromString(const char text[]) {
        std::string buffer(text);
        std::istringstream in(buffer);

        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> top[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> left[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> right[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> front[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> back[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> down[i][j];
            }
        }
    }
};

std::ostream& operator<< (std::ostream &out, const RubiksCube &cube) {
    for(int i=0; i<3; i++) {
        out << "      ";
        for(int j=0; j<3; j++) {
            out << cube.back[i][j] << " ";
        }
        out << std::endl;
    }

    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            out << cube.left[i][j] << " ";
        }
        for(int j=0; j<3; j++) {
            out << cube.top[i][j] << " ";
        }
        for(int j=0; j<3; j++) {
            out << cube.right[i][j] << " ";
        }
        for(int j=0; j<3; j++) {
            out << cube.down[i][j] << " ";
        }
        out << std::endl;
    }

    for(int i=0; i<3; i++) {
        out << "      ";
        for(int j=0; j<3; j++) {
            out << cube.front[i][j] << " ";
        }
        out << std::endl;
    }

    return out;
}

#endif

Eteocles

I don't want to say that it would be impossible, but most likely very difficult to implement. The chromosome would have to define the behavior of how the cube is solved. On a more abstract level the GA would evolve algorithms to solve the cube. Another option might be to define an algorithm that can solve a cube, and the GA would evolve parameters for the algorithm, but this makes the problem almost trivial. – Kurtzig

Also this question is too broad for StackOverflow. I might be wrong but the CS StackExchange might be the better place? – Kurtzig

I am thinking about encoding as string of instructions. For example: T - top D - down L - left R - right F - front B - back Each chromosome can be set of instructions like: TTBBFFLL and so one. – Eteocles

That could work, but only if the initial starting permutation of the cube was used for every fitness evaluation. Moreover your GA would only be good at solving that cube permutation and not all possible permutations. Its kind of cheating.. // If a different permutation was used then you would (I think but I may be wrong) be simply modeling randomness with the GA. Solving the cube with a given chromosome would have the same chance of generating the same random number in the range 0 - Possible cube permutations for every single run. There is no way a chromosome could become more fit. – Kurtzig

Yes. You are correct. The solution would not be universal, but in GA it is difficult to find universal solution when the problem is combinatorial. I am thinking to start with random population. As crossover I think to apply single cut point. Chromosomes will be with different length. For mutation I am thinking to change randomly selected instruction. – Eteocles

You will need to preserve the beginning of the chromosomes that perform well, possibly as the iteration number increases move the "cut point" further down the chromosomes. Also never mutate in front of the cut point. // Your still missing your fitness value. There is also the issue that there are infinite amount of sequences that will solve a single cube permutation. You will have to first determine the sequence you deem the "correct" way to solve the given permutation and base fitness off of that. – Kurtzig

It is very nice idea to move the "cut" point and the mutation to the back of the chromosomes. As fitness value I was thinking about Euclidean distance, but friend of mine said that Hausdorff distance will be better. The problem is that Hausdorff distance is very complicated and I can not imagine how I can apply it for two instances of the Rubik's cube (the shuffled and the initial). – Eteocles

Why not just use the percentage of correct moves? Regardless of "cut point" the chromosome with the most correct moves in it is seemingly more fit to solve the cube, or at least will be better at it in future generations. – Kurtzig

There can be local minimums in the situation described so far. The chromosomes either strictly get better at solving the specific permutation (with fitness based upon a chosen solution to that permutation) or die off. – Kurtzig

Answer 1

Disclaimer: I'm by far no expert on Rubik's cubes, I even never solved one

Solving a given Rubik's cube by GA

You have a given configuration and you want to use GA to produce the sequence of steps that solve this particular configuration.

Representation

For each of the axes there are three possible rotations, each of them in two directions. This gives following moves:

X1+, X1-, X2+, X2-, X3+, X3-,
Y1+, Y1-, Y2+, Y2-, Y3+, Y3-,
Z1+, Z1-, Z2+, Z2-, Z3+, Z3-

The genotype is then a sequence of these moves.

Genotype

There are two possibilites:

• variable-length genotype
• fixed-length genotype

Variable-length genotype follows the idea that we don't know, in advance, how many moves will the particular configuration take to solve. I'll come back to this variant later.

Fixed-length genotype can be used too. Even though we don't know how many moves will the particular configuration take to solve, we know that any configuration can be solved in 20 moves or less. Since 20 would mean that for some positions the algorithm would be forced to find the optimal solution (which could be quite hard), we can set the genotype length to, say, 50 to give the algorithm some flexibility.

Fitness

You need to find a good fitness measure for judging the quality of the solutions. Currently I can't think of a nice quality measure as I'm no expert on Rubik's cubes. However, you probably should incorporate the number of moves in your fitness measure. I'll come back to it a little bit later.

Also you should decide whether you are looking for any solution or for a good one. If you are looking for any solution, you can stop at the first solution found. If you are looking for a good solution, you don't stop at first solution found but instead you then optimize its length. You then stop when you decide to stop (i.e. after a desired amount of time spent searching).

Operators

The two basic operators - crossover and mutation - can be basically identical to classical GA. The only difference is that you don't have two states for a "bit" but 18. Even when using a variable-length genotype, the crossover can remain the same - you just cut the both genotypes in two pieces and swap the tails. The only difference from the fixed-length case is that the cuts won't be at the same positions, but rather independent of each other.

Bloat

Using the variable-length genotypes brings an unpleasant phenomenon, which is an excessive growth of the size of the solution, without a big impact on fitness. In Genetic Programming (which is quite different topic) this is called bloat. This can be controlled by two mechanisms.

The first mechanism I already mentioned - incorporate the length of the solution into the fitness. If you look for a good solution (i.e. you don't stop at finding the first one), the length is, of course, only the length of the effective part (i.e. the number of moves from the start up to the move that finishes the cube), not counting the rest.

The other mechanism I borrow from Grammatical Evolution (a Genetic Programming algorithm that also uses linear, variable-length genotypes), which is pruning. A pruning operator takes a solution and deletes the non-effective part of the genotype.

Other possibilites

You could also evolve something like a "policy" or strategy - a general rule that would, given a cube, decide what move to do next. That is far more difficult task, but definitely evolvable (meaning that you can use evolution to try to find it, not that you will find it eventually). You might use e.g. neural networks as a representation of the policy and use some neuro-evolution concepts and frameworks to achieve this task.

Or you could evolve a heuristic (using Genetic Progamming) for a given search algorithm, e.g. A*. The A* algorithm needs a heuristic to estimate the distance of a state to the final state. The more accurate this heuristic is, the faster the A* algorithm finds the solution.

Final remarks

From my experience, if you know something about the problem (which in case of Rubik's cube you do know), it is far better to use a dedicated or at least an informed algorithm to solve the problem rather than using an almost blind one like GA. In my opinion, Rubik's cube is not a good problem for GAs, or rather GAs are not a good algorithms for solving Rubik's cube.

Wingard

Yes, exactly. I would like to obtain set of rotation instructions after GA optimization. I do not see clearly how ANN can be used in such combinatorial problem. From what I know about A*, it is best used for path finding. – Eteocles

@TodorBalabanov ad A* - you are trying to find a path - from the initial position, through the rotations, to the solved state. Ad ANN - that was just an idea... basically the ANN would represent a function that would map the cube's configuration to the move to take, but it probably won't work. Ad genetic solving - I'll update my answer in a while. – Wingard

I like the Rubik's cube problem, because it is a combinatorial problem and I can measure how efficient is GA. – Eteocles

Answer 2

I have done a lot of experiments and I have found that such chromosome representation is good enough, but genetic algorithm gets trapped in local optimum. Solution of the Rubik's cube is highly combinatorial and genetic algorithms are not strong enough to be used for such problem.

Eteocles

Answer 3

A post doc at my university wrote his thesis about this topic and solved it basically. As far as I remember, he used some combined moves as operators.

https://link.springer.com/chapter/10.1007/978-3-642-12239-2_9

Nail El-Sourani, Sascha Hauke, Markus Borschbach

Solutions calculated by Evolutionary Algorithms have come to surpass exact methods for solving various problems. The Rubik’s Cube multiobjective optimization problem is one such area. In this work we present an evolutionary approach to solve the Rubik’s Cube with a low number of moves by building upon the classic Thistlethwaite’s approach. We provide a group theoretic analysis of the subproblem complexity induced by Thistlethwaite’s group transitions and design an Evolutionary Algorithm from the ground up including detailed derivation of our custom fitness functions. The implementation resulting from these observations is thoroughly tested for integrity and random scrambles, revealing performance that is competitive with exact methods without the need for pre-calculated lookup-tables.

Lacilacie