World of Warcraft Legion головоломки шаманов. Генетический алгоритм решения

Ave $USER!

Не так давно, вышло очередное дополнение World of Warcraft Legion. Первым делом я принялся прокачивать шамана и был приятно удивлен получив артифактное оружие в оплоте шаманов. Я забрел к Мастеру головоломок Ло и увидел то, что вы подумали - головоломку.

Передо мной был квадрат из огненных и водных тотемов 5 на 5, после того как кликаешь на тотем, он меняется на противоположный, например водный на огненный или огненный на водный и так же меняет сверху, снизу, слева и справа. Необходимо сделать так, что бы все тотемы стали водными. После первого клика я понял, что срочно нужно написать решение для этой головоломки.

Задача стояла следующая: Дана матрица размерности N на M, каждая ячейка матрицы содержит либо 0 либо 1. При изменении значения ячейки матрицы на противоположное, автоматически меняются на противоположные значения на соседних ячейках сверху, снизу, слева и справа. Найти последовательность изменений ячеек, что бы матрица состояла только из нулей.

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

Немного теории

Для написания алгритма нам понадобится ввести поняия генов, генотипа, фитнес функции, мутация, поколения и выживания поколения.

Гены

Геном будем называть значение ячейки матрицы, т.е. это либо 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);
   } );
}

Выживание

Селекция индивидов по приспособленности в результате которой, остается ограниченное число наиболее приспособленных. В нашем случае мы сортируем всех индивидов по убыванию значения фитнесс функции и оставляем первых N x M 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 );
}