Уровень подготовки:
Если за плечами уже есть змейка и тетрис - читаем смело. Если нет, ничего страшного, расширяем кругозор.
Также желательны базовые знание LUA для понимания кода.
Итак поехали!
Теоретическая часть.
Наверняка многие уже не раз слышали про генетические алгоритмы и с чем их едят.
Что далеко ходить, у нас даже есть небольшая статья в разделе термины Генетический алгоритм.
Но сегодня разговор не о теоретической, а практической стороне вопроса, как все это безобразие можно пустить в дело.
Для начала попробую простыми словами рассказать, что же из себя представляет этот хитрый алгоритм.
Если максимально упрощенно генетический алгоритм - ничто иное, как подбор коэффициентов для решения уравнения.
Вся соль кроется в способе подбора этих параметров, тут то мы и вспоминаем про название алгоритма.
Представим искомые коэффициенты как гены и вспомним, как работает эволюция.
Еще в далекие времена Дарвин говорил про естественный отбор, что всегда выживает самый приспособленный. Вот так же и у нас.
алгоритм до неприличия прост:
1-создаем новое поколение популяции
2-отбираем самых приспособленных, остальных удаляем
3-из оставшихся выводим(селекционируем) новое поколение и снова пункт 2
И все это происходит до тех пор, поке не будет найдено решение задачи.
Простой пример: уравнение X + Y = 100, здесь X и Y можно представить как гены.
Создаем 4 особи со случайным набором ген:
( X = 2, Y = 2 )
( X = 20, Y = 2 )
( X = 30, Y = 50 )
( X = 22, Y = 44 )
Проверяем приспособленность, для этого считаем насколько переменные приближают нас к решению уравнения:
| 2 + 2 | / 100 = 0.04
| 20 + 2 | / 100 = 0.22
| 30 + 50 | / 100 = 0.8
| 22 + 44 | / 100 = 0.66
На основе лучшей пары создаем следующее поколение, также добавляем в него и лучших особей из предыдущего.
У нас крайне простой случай, у каждой особи всего по 2 гена.
Скрещиваем ( X1, Y1 ) и ( X2, Y2 ) и получаем в итоге ( X1, Y2 ) и ( X2, Y1 )
новое поколение:
( X = 30, Y = 50 ) родитель 1
( X = 22, Y = 44 ) родитель 2
( X = 30, Y = 44) потомок 1
( X = 22, Y = 50) потомок 2
И казалось бы, вот уже мы скачем верхом на эволюционном процессе и все задачи нам по плечу, но не все так просто.
На данном примере видно, что уже через 1 итерацию - новых генов взять неоткуда, а из старых уже найдена лучшая комбинация.
Решения достигнуто не было, и система работает без изменений.
Тут то нам на помощь приходят мутации, они не такие красивые как скажем в сталкере, но зато очень даже эффективные.
Суть мутации проста: добавить новых генов при формировании следующей популяции.
Будь это совершенно новая особь или изменение случайных генов потомка, уже детали реализации.
Но, как говорится и это еще не все! При большом количестве генов система порой приходит к равновесию, так и не найдя решения.
И даже мутации из за малого удельного веса не спасают ситуацию.
В качестве аналогии можно привести новичка, пришедшего в большую компанию.
У него горят глаза, полно энергии, идей, инновационные технологии.
Он кричит: “Я знаю как правильно, как нам улучшить компанию, достигнуть успеха, даже есть опыт”
А с другой стороны - бывалые дяди, которые всю жизнь тут трудятся и знают, как делать дела.
У них связи, авторитет, они сидят на откатах и не хотят ничего менять.
И они ему говорят: “Ты кто такой ваще, ты нам мать что ли, че учить то нас вздумал, уйди,
не мешай работать” А дальше система либо его ломает, либо он уходит.
И чтобы эволюция не буксовала на месте - нужны встряски. Как с динозаврами например.
Как только происходит застой ( появился стабильный генотип ), всей системе нужна встряска.
Удаление большей части популяции или даже полностью всей и создание недостающих особей со случайным набором генов.
Опять же аналогия с компанией.
Большие компании поделили рынок поровну и всем достается понемногу, рынок не развивается.
И тут приходят стартапы, состоящие из тех самых молодчиков с горящими глазами.
Конечно только один из ста в итоге останется на плаву, а остальные потонут, но тот кто сможет - сорвет куш.
Итак ребятишки, давайте подведем итог, что же сегодня мы узнали.
Для работы генетического алгоритма нужны следующие вещи:
-описать решение задачи набором параметров( генов ) назовем это описание особью.
-определить критерии успешности особи( мера правильности решения задачи )
-провести эволюционный отбор при помощи 3х методов: скрещивание, мутация и встряска.
Практическая часть.
Формулы и циферки эт конечно хорошо, но как говорится ближе к телу.
Есть задача, с которой часто встречаются, как разработчики, так и игроки, а именно расчет билда.
Для простоты примем, что игра пошаговая.
Есть монстр, у него нет хп и мы будем измерять максимально урон, который герой может нанести пока не погибнет.
Каждые 3 хода монстр атакует игрока, с 20% шансом крита.
Есть игрок со следующими параметрами: шкалы здоровья и силы, реген здоровья и силы, атака и защита.
Также у игрока есть экипировка, которая влияет на параметры.
В качестве генов здесь будет выступать экипировка, что и в каком слоте находится у героя.
руки:
меч1( атака 5, требует силы 5 )
меч2( атака 4, требует силы 3 )
меч3( атака 8, требует силы 10 )
щит1( защита 3, требует силы 2 )
щит2( защита 5, требует силы 3 )
туловище:
доспех1( защита 5, атака -2 )
доспех2( защита 3, атака 0 )
доспех3( защита 1, реген здоровья 1 )
голова:
шлем( защита 2 )
шапка силы( реген силы 1 )
шапка здоровья( реген здоровья 1 )
макс здоровье 500
макс сила 100
реген здоровья 0
реген силы 5
атака 1
защита 1
Монстр атакует за раз на 25 единиц, во время крита на 45, шанс крита 20%.
Игрок атакует каждый ход, когда хватает силы.
Кодить все это дело будем на луа. Почему, да это быстро и весело :)
Для начала пропишем параметры персонажа, монстра и экипировки.
+ Входные данные
Создаем таблицу и заполняем случайными билдами. Размер популяции был выбран в 16 особей.
Далее вся популяция проходит проверку боем и сортируется по нанесенному урону.
Переходим к селекции. Гены лучшей половины популяции переходят в следующее поколение.
После чего начинаем скрещивать успешную половину с теми, кто отбор так и не прошел, в этот же момент может происходить мутация.
В итоге мы получаем количество особей, что было в начале. И опять бой, селекция, бой…
Казалось бы все этом может длиться вечно, но на небольшом количестве генов лучшая комбинация находится довольно быстро,
поэтому у нас стоит ограничение в 50 циклов. После чего можно подводить итоги.
Для запуска всего этого мракобесия осталось только взвести рандомизатор по текущему времени и запустить симуляцию.
math.randomseed( os.time() )
GenTest()
Сохраняем , запускаем, затаив дыхание ждем результата.
И вуаля! Видим, что самый хороший билд это: два вторых меча, доспех номер 3 и шапка жизни :)
Запустив симуляцию еще несколько раз подряд - видно что, этот билд является стабильным, но все же иногда есть небольшие отклонения.
Это получается за счет небольшого количества поколений и рандома связанного с критическими атаками монстра.
При увеличении количества поколений до 500 - билд получается всегда один и тот же.
Поэтому для балансировки важно правильно подобрать количество итераций.
Вот сводный график 3х запусков моделирования. Зависимость нанесенного урона от поколения особей.
Высокий старт всех случаев обусловлен тем, что это результаты лучшей особи первого поколения.
Основная часть эволюции происходит в течении первых 20 циклов, после уже видна стабилизация.
Снизив количество поколений до 10, можно увидеть и другие жизнеспособные варианты.
Что интересно, в них ни разу не было щитов, а значит они нуждаются в ребалансе.
Та же при помощи этого алгоритма можно определить среднее время жизни монстра,
а если немного переделать, то появится возможность сталкивать билды друг с другом.
Выводы.
Подводя итог, у нас получилось за небольшое время сделать довольно гибкий инструмент для балансировки игры,
который поможет проверить, работают ли все как задумано, или есть места которые стоит поправить.
Правда в примере не был использован механизм встряски, из за малого количества генов, его эффект был бы просто незаметен.
Надеюсь еще расскажу вам об этом, но это уже будет совсем другая история.
А пока всего хорошего и спасибо за рыбу :)
20 марта 2018
(Обновление: 31 дек 2018)
Комментарии [63]