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

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.

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.

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.