Игра InvaderZ генерирует врагов в стиле Space Invaders генетическим алгоритмом

Разработка игр Машинное обучение Дизайн игр
Иллюстрация: Smithsonian Magazine

Пользователь GitHub под ником victorqriberio показал свою версию классической аркады Space Invaders. Его вариант называется InvaderZ. В нем всё так же нужно отстреливать появляющихся вверху экрана пришельцев, но каждая волна «вторженцев» уникальна. Victorqriberio использовал генетический алгоритм, который изменяет форму каждого нового пришельца.

Генетический алгоритм — это алгоритм поиска, работающий как естественный отбор в природе. Алгоритм пользуется тремя основными функциями: отбор, скрещивание и формирование новых поколений. Применять генетический алгоритм можно не только и не столько на играх, но и для задач на графы и компоновки, при составлении расписаний, и т.д. Для генетического алгоритма нужно определить параметр успешности «особи». Если в живой природе это выживаемость и продолжение рода, то в случае с генетическими алгоритмами в программировании это может быть эффективность решения задачи.

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


Первый квадрат по горизонтали от одного «родителя», второй квадрат по горизонтали от второго «родителя»
Первый квадрат по горизонтали от первого «родителя», второй квадрат по горизонтали от первого «родителя»
Первый квадрат по вертикали от одного «родителя», второй квадрат по вертикали от второго «родителя»
Первый квадрат по вертикали от первого «родителя», второй квадрат по вертикали от первого «родителя»
Четные гены от первого родителя», нечетные — от второго
Нечетные гены от первого родителя», четные — от второго


Иллюстрация: Github

Заложен 10% шанс случайных изменений. При этом форма пришельца влияет на то, как он двигается по экрану. После семи волн отбор запускается по новой, а среди семи прошедших поколений сохраняются только лучшие пришельцы.

Игра сохраняет простоту управления Space Invaders: две кнопки движения и одна стрельбы. Игра запускается в браузере или на телефоне.

Еще одним примером использования генетического алгоритма в играх стала Evolution, созданная Keiwan. В этой игре нужно создавать существо из точек — суставов, соединенных костями. Кости соединяются между собой мышцами, которые приводят всю конструкцию в движение. Игрок может создавать любое существо на свой вкус с рядом ограничений: мышца соединяет только две кости, а две кости можно соединить только одной мышцей. Мышца в Evolution действует как биологический аналог: она ​​может как сокращаться, так и расширяться. При этом мышца прикладывает силы к костям в соответствующих точках соединения, что позволяет существу двигаться.

Игрок создает свое существо, а после дает ему задание — прыгать, бегать, перепрыгивать препятствия или взбираться на гору. Затем существо обучается пользоваться созданной пользователем конструкцией. Keiwan пояснил, что не стал встраивать в игру эволюцию самого существа, потому что это потребовало бы переписать большой кусок кода.


Поиграть в Evolution также можно в браузере, но для сохранения существ вам понадобится скачать и установить игру.

Пользователь Хабра JediPhilosopher нашел генетическому алгоритму еще одно применение . С помощью такого алгоритма он научил нейросеть строить круговые туристические маршруты по Санкт-Петербургу (в теории можно применить к любому городу). Он отобрал достопримечательности, присвоил им индекс интересности и задал такие параметры:


Не слишком короткий и не слишком длинный маршрут.
Максимальная суммарная интересность объектов.
Маршрут без пересечений.
Маршрут должен стремиться к форме круга.

В итоге JediPhilosopher научил алгоритм строить круговые, насыщенные достопримечательностями, маршруты по центру Петербурга.)
Теги:
Хабы: