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

_{Иллюстрация: Smithsonian Magazine ^[1]}

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

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

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

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

_{Иллюстрация: Github ^[3]}

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

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

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

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

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

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

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

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

Автор: Leonid_R

Источник ^[6]