Складання Кубика Рубіка генетичним алгоритмом онлайн без смс



У той час поки я збирався на ланч, мій ко-воркер Дейв гукнув до мене: «Хей, Алекс, а ти не хочеш займатися поліпшенням свого навичок програмування?». Я задумався. Це була цікава пропозиція, але я схилявся відповісти відмовою: «Зараз я займаюся развитем навичок говоріння на мовах, друже!». Гаразд, жартую. Ранок почався з того, що я дістався до пошти і взяв у руки копійчаний китайський Кубик, випадково замовлений на алі. До обіду я простудіював мануал складання і оновив м'язову пам'ять, а до вечора прийшло усвідомлення, що я награвся. Майбутнє кубика було ясним: він буде припадати пилом на полиці, раз або два в тиждень може бути я буду його збирати, щоб привести думки в порядок або відволіктися, але не більше того. Змагання в механічній швидкості збірки? 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>
<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.ua/cube/
Архів з кодом: http://misc.motogipsy.ua/cube/cube.zip
Код з collabedit: http://misc.motogipsy.ua/cube/index_net.html

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.