В то время пока я собирался на ланч, мой ко-воркер Дейв окликнул меня: «Хэй, Алекс, а ты не хочешь заниматься улучшениями навыков своего программирования?». Я задумался. Это было интересное предложение, но я склонялся ответить отказом: «Сейчас я занимаюсь развитем навыков говорения на языках, дружище!». Ладно, шучу. Утро началось с того, что я добрался до почты и заполучил в руки копеечный китайский Кубик, случайно заказанный на али. К обеду я проштудировал мануал сборки и обновил мышечную память, а к вечеру пришло осознание, что я наигрался. Будущее кубика было ясным: он будет пылиться на полке, раз или два в неделю может быть я буду его собирать, чтобы привести мысли в порядок или отвлечься, но не более того. Соревнование в механической скорости сборки? Non merci, уж лучше скворечники делать…
Ситуацию, как всегда, спасли мысли об автоматизации. После недолгого изучения я узнал рекогнисцировку. Для начала, число Бога уже давно найдено и равно 20. Правда задача сборки от этого не упрощается, т.к. использовать граф кратчайших путей для всех возможных конфигураций кубика не очень спортивно и немножко накладно по ресурсам. Алгоритм Бога предполагает под собой некое разумное количество использованной памяти, и в то же время обязан обеспечить минимально возможное число модификаций. Так вот, такого алгоритма еще нет. Есть ряд алгоритмов, позволяющих заметно ускорить сборку по сравнению с традиционными шаблонными методоми, но повторять кем-то уже проложенный (математически) путь мне показалось скучным. Если кому интересно, вот хороший анализ: http://mike.verdone.ca/media/rubiks.pdf Далее, есть традиционные шаблонные методы. Идея здесь в послойной сборке снизу вверх с использованием формул. Формула — последовательность модификаций Кубика, приводящая к таким-то целевым модификациям, и таким-то побочным. Соответственно, побочные модификации почти всегда падают на еще не собранные слои. Различаются шаблонные методы уровнем детализации шаблонов. Всякого рода спидкуберы знают все мыслимые шаблоны для большого количества частных случаев, что позволяет отыграть лишнюю 0.1 секунду с каждой модификации на соревнованиях. Пример, на что еще можно потратить жизнь.
Итак, я постепенно формировал для себя задачу. В итоге, формулируется она так: за кратчайшее реальное время необходимо написать решалку для Кубика Рубика.
Что мы знаем о Кубике? Число его состояний описывается как
(8! × 3^7) × (12! × 2^11)/2 = 43 252 003 274 489 856 000
.
Именно это число накладывает ограничения на использование графа кратчайших путей. Что мы знаем о его правилах? То что каждый конкретный элемент (боковой или угловой) должен стоять точно на своём месте. Что является точным местом? Для бокового элемента — это соотстветствие обоих его цветов цветам центральных элементов, для углового элемента — соответствие трёх центральных элементов трём цветам этого углового элемента.
Таким образом мы можем в любой момент времени просто ответить на вопрос — «стоит ли данный элемент на своём месте?». Второй аспект, который мы знаем — Кубик может быть собран послойно, при чём каждый слой собирается постепенно. А это значит… па-пара-парам! Нужна градиентная эвристика. Осталось лишь выбрать метод реализации. Алгебраические методы я не стал рассматривать, т.к. мне хотелось получить некое решение, легко обобщаемое на подобый класс задач. (То что получилось я могу не слишком сложно обобщить до 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
ссылка на оригинал статьи http://habrahabr.ru/post/260965/
Добавить комментарий