- PVSM.RU - https://www.pvsm.ru -
Привет, Хабражитель!
Не так давно, вышло очередное дополнение World of Warcraft Legion. Первым делом я принялся прокачивать шамана. В оплоте шаманов я забрел к Мастеру головоломок Ло и увидел то, что вы подумали — головоломку.
Передо мной был квадрат из огненных и водных тотемов 5 на 5, после того как кликаешь на тотем, он меняется на противоположный, например водный на огненный или огненный на водный и так же меняет соседние тотемы сверху, снизу, слева и справа. Необходимо сделать так, что бы все тотемы стали водными. После первого клика я понял, что срочно нужно написать решение для этой классной головоломки.
Что из этого получилось, читай под катом.
Задача стояла следующая:
Дана матрица размерности N на M, каждая ячейка матрицы содержит либо 0
либо 1
. При изменении значения ячейки матрицы на противоположное, автоматически меняются на противоположные значения на соседних ячейках сверху, снизу, слева и справа.Найти последовательность изменений ячеек, что бы матрица состояла только из нулей.
Решение этой задачи весьма стандартное и скучное и я решил написать генетический алгоритм решения задачи.
UPD: Так как замечено недопонимание, то делаю акцент на том, что смысл не в решении задачи, а в написании генетического алгоритма поиска решения
Для написания алгритма нам понадобится ввести поняия генов, генотипа, фитнес функции, мутация, поколения и выживания поколения.
Геном будем называть значение ячейки матрицы, т.е. это либо 1
либо 0
Генотипом будем называть матрицу представленную в виде строки длинной L = N x M
, которая будет содержать последовательно объединенные строки матрицы, каждый символ строки — это ген
Пример
Для матрицы[ [0,0,0,0,0], [1,1,1,1,1], [0,0,0,0,0], [1,1,1,1,1], [0,0,0,0,0] ]
Генотипом будет строка
0000011111000001111100000
, гдеL = 25
Фитнесс функцией (Функцией приспособленности) назовем функцию, которая возвращает число от 0
до 1
, чем ближе значение к 1
тем лучше преспособленность индивида. Остается вопрос, что же считать приспособленностью индивида. Для простоты можем обойтись количеством нулевых генов в генотипе разделенное на длину генотипа
function fitness(genotype) {
return genotype.replace(/1/g,'').length / genotype.length;
}
Изменение одного гена в генотипе индивида. Т.к. по правилам игры меняются 5
ячеек матрицы (целевая и соседние), то одна мутация будет давать 5
новых индивидов.
const DIRECTIONS = [
{x: 0, y: 0},
{x: 1, y: 0},
{x:-1, y: 0},
{x: 0, y: 1},
{x: 0, y:-1}
];
function mutate(genotype) {
return DIRECTIONS.map( direction => {
const nextX = x + direction.x;
const nextY = y + direction.y;
return genotype.flip(nextX, nextY);
} );
}
Селекция индивидов по приспособленности в результате которой, остается ограниченное число наиболее приспособленных. В нашем случае мы сортируем всех индивидов по убыванию значения фитнесс функции и оставляем первых L x 8
(значение получено экспериментально)
const maxGenerationSize = 400; // 5 * 5 * 8
function surviving(populations) {
return populations.sort( (a, b) => {
return b.fitness - a.fitness;
}).slice(0, maxGenerationSize);
}
Множество индивидов оставшихся после "Выживания". Причем самый первый индивид поколения и будет решением, если его приспособленость равна единице
Можно заметить, что после мутации очень часто можно получить ранее известный геном либо геном, полученный меньшим количеством мутаций, но с такой же или лучшей приспособленностью. Что бы такого не происходило, создадим хэш-таблицу геномов, ключом которой будет сам геном, а значением, массив из ячеек мутаций. В случае если этот геном уже встречался и количество ячеек мутаций не превосходит уже встречавшейся, создаем из него покаление.
Также легко заметить, что мы меняем на всем поле либо 3
либо 5
ячеек, т.е. фитнесс функция возвращает 1
только после значений L - 3
и L - 5
. Для них, можно возращать значения фтнесс функции 0.999
, что бы увеличить их приспособленность
Пример
Для марицы5x5
значение фитнесс функции1
будет при наличии всех25
нулей в геноме, а им предшедствуют только либо20
нулей либо22
Весь цикл поиска решения можно представить в виде следующего кода
while ( generation++ < maxGenerationsCount && populations[0].fitness !== 1 ) {
populations = mutating( populations );
populations = surviving( populations );
}
Вооружившись Webpack, React-Redux и, Material-UI за пару часов получилось, вот такое простенькое веб приложение:
Вычисления происходят на стороне Web Worker в файле breeder.js
, что бы снять нагрузку с UI.
Автор: 3axap4eHko
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/javascript/184335
Ссылки в тексте:
[1] Ссылка на задачу в WiKi: https://en.wikipedia.org/wiki/Lights_Out_(game)
[2] Посмотреть на готовое решние можно здесь: https://potofcode.com/code/game-wow-legion-shaman-puzzles/
[3] Исходники на GitHub: https://github.com/potofcode/game-wow-legion-shaman-puzzles
[4] Все замеченные и не замеченные ошибки сюда: https://habrahabr.ru/conversations/3axap4ehko/
[5] Источник: https://habrahabr.ru/post/309286/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.