Сборка Кубика Рубика генетическим алгоритмом online без смс



    В то время пока я собирался на ланч, мой ко-воркер Дейв окликнул меня: «Хэй, Алекс, а ты не хочешь заниматься улучшениями навыков своего программирования?». Я задумался. Это было интересное предложение, но я склонялся ответить отказом: «Сейчас я занимаюсь развитем навыков говорения на языках, дружище!». Ладно, шучу. Утро началось с того, что я добрался до почты и заполучил в руки копеечный китайский Кубик, случайно заказанный на али. К обеду я проштудировал мануал сборки и обновил мышечную память, а к вечеру пришло осознание, что я наигрался. Будущее кубика было ясным: он будет пылиться на полке, раз или два в неделю может быть я буду его собирать, чтобы привести мысли в порядок или отвлечься, но не более того. Соревнование в механической скорости сборки? Non merci, уж лучше скворечники делать…

    Ситуацию, как всегда, спасли мысли об автоматизации. После недолгого изучения я узнал рекогнисцировку. Для начала, число Бога уже давно найдено и равно 20. Правда задача сборки от этого не упрощается, т.к. использовать граф кратчайших путей для всех возможных конфигураций кубика не очень спортивно и немножко накладно по ресурсам. Алгоритм Бога предполагает под собой некое разумное количество использованной памяти, и в то же время обязан обеспечить минимально возможное число модификаций. Так вот, такого алгоритма еще нет. Есть ряд алгоритмов, позволяющих заметно ускорить сборку по сравнению с традиционными шаблонными методоми, но повторять кем-то уже проложенный (математически) путь мне показалось скучным. Если кому интересно, вот хороший анализ Далее есть традиционные шаблонные методы. Идея здесь в послойной сборке снизу вверх с использованием формул. Формула — последовательность модификаций Кубика, приводящая к таким-то целевым модификациям, и таким-то побочным. Соответственно, побочные модификации почти всегда падают на еще не собранные слои. Различаются шаблонные методы уровнем детализации шаблонов. Всякого рода спидкуберы знают все мыслимые шаблоны для большого количества частных случаев, что позволяет отыграть лишнюю 0.1 секунду с каждой модификации на соревнованиях. Пример, на что еще можно потратить жизнь.

    Итак, я постепенно формировал для себя задачу. В итоге, формулируется она так: за кратчайшее реальное время необходимо написать решалку для Кубика Рубика.

    Что мы знаем о Кубике? Число его состояний описывается как
    (8! × 3^7) × (12! × 2^11)/2 = 43 252 003 274 489 856 000
    .
    Именно это число накладывает ограничения на использование графа кратчайших путей. Что мы знаем о его правилах? То что каждый конкретный элемент (боковой или угловой) должен стоять точно на своём месте. Что является точным местом? Для бокового элемента — это соотстветствие обоих его цветов цветам центральных элементов, для углового элемента — соответствие трёх центральных элементов трём цветам этого углового элемента.

    image

    Таким образом мы можем в любой момент времени просто ответить на вопрос — «стоит ли данный элемент на своём месте?». Второй аспект, который мы знаем — Кубик может быть собран послойно, при чём каждый слой собирается постепенно. А это значит… па-пара-парам! Нужна градиентная эвристика. Осталось лишь выбрать метод реализации. Алгебраические методы я не стал рассматривать, т.к. мне хотелось получить некое решение, легко обобщаемое на подобый класс задач. (То что получилось я могу не слишком сложно обобщить до 11*11*11, к примеру) Еще был вариант: подробно забить маски шаблонов и формулы к ним, просто автоматизировав любую из статей в гугле «сборка Кубика Рубика». Но по понятным причинам, кроме тоски этот вариант не навевал ничего.

    Оставался перебор. Несмотря на полное возможное число состояний, перебор представлялся мне самым простым решением. Оставалось выяснить детали реализации. Интуиция подсказывала мне, что потребуется некая конкурентная среда возможных вариантов, чтобы из представленных вариантов было быстрее найти переход на следующий уровень сборки. В общем-то вариант генетического алгоритма начал доминировать сам собой.

    Средой исполнения я решил выбрать обычный современный браузер, т.к. эта штука идеально выполняла требование скоростной реализации. Я поделился идеей с приятелем, занимавшимся в этот момент выпасом гусей в Белоруссии, или чем-то в этом роде. Дима подхватил предложение, мы начали смотреть способы параллельного объединения усилий. Довольно быстро нашёлся collabedit.com, позволявший писать JavaScript код нескольким людям одновременно. Я закинул html на хостинг с инклюдами
    <script src=«collabedit.com/download?id=svxve»></script>
    <script src=«collabedit.com/download?id=s8xkv»></script>

    И мы приступили. Хранить кубик как описание физического объекта нам показалось бессмысленным и гораздо более сложным процессом, чем хранение и связка отдельных 6-ти плоскостей, состоящих из массивов по 9 элементов. Я сел за написание UI и рендеринг кубика, Дима сел за описание объекта куба и его модификаций. Для того чтобы выполнить над кубиком абсолютно любой набор действий, требуется уметь выполнять 3 операции:
    1. Вращение куба влево
    2. Вращение куба вверх
    3. Вращение фронтальной плоскости по часовой стрелке

    Я думаю нет смысла доказывать утверждение, оно вполне интуитивно понятно.

    При вращении куба, например, вверх, необходимо циклично поменять местами 4 массива плоскостей, вращать левую и правую стороны против и по- часовой стрелке соответсвенно, а так же отразить по горизонтальной оси заднюю плоскость. На следующее утро я убил практически 2 часа времени на осознание последнего факта, получая после вращений виртуального и реального кубиков расхождение в симметрии. Кубик научился поддерживать через метод .modify (symbol) команды из стандартной формульной записи (Right, Left, Upper, Down, Front), а так же их против-часовые модификации с апострофом. Далее я написал функцию runSequence позволяющую выполнять формулу целиком над заданным кубиком. Часть подготовки интерпретатора была почти завершена. Последним штрихом я сделал функцию shuffle с выводом новой случайной формулы тасования кубика, и на всякий случай сверил результат интерпретатора и реального кубика. Теперь всё, рутинная часть позади.

    Общество Кубов, в котором нет цветовой дифференциации, лишено цели.

    подумалось мне. Каждый член Популяции Кубов, каждый маленький Кубик, должен представлять на сколько он близок, как личность, к Высшему Кубу. В противном случае данная социальная группа очевидно повязнет в хаосе и модификационных излишествах. Первым делом, я сел за описание фитнесс-функции. Было очевидно, что просто считать количество одинаковых цветов на каждой из плоскостей, возводить их, скажем, в квадрат и складывать — хочется, но нельзя. В противном случае из ближайшего локального максимума популяция Кубов никогда не выберется. Луч надежды должен быть более узконаправленным. Я описал функцию в соотстветсвии с классическими методами сборки — послойно. При чем каждый следующий слой, и каждый следующий элемент текущего слоя давал ощутимый прирост фитнесса, что позволяло более приспособленным только что появившимся Кубособям быстро доминировать в популяции.

    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 ? 1 : 0;
        }
        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;


    Каждый уровень содержит в себе проверку четырёх элементов, боковых или же угловых, стоят ли эти элементы на своих местах. Если все 4 элемента стоят на своих местах, мы можем переходить к следующему уровню. Это обеспечивает плавную сегрегацию всей популяции.

    Далее, предстоял сам генетический алгоритм. Очевидно, геном является некая шаблонная модификация Куба. Геномом — весь набор модификаций, который привел к текущему состоянию. Что же является результатом скрещиванием Кубов? Ничего, они все однополые и размножаются почкованием. В каждом раунде эволюции происходит мутация всех геномов путем добавления генов к уже существующему геному. Еще одним параметром мутации является значение geneMaxAppendCount — максимальное возможное число генов, которые будут добавлены во время следующей мутации. Это важное число, которое регулирует, на сколько сложную модификацию Куб сможет сгенерировать за один раз. После мутации Куба считается его фитнесс, а затем и всех остальных кубов. Затем считается средняя температура по больнице, и на основании неё — насколько широко генотип конкретного Куба распространится теперь в популяции:
                var poluttionCount = Math.floor((1) * (curFitness / averageTemperature - 1) );
                poluttionCount *= poluttionCount;
                poluttionCount--;
    

    Далее этот более сильный Куб вымещает собой несколько более слабых Кубов популяции, и начинается следующий виток эволюции.



    Ура! Оно работает.
    Основная проблема с которой я столкнулся, заключалась в самом последнем этапе сборки: полностью собраны 2 уровня, на 3-м уровне верно стоят боковины, и даже на своих местах расположены углы — осталось лишь повернуть по- или против часовой стрелки несколько уголков и вот он полностью готовый Куб… Но, этот этап хранит в себе хитрость: во время финального поворота углов, а их всегда либо 0, либо 2 и более — разрушаются все два нижних слоя куба до тех пор, пока не будут повернуты в правильное положение все верхние углы, да еще и так, что все модификации должны производиться с одной и той же плоскости, а в конце вдобавок нужно правильно совместить по горизонтальным плоскостям все 3 полностью собранных слоя Кубика. И несмотря на то, что с самым последним действием интуитивно справится даже двухлетний ребёнок, мне не хотелось закладыавть в фитнесс-функцию каких-то частных случаев. Задача эволюционного алгоритма любыми способами перескочить яму, которая необходима для промежуточной сборки финальной части. Для этого я сделал две вещи:

    1. В набор формул я добавил формулы поворота угла в повторении 2х и 4х, для того чтобы угол поворачивался против или по часовой стрелке за 1 ген соответственно. Это увеличивает вероятность выполнить большую часть операцию за одну мутацию.
    2. Ввел значение geneMaxAppendCount и включил его в фитнесс-функцию: points += cube.geneMaxAppendCount * 30;. Дело в том, что обычно Кубы стартую с максимального значения в 4 или 5. В самом начале, когда улучшение Куба сделать легко, оно происходит за 1 или 2 гена, в популяции начинают доминировать Кубы с короткими генетическими переходами. На самом последнем этапе подобная стратегия уже не проходит, и мы должны поощрять особей, которые пытаются найти более сложные решения, но так, чтобы рост geneMaxAppendCount не стал самоцелью популяции.

    Два этих ухищрения позволили гарантированно решать любой Кубик Рубика в среднем за 300 операций (исключая операции вращения всего Куба). Иногда процесс затягивается на последнем этапе, до тех пор, пока случайная мутация не переживет яму, временно разрушающую Куб. Вручную, по самому примитивному алгоритму я собираю Кубик в среднем за 170 операций. Но я считаю для переборного алгоритма это вполне разумное число, к тому же перед популяцией вполне можно поставить задачу сокращения длины генотипа, что резко снизит требуемое число операций.

    Далее, о более низкоуровневом решении.

    Как возможные гены, программа использует набор формул, которые я скопировал из случайной статьи в интернете.
    var formulHigh = [
        "U", "D", "<", "^", ">", "v", "<", "^", ">", "v", 
        "R' D' R D",  
        "U' L' U L U F U' F'", "F R U R' U' F'", 
        "R U R' U R U U R'", "U R U' L' U R' U' L", "U' L' U R U' L U R'",
        "R' D' R D R' D' R D", "R' D' R D R' D' R D R' D' R D R' D' R D"
    ];


    Я задумался, возможно решить задачу совсем чисто, на использовании лишь операторов вращения и базовых модификаций?

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


    Формулы поворота углов мне показались однозначно необходимыми, в противном случае предфинальная яма представляется мне непреодолимой за разумный промежуток времени.

    Я столкнулся со следующей проблемой: даже небольшие ямки уже преодолевались с трудом. Из-за усложнения на порядок пути до полезой модификации, Кубы очень трудно переживали периоды временного разрушения. Нужно было каким-то образом обеспечить протекцию некоторых смелых Кубов, ушедших в поисках лучшей формы. Я решил ввести политику Льготного Кредитования Популяции. В случае, когда за последние 100 раундов эволюции не происходило значимых улучшений фитнесса, случайные Кубы безпроцентно кредитовались на 30 раундов дополнительным фитнессом. Но они не могли использовать свой кредит, чтобы только за счет него возвыситься над всей популяцией и расплодиться. Они получали временную протекцию от более приспособленных в данный момент Кубов, для того чтобы иметь больше шансов выйти на следующую выйгрышную конфигурацию.

    Идея, на мой взгляд, неплохая, но видимо я недокрутил настройки, поэтому сильной прибавки эффективности я не получил.



    Вероятно, на «чистое» решение требуется на несколько порядков большая популяция, в которой пространство доступных вариантов резко расширится. Кстати, в Хроме код работает заметно быстрее моего ФФ.

    Какой итог я могу подвести. Это первое моё применение генетического алгоритма, и, к счастью, успешное. Поставленная цель достигнута, при чём путём наименьшего сопротивления. Передаю эстафетную палочку тебе, хабровчанин, возможно у тебя получится заставить популяцию придти к решению «чисто».

    Онлайн демо: http://misc.motogipsy.ru/cube/
    Архив с кодом: http://misc.motogipsy.ru/cube/cube.zip
    Код с collabedit: http://misc.motogipsy.ru/cube/index_net.html
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 14
      +3
      Спасибо за статью, сам собирал кубик и также разочаровался. Теперь поподробнее изучу генетические алгоритмы — тут у меня яма.
      Топовый пример занятия для прожига времени — называется Speed Stacking.
        0
        Крутая статья, очень просто и на пальцах объясняет, зачем и для чего нужны генетические алгоритмы. Надо бы самому что-то такое намутить.
          +1
          A* должен катить. Только опять же все будет зависеть от хорошей «допустимой эвристической оценки» (admissible/consistent heuristics). Не всякая функция оценки катит для поиска! Но если поэкспериментировать и найти хорошую, то может очень сильно ускорить. Вот в курсе по AI на edX. В этом же курсе есть еще несколько «атак» на «сложные переборные поиски»
            +2
            Спасибо огромное! постараюсь изучить в выходные.
            0
            Так ведь результат эволюции у вас получается просто набор команд для решения одного кубика. Это вовсе не то для чего существуют металгоритмы в стиле генетического. Вы должны были бы поставить задачу вот так: генетическим способом найти функцию которая собирает любой кубик. Результатом работы метаалгоритма является алгоритм а не одиночное решение.

            На самом деле вы просто сделали алгоритм А*-поиска.

              0
              Мне было интересно применить генетический алгоритм в данной задаче — и я его применил. Это первично )
              По поводу метаалгоритмов и генетического в частности — я нигде не видел доселе подобного суждения о предназначении, вы не могли бы показать соус? Напрмер, когда ставится задача оптимизации лопасти турбины — эта задача решается очевидно под конкретный диаметр, и под конкретную рабочую скорость. Я не верю что какой-то алгоритм обязан выдасть формулу или функцию описывающую все формы лопастей под все скорости и все размеры.
                0
                Например когда вы используете другую метаалгоритмическую систему — нейронные сети, какая у вас цель? Ну например создать сеть которая умеет распознавать лица, или капчу. Вы же не одну конкретную картинку распознать хотите.

                На самом деле задача которую вы поставили и ее решение ( особенно включая факт что у вас нет перекрестных мутаций) фактически сводится к хрестоматийной задаче: 8 Puzzle . Можно конечно сказать что генетический подход можно использовать для решения А*-задач. Но как перекрестные мутации и являются главной фишкой подхода которая в теории позволять получить результат быстрее.

                Кстати если вы таки попробуете сделать подход с скрещиванием то отпишитесь, интересно заработает быстрее или нет.

                  0
                  Я понял. Вы говорите о том, что логичнее было бы построить систему, оперирующую скажем шаблонами и их применением, а не конкретными случайными модификациями кубика? Т.е. на выходе самая живущая особь получила бы в генотипе все возможные шаблоны действий в тех или иных случаях? Должен признаться, мне это в голову не приходило, довольно интересная задумка… Ну что ж, будет чем заняться в следующий раз, если энтузиазм накатит, спасибо. А по текущему решению… нечего скрещивать тут, я не вижу что.
                    0
                    Ну почему нечего. Вот например есть у вас 10 наборов команд и их фитнес-значения. Берем например топ 2 набора, режем их пополам и склеиваем половинки, получаем в итоге еще 4 набора для которых тоже считаем фитнес-функцию и добавляем в пул. Таким образом в пуле уже 14 наборов. Выбрасываем нижние 4 и у нас снова 10. Но проблема в том что таким образом очень трудно случайно попасть на решение. А это имхо уже проблема больше того что генетический подход больше подходит для статистических задач в которых нет однозначного решения.

                    Генетическим алгоритмом интересно создавать ботов для игр типа Цивилизации. Например для начала в пул ставим ботов которые один мирный, второй форсит науку, третий вступает в войны и тд. Фитнес-функция для них будет например количество ресурсов после 1000 ходов в игре. В конце итерации путем скрещивания ( подкручивания разных коэффициентов в настройках ботов) получаем первые мутации. То есть если боты выстроились по фитнесу в таком порядке: наука > война > мир > экономика, то создаем мутацию которая фокусируется на науке на 40%, на войне 30%, 20% мире и 10% экономике и например еще несколько ( переставив мир и экономику местами ) и снова прогоняем.

                    Идея в том что подбирать коэффициенты способом мутаций быстрее чем брутфорс перебором, так как вероятность что мутация будет не хуже чем родитель больше сем если просто менять перебором.

                    В варианте с кубиком конечно труднее так как результат должен быть не статистический а конкретный. Это как если пробовать написать полностью идеального бота — долго, мучительно и требует множества итераций
                      0
                      В генетических алгоритмах нужно совмещать скрещивание с мутацией, потому что если использовать только скрещивание, то быстро получатся осыби с одинаковыми генами и соответственно однородные, а если использовать только мутации — то это практически все равно, что рандомный поиск!
                0
                Это вовсе неправда, что «метаалгоритмы», как вы их называте, должны находить функцию, которая будет собирать любой кубик. Что насчет nP проблем, которые можно (насколько известно) решить только перебором? Для них ведь нет функции. А генетические алгоритмы — это направленный перебор, чтобы прийти к решению быстрее, чем случайный поиск.
                0
                Идея очень интересная! Я сначала не понял, как работает Ваш алгоритм, и зачем geneMaxAppendCount, но потом разобрался, что каждый ген — это изменение Куба, и соответсвенно иногда невозможно найти резултьтат за 5 ходов, поэтому мы добавляем гены. Но можно было задать определнное постоянное значение, например 50 генов, за которое решение должно быть найдено и посмотреть, сколько раундов понадобиться, если проблему вообще можно решить при этом количестве генов.

                И почему вы не используете скрещивание?! Со скрещиванием, вы сможете решать проблемув разы быстрее, я уверен! Как написал выше, без скрещивание получается случайный поиск, когда выбираются лучшие значения для следующих случайных модификаций. Вся сила генетических алгоритмов в кросс-оверах совмещенных с мутациями, потому что скажем вначале оптимально поворачивать куб, а в конце крутить, поэтому если скрестить два фенотипа, которые делают именно это, но по отдельности, получится оптимальное решение!

                К тому же, Вы можете попробовать sequential и generational подходы: первый, когда новый Куб создается и сразу же помещается в популяцию, после чего в следующем раунде он будет уже доступен для генерации детей, второй, когда создаются скажем все 50 Кубов, которые вместе заменяют всю популяцию, и процесс повторяется заново. Если честно, не помню плюси и минусы каждого подхода, но они связаны со скоростью нахождения решения и риском того, что все Кубы в попляции будут более-менее однородны и соответственно не будет прогресса.

                Я большой фанат генетических алгоритмов, если будет время попробую тоже что-то сделать с кубиками! Спасибо за идею и за описание самой проблемы и метода modify! Классный получился топик, нравится гифка!

                P.S. Я думал, что можно было бы закодировать кубик как gggggggggyyyyyyyyyooooooooorrrrrrrrrbbbbbbbbb, например, где каждый ген — это меленький квадратик, но тогда очень много компьютаций понадобиться, чтобы вычислять возможные изменения, потому что поворот — это изменение 3*5 генов, и по определнному правилу, т.е. если один квадратик стал желтым, то соответсвенно определенный другой должен стать синим при повороте. Можно было бы делать мутацию/скрещивание и проверять, возможна ли она, но это очень много ресурсов, нежели делать как Вы — кодировать именно изменения.

                  +1
                  Кстати математически доказано что любой кубик можно собрать за 20 ходов. Так что можно было б ограничится этим числом
                  0
                  image
                  И он все еще считает…

                  Похоже что-то тут не так.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое