06.09.2016 21:31
3axap4eHko 26 25800 Источник

Привет, Хабражитель!
Не так давно, вышло очередное дополнение 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.


Поделиться с друзьями
-->

Комментарии (26)


  1. 1vanK
    07.09.2016 02:11
    #9792442
    +4

    Не играл в ВОВ, но если я правильно понял, это та же головоломка, что в братьях пилотах на открытие сейфа. Можно одно состояние представить 1, второе ноль и рассматривать четность КРЕСТОВ. То есть все поле должно быть либо четным либо нечетным, то ищем например нечетные кресты (сумма всех элементов нечетные) и меняем его. И задача решается за минимальное число шагов.

    p.s. о чем речь идет в статье я не совсем понял, жесть какая-то :)


    1. 1vanK
      07.09.2016 02:19
      #9792448
      +1

      Нет, походу тут немного другая головоломка. В братьях пилотах вся строка и весь столбец менялись на противоположные.


    1. TriBar
      08.09.2016 20:42
      #9796258

      Помню та головоломка имела занятное решение «в лоб», может именно его вы и описали — достаточно было записать состояние всех, например, вертикальных переключателей, а потом 2 раза прощелкать по ним по порядку, не задумываясь что происходит на поле, и все открывалось. Не знаю важен ли там порядок, но такое решение помогло наконец уровень пройти, ибо детских мозгов на решение не хватало…


  1. Nakilon
    07.09.2016 02:15
    #9792446
    -6

    Школьный портал habrahabr.ru не перестает радовать оригинальными исследованиями…

    https://en.wikipedia.org/wiki/Lights_Out_(game)


    1. 3axap4eHko
      07.09.2016 02:22
      #9792450
      +3

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


    1. QtRoS
      07.09.2016 08:23
      #9792546

      Присоединяюсь к комментарию — это классическая игра, есть множество реализаций и алгоритмов решения.
      Генетический алгоритм — это хорошо, но всему свой инструмент. Можно, например, с помощью машинного обучения определять четность числа, но… зачем?


  1. napa3um
    07.09.2016 02:23
    #9792454
    +12

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


    1. Semenar
      07.09.2016 09:32
      #9792680
      +1

      При этом получившееся решение, в отличие от полного перебора, теоретически может ещё и не закончиться: например, если среди существ останутся только те, у которых недостаёт 3 или 5 нулей, при этом из них нет решения в один ход. Тогда любая мутация приведёт к тому, что фитнесс-функция окажется не больше (а можно выбрать позиции так, что и меньше) и потомство отправится в утиль.


      1. napa3um
        07.09.2016 09:48
        #9792718
        +1

        Да, там несколько таких «случайных эвристик», по счастливой случайности укладывающихся в решение. Например, количество «поколений» должно быть больше количества ходов в решении. Код кажется шуткой на тему того, насколько тщательно можно замаскировать один алгоритм под другой.


    1. 3axap4eHko
      07.09.2016 16:12
      #9793644
      -2

      С таким успехо даже алгоритм А-звезда, можно назвать поиском в глубину с эвристикой, но это принципиально и концептуально разные алгоритмы, причем тут нет графа, мы просто мутируем матрицу в определенной последовательности. Была идею сделать это рандомно, но как-то руки не дошли


      1. napa3um
        07.09.2016 16:31
        #9793684
        +1

        «С таким успехо даже алгоритм А-звезда, можно назвать поиском в глубину с эвристикой» — именно этим он и является. А ваше решение вообще никакого отношения к генетическим алгоритмам не имеет, вы просто некоторым объектам в вашем коде дали «генетические» названия, а потом добавили эвристику, отрезающую от дерева обхода фактически случайные ветки (необоснованные задачей, но обоснованные заблуждением о том, что что ветки дерева состояний игрового поля — это особи). И фтинесс-функция у вас не несёт никакого смысла (всё потому же — особей-решений у вас нет, есть только варианты состояния поля). ЭТО НЕ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ. Постарайтесь принять факт своего заблуждения, это же не катастрофа.


    1. fireSparrow
      07.09.2016 17:55
      #9793896
      +2

      Вот та же мысль возникла при чтении.
      В генетическом алгоритме мы меняем и сравниваем те объекты, для которых нужно найти оптимальное состояние. И это состояние и является искомым само по себе, какими мутациями алгоритм к нему пришёл — не принципиально.
      А здесь искомое состояние уже известно — это матрица из нулей, а нас интересует именно то, как к ней прийти.

      Вообще, попытка применения ГА к данной задаче вызывает ассоциацию с известным рисунком про троллейбус из буханки хлеба.


    1. s-y
      07.09.2016 17:56
      #9793904
      +1

      Вот и мне так кажется, самое интересное на самом деле сравнить затраты, и скорость на поиск с помощью этого генетеческого алгоритма и обычного перебора, чтоб потом долго не рассказывать почему в таких задачах он не нужен. А то скоро станет трендом так решать задачи с помощью модного инструмента.


  1. ThePretender
    07.09.2016 08:25
    #9792550
    +6

    Я просто оставлю это здесь:
    image


  1. Semenar
    07.09.2016 09:08
    #9792608
    +1

    А почему мы меняем только 3 или 5 ячеек? При выборе крайней, не являющейся угловой, мы 4 поменяем же.


  1. Sild
    07.09.2016 10:39
    #9792842

    Есть подозрение, что из-за ограничения на 8 экземпляров поколения алгоритм будет сходиться не всегда.
    А иначе будет полный перебор.


    1. Semenar
      07.09.2016 10:57
      #9792886

      Там же не 8, а количество клеток, умноженное на 8, то есть, 200. Автор немного обсчитался и указал 400, кажется.


      1. Sild
        07.09.2016 11:40
        #9792998

        Это все моя невнимательность.

        Но 200 это хоть и уменьшает вероятность проблемы, в общем случае её не решает


  1. napa3um
    07.09.2016 11:49
    #9793026
    +4

    Почему статья до сих пор существует? Либо удалите её, либо исправьте заголовок (и удалите все упоминания в тексте всяких «генов» и «мутаций», не имеющих к брутфорсу никакого отношения), не вводите неискушённых читателей в заблуждение относительно генетических алгоритмов.


  1. bromzh
    07.09.2016 12:52
    #9793156

    В емаксе есть такая игра. И "решатель" тоже присутствует.


    Картинка

    image
    image


  1. augur
    07.09.2016 16:05
    #9793624
    +1

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


    1. napa3um
      07.09.2016 16:37
      #9793696
      +1

      > Результатом работы генетического алгоритма будет являться решение, подходящее для любого набора входных данных
      Не обязательно генетическими алгоритмами ищется универсальное решение, но в данном случае нет никакого генетического алгоритма вообще.


  1. feogabber
    07.09.2016 17:56
    #9793906

    Я так понял — это алгоритм перебора.


  1. timapple
    07.09.2016 17:56
    #9793908
    +1

    А теперь объясните, как вы в итоге получаете решение в виде последовательности ходов? Сдается мне, что «генетический» подход применен неверно.
    Я бы в качестве гена взял операцию клика на тотем в определенной позиции (итого 25 генов). Тогда генотип (хромосома) кодирует последовательность ходов. Для оценки берем начальное поле, применяем последовательность и смотрим что получилось. Как-то так.


  1. Ghool
    07.09.2016 20:07
    #9794154

    А почему у вас Y сверху вниз а не снизу вверх?
    за тему спасибо.


  1. sovsem1234
    08.09.2016 12:52
    #9795238
    +1

    Решал такую задачу на scrath, там можно поиграть и посмотреть исходники
    В ней не важна последовательность ходов, а только сами ходы. Правда мой алгоритм основывался на решении системы линейных уравнений, (просто, надежно, быстро)