Решаем головоломки шаманов в World of Warcraft генетическим алгоритмом

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


    Поделиться публикацией

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

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

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

      p.s. о чем речь идет в статье я не совсем понял, жесть какая-то :)
        +1
        Нет, походу тут немного другая головоломка. В братьях пилотах вся строка и весь столбец менялись на противоположные.
          0
          Помню та головоломка имела занятное решение «в лоб», может именно его вы и описали — достаточно было записать состояние всех, например, вертикальных переключателей, а потом 2 раза прощелкать по ним по порядку, не задумываясь что происходит на поле, и все открывалось. Не знаю важен ли там порядок, но такое решение помогло наконец уровень пройти, ибо детских мозгов на решение не хватало…
          –6
          Школьный портал habrahabr.ru не перестает радовать оригинальными исследованиями…

          https://en.wikipedia.org/wiki/Lights_Out_(game)
            +3
            Вы, уважаемый, читать не умеете. Суть не в том, что бы решить задачу, а в написании генетического алгоритма поиска решения. Но за ссылку спасибо, добавлю в статью
              0
              Присоединяюсь к комментарию — это классическая игра, есть множество реализаций и алгоритмов решения.
              Генетический алгоритм — это хорошо, но всему свой инструмент. Можно, например, с помощью машинного обучения определять четность числа, но… зачем?
              +12
              Похоже, у вас вместо генетического алгоритма получился поиск в глубину («генотипы» у вас кодируют не решения головоломки, а перебираемые состояния игрового поля). Это просто полный перебор с небольшой эвристикой.
                +1
                При этом получившееся решение, в отличие от полного перебора, теоретически может ещё и не закончиться: например, если среди существ останутся только те, у которых недостаёт 3 или 5 нулей, при этом из них нет решения в один ход. Тогда любая мутация приведёт к тому, что фитнесс-функция окажется не больше (а можно выбрать позиции так, что и меньше) и потомство отправится в утиль.
                  +1
                  Да, там несколько таких «случайных эвристик», по счастливой случайности укладывающихся в решение. Например, количество «поколений» должно быть больше количества ходов в решении. Код кажется шуткой на тему того, насколько тщательно можно замаскировать один алгоритм под другой.
                  –2
                  С таким успехо даже алгоритм А-звезда, можно назвать поиском в глубину с эвристикой, но это принципиально и концептуально разные алгоритмы, причем тут нет графа, мы просто мутируем матрицу в определенной последовательности. Была идею сделать это рандомно, но как-то руки не дошли
                    +1
                    «С таким успехо даже алгоритм А-звезда, можно назвать поиском в глубину с эвристикой» — именно этим он и является. А ваше решение вообще никакого отношения к генетическим алгоритмам не имеет, вы просто некоторым объектам в вашем коде дали «генетические» названия, а потом добавили эвристику, отрезающую от дерева обхода фактически случайные ветки (необоснованные задачей, но обоснованные заблуждением о том, что что ветки дерева состояний игрового поля — это особи). И фтинесс-функция у вас не несёт никакого смысла (всё потому же — особей-решений у вас нет, есть только варианты состояния поля). ЭТО НЕ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ. Постарайтесь принять факт своего заблуждения, это же не катастрофа.
                    +2
                    Вот та же мысль возникла при чтении.
                    В генетическом алгоритме мы меняем и сравниваем те объекты, для которых нужно найти оптимальное состояние. И это состояние и является искомым само по себе, какими мутациями алгоритм к нему пришёл — не принципиально.
                    А здесь искомое состояние уже известно — это матрица из нулей, а нас интересует именно то, как к ней прийти.

                    Вообще, попытка применения ГА к данной задаче вызывает ассоциацию с известным рисунком про троллейбус из буханки хлеба.
                      +1
                      Вот и мне так кажется, самое интересное на самом деле сравнить затраты, и скорость на поиск с помощью этого генетеческого алгоритма и обычного перебора, чтоб потом долго не рассказывать почему в таких задачах он не нужен. А то скоро станет трендом так решать задачи с помощью модного инструмента.
                      +6
                      Я просто оставлю это здесь:
                      image
                        +1
                        А почему мы меняем только 3 или 5 ячеек? При выборе крайней, не являющейся угловой, мы 4 поменяем же.
                          0
                          Есть подозрение, что из-за ограничения на 8 экземпляров поколения алгоритм будет сходиться не всегда.
                          А иначе будет полный перебор.
                            0
                            Там же не 8, а количество клеток, умноженное на 8, то есть, 200. Автор немного обсчитался и указал 400, кажется.
                              0
                              Это все моя невнимательность.

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

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


                              Картинка

                              image
                              image

                                +1

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

                                  +1
                                  > Результатом работы генетического алгоритма будет являться решение, подходящее для любого набора входных данных
                                  Не обязательно генетическими алгоритмами ищется универсальное решение, но в данном случае нет никакого генетического алгоритма вообще.
                                  0
                                  Я так понял — это алгоритм перебора.
                                    +1
                                    А теперь объясните, как вы в итоге получаете решение в виде последовательности ходов? Сдается мне, что «генетический» подход применен неверно.
                                    Я бы в качестве гена взял операцию клика на тотем в определенной позиции (итого 25 генов). Тогда генотип (хромосома) кодирует последовательность ходов. Для оценки берем начальное поле, применяем последовательность и смотрим что получилось. Как-то так.
                                      0
                                      А почему у вас Y сверху вниз а не снизу вверх?
                                      за тему спасибо.
                                        +1
                                        Решал такую задачу на scrath, там можно поиграть и посмотреть исходники
                                        В ней не важна последовательность ходов, а только сами ходы. Правда мой алгоритм основывался на решении системы линейных уравнений, (просто, надежно, быстро)

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                        Самое читаемое