Муки виртуальной эволюции: как нейросети с генетическим алгоритмом тренируются на компьютерных играх

Первые шаги логотипа TJ, выживание наиболее приспособленных «Змеек» и тысячи поколений водопроводчика Марио.

«Будущее искусственного интеллекта начинается с игры „Космические захватчики”», — писал в 2015 году журнал Wired. Статья рассказывала о принадлежащей Google компании DeepMind, которая натренировала свои нейросети проходить 49 старых видеоигр. Материал вышел всего за несколько месяцев до того, как программа AlphaGo, разработанная DeepMind, стала первым искусственным интеллектом, победившим профессионала в игре го.

С тех пор нейросети освоили множество сложных задач — от распознавания изображений до определения авторства Шекспира, — но «Космические захватчики» не ушли в прошлое. Обучение алгоритмов простым играм стало широко распространённым упражнением среди программистов. К тому же, это отличный образовательный ресурс. Объяснить принципы машинного обучения на примере нейросети, играющей в «Змейку», проще, чем с помощью научных статей и графиков.

В этом материале я расскажу про одну разновидность программ — нейросети с генетическим алгоритмом. Их обучение происходит благодаря процессу, схожему с эволюцией. Тысячи версий соревнуются друг с другом, лучшие выживают и дают потомство, дети наследуют удачные черты родителей, и игра начинается снова. Повторение этого цикла позволяет не только проходить Flappy Bird, «Змейку» и Super Mario World, но и проводить наглядные эксперименты с эволюцией искусственных существ.

Сам по себе генетический алгоритм — достаточно сложный инструмент для решения задач оптимизации и моделирования. Но любительские нейросети на основе этой идеи гораздо проще. Для их понимания не требуется никаких специальных знаний. Мы начнём с сетей, количество узлов которых можно пересчитать на пальцах, затем перейдём к примерам с тысячами связей, а в конце познакомимся с масштабными симуляторами эволюции. И да: я действительно превратил логотип TJ в существо из костей и мышц, которое научилось двигаться. Но обо всём по порядку.

Рассмотрим простейшую нейросеть с генетической эволюцией, которую создал программист Срджан Суснич для игры Flappy Bird.

Система состоит из девяти узлов, или нейронов, соединённых линиями. Каждому нейрону и каждой линии соответствует число от нуля до единицы. Чем больше вес связи, тем выше шанс возбуждения следующей клетки. Нейроны разделены на три слоя: входной, скрытый и выходной. На входе программа получает два числа: расстояние до ближайшей трубы по горизонтали и расстояние до отверстия по вертикали. На выходе остаётся одно число. Если оно больше 0.5, птица взлетает, если меньше — падает.

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

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

В начале симуляции программист выбирает случайные числа для нейронов и их связей. На этом его контакт с системой заканчивается. Далее нейросеть работает на автопилоте.

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

Связи — это «генотип» наших птиц, а органы восприятия, кора мозга и конечности — «фенотип», то есть признаки, зависящие от среды. В течение жизни организма его гены не меняются. Так же и с птицами: пока поколение живёт, веса связей остаются неизменными, меняются только потенциалы нейронов.

Что происходит между поколениями? Здесь в игру вступает генетический алгоритм. Если бы лучшие птицы просто клонировались, приспособленность оставалась бы на одном уровне. На помощь приходят идеи из биологии: рекомбинация и мутация генов. Во-первых, программа перемешивает гены лучших особей: одни веса связей достаются ребёнку от мамы, другие от папы. Во-вторых, программа вводит случайные изменения в каждом из десяти отпрысков.

Этого оказывается достаточно, чтобы нейросеть стала мастером Flappy Bird. Уже в третьем поколении лучшей птице удаётся преодолеть четыре трубы, в десятом — восемь, в 22-м — 41, в 72-м — 168, а в следующем 73-м рождается чемпион. Суснич прослеживает его полёт до 448-й щели и прерывает симуляцию.

Успех птицы-рекордсмена оплачен сотнями «жертв»: как минимум 720 её предков (по десять в 72-х поколениях) глупо вреза́лись в трубы, расшибались об землю или вылетали за экран, где их ждала смерть от удушья. Слепой процесс «нашаривания» адаптации особенно заметен по первым поколениям, чей геном подобран наугад: 9 из 10 «Адамов» и «Ев» не в силах преодолеть даже первую щель. Они понятия не имеют о том, что эволюционная гонка уже началась.

Flappy Bird — относительно простая игра для машинного обучения. Что насчёт более сложных задач?

В 2016 году Самуэль Арцт научил нейросеть с генетической эволюцией проходить примитивные гонки. Его сеть состоит из четырёх слоёв. В первом слое пять нейронов: оценивается расстояние до стены в пяти направлениях (машинки смотрят влево, вперёд, вправо и под 45° в две стороны). В скрытых слоях четыре и три нейрона. На выходе — два варианта: повернуть влево или повернуть вправо. Скорость машин не меняется.

На схемах нейросети Арцт помечает связи зелёным и красным цветом в зависимости от того, хорошо они проводят сигнал или плохо. Толщина связи пропорциональна её весу.

В каждом поколении 20 машин, из них выживает две. Как и у Суснича, происходит рекомбинация и мутация генов. При этом меняется цвет и толщина линий. Опять же, в первом поколении геном выбирается наугад. Трассу Арцт построил не самую сложную, и к пятнадцатому поколению машины справились с задачей. Но и нейросеть для этого пришлось соорудить побольше, чем у Суснича: 15 узлов против 9.

Ещё одна игра, которую часто используют для тестирования нейросетей, — это «Змейка». Наглядный эксперимент провёл в 2018 году программист из США Грир Вио. Архитектура у него выглядит солидно: 24 входных нейрона, два скрытых слоя с 18 нейронами и 4 выходных нейрона. Связи также помечены в зависимости от того, положительные они или отрицательные, только вместо зелёного цвета используется синий.

У змейки три «органа восприятия», направленных в восемь сторон. Она отдельно оценивает расстояние до стены, до еды и до собственного хвоста (что-то вроде эхолокации, обоняния и проприоцепции, то есть ощущения положения частей своего тела). На выходе — четыре варианта поведения: повернуть в одном из четырёх направлений. Если птицам Суснича нужно было принимать во внимание всего два фактора, а машинам Арцта пять, змейкам Грира Вио — уже 24. Они вынуждены учитывать опасность врезаться не только в стены, но и в самих себя, а также искать путь к еде.

Сложность задачи требует увеличения популяции. В каждом поколении в террариум запускается 2000 змей. Из них выживают только две. Они дают потомство из 2000 детей, и всё начинается по новой. Что касается функции приспособленности, здесь возникла проблема: некоторые змейки выживали бесконечно долго благодаря тому, что ходили по кругу. Тогда программист ограничил количество ходов, которые есть у змеек. На старте они получали 200 бесплатных ходов (можно считать, родители заплатили за их обучение), затем ещё 100 ходов добавлялось за каждую съеденную точку.

Первые змейки совершенно не понимают, что от них требуется, но обучение происходит довольно быстро. Уже во втором поколении лучшая особь съедает пять точек. Затем следует «эволюционное плато»: 6 поколений остаются на одном уровне. В девятом поколении происходит прорыв: 15 точек и первые зачатки «стратегии» (змейка ходит кругами по часовой стрелке). Наилучшего результата добивается особь в тридцатом поколении: 140 точек.

Далее обучение оказывается невозможным: из-за особенностей модели нейросеть предпочитает правые повороты левым. Как объясняет автор проекта в комментариях, это эволюционная случайность. В других симуляциях ситуация была обратной. Это можно сравнить с превратностями человеческой эволюции: например, 10 пальцев на руках и, как следствие, популярность десятичной системы счисления — во многом, результат случайности.

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

Обширную работу в этой области провёл автор YouTube-канала Code Bullet. О нём мы знаем только то, что его зовут Эван и он из Австралии. В собственном проекте Эван использовал Q-обучение, разновидность обучения с подкреплением. Змейку по имени Эдриан программист снабдил входным слоем на 400 нейронов: она видела по отдельности все пиксели вокруг своей головы в квадрате 20 на 20. Алгоритм тренировался на протяжении 40 тысяч игр и достиг максимального результата примерно в 120 точек. С небольшими усовершенствованиями Эван поднял планку до 200. Для поля 40 на 40 это немного: 12,5% от идеала (максимальная длина была бы 1600).

Code Bullet также не нашёл человека, заставившего нейросеть обучиться проходить «Змейку» на уровне лучших игроков.

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

Code Bullet — многостаночник цифровой эволюции. За три года существования канала он обучил нейросети с генетическим алгоритмом играть в бильярд, «Астероиды», «Пэкмэна», Flappy Bird, Hill Climb Racing и в динозавра, который появляется в браузере Chrome, когда отсутствует доступ к интернету. Иногда программист добавляет забавные детали: если в реальной эволюции предки передают потомкам цвет глаз, в одной из симуляций Эвана наследуется цвет рубашки.

Во всех примерах, рассмотренных до сих пор, авторы экспериментов создавали собственные копии простых игр. Программы как бы обучались изнутри симуляции. В 2015 году автор YouTube-канала SethBling Сет Хендриксон пошёл другим путём. Он взял игру Super Mario World и прикрутил к ней нейросеть с генетической эволюцией. В распоряжении алгоритма MarI/O были те же средства, что и у обычного геймера: он «видел» пиксели на экране и мог «нажимать» на восемь кнопок, как на старом геймпаде.

Входной слой в архитектуре Хендриксона — это квадратный массив из 144 пикселей. Они представляют собой упрощённую схему уровня. Каждый пиксель — это нейрон. Он может принимать три значения: пустое место, белая точка, обозначающая землю, и чёрная точка, обозначающая движущиеся предметы — врагов и бонусы. Скрытый слой разбросан по всему экрану: пиксели зажигаются в момент активации. Иногда связи минуют скрытый слой: программа видит блок на экране и нажимает «налево».

Ещё одна особенность подхода Сета: различные виды эволюционируют отдельно. Эту идею он заимствовал у исследователей из Техасского университета в Остине Кеннета Стэнли и Ристо Микулайнена, которые в 2002 году написали статью о нейроэволюции. Разделение на виды позволяет не потерять удачные наработки. Если один Марио научился перепрыгивать врагов, а другой — проходить под ними, когда они сами прыгают, эти две стратегии выживания эволюционируют параллельно, пока не окажется, что одна всё-таки лучше.

MarI/O прошла уровень в 34-м поколении. На этом Хендриксон закончил симуляцию. Позже он выпустил продолжение, в котором натренировал свою систему проходить первый уровень в Super Mario Bros, но алгоритм застрял на втором. Зато программа обнаружила глитч — во всяком случае, для самого программиста это был сюрприз. SethBling предположил, что нейросеть с таким фукнционалом может быть полезна для поиска багов в играх.

Для генетических алгоритмов можно создавать оригинальные игры. Самый интересный пример — это симулятор эволюции разработчика под ником Кейван. Приложение появилось в 2017 году и бесплатно доступно онлайн.

В начале игры пользователь создаёт существо из суставов, костей и мышц. Затем нажимает кнопку «Evolve» и следит за тем, как его творение делает первые шаги. Организму можно поставить одну из четырёх задач: научиться ходить, прыгать вверх, прыгать через препятствия или забираться по лестнице. Также можно выбрать размер популяции в каждом поколении, длительность его жизни и скорость мутаций.

Попробуем создать существо, вдохновлённое TJournal.

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

Как и в случае с нейросетями для «Flappy Bird» и «Змейки», первые поколения организмов ведут себя хаотически. Вопрос в том, достаточно ли у них сложная архитектура, чтобы обучиться навыку. Если перспектив эволюции никаких, игрок возвращается к чертёжной доске.

Вторая версия чудища выглядела более костисто и мускулисто:

К моему большому удивлению, на этот раз логотип TJ смог эволюционировать. Он нашёл собственный способ передвижения: ползком.

К тринадцатому поколению TJ-гусеница нащупала полезную инновацию: она научилась сильно отталкиваться хвостом и подпрыгивать. Также я включил функцию, которая отмечала голубым расслабленные мышцы, красным — сокращающиеся. У меня получился довольно симпатичный гибрид кузнечика и акулы-молота.

В настройках игры можно посмотреть на реальную нейросеть, которая управляет существом. Входной и выходной слои здесь изображены не полностью: должно быть примерно 20 нейронов на выходе — по количеству мышц, — и около сотни на входе. На своём сайте Кейван поясняет, что нейроны входного слоя содержат информацию о позиции, высоте и скорости частей животного, но не говорит, сколько их конкретно.

Количество слоёв можно поменять, наравне со скоростью мутаций и многими другими параметрами — здесь открыт простор для экспериментов.

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

Странно осознавать, что в некоторых виртуальных экосистемах логотип TJ оказался бы более приспособленным, чем Homo sapiens, и привёл бы к вымиранию людей.

В завершение рассмотрим эксперимент программиста из Нижнего Новгорода Михаила Царькова. Он выкладывает видео под ником foo52ru. Царьков взял обычную «Змейку» и заставил игроков напрямую соревноваться друг с другом за ограниченные ресурсы.

В первом видео генетической эволюции ещё нет. Царьков создал змеек с достаточно сложным мозгом (240 входов, 4 выхода, без скрытых слоёв) и натренировал их вручную: нейросеть следила за игрой программиста и корректировала веса связей. Царьков опробовал две тактики тренировки, затем столкнул два получившихся алгоритма. От каждого на поле выходило по три клона.

Интересное начиналось во втором видео. Автор создал виртуальную чашку Петри и запустил в неё генетически запрограммированных цифровых бактерий. Змейки, в основе которых лежала всё та же нейросеть, могли умереть от столкновения или от недостатка энергии. Царьков настраивал количество еды на поле и то, сколько энергии даёт каждая точка. Если длина змейки достигала 16, происходило деление пополам. Дети получали от родителей гены с добавлением случайных мутаций.

После нескольких дней симуляции и 16 миллионов шагов сменилось 2900 поколений. Организмам удалось добиться некоторой стабильности: на поле постоянно оставалось в живых около 300 змей.

Затем Царьков устроил битву одной из эволюционировавших змей («Дарвина») и лучшего алгоритма из предыдущего видео, который учился с тренером. Дарвин одержал убедительную победу 5:0.

В других экспериментах нейроэволюция всегда давала более скромные результаты, чем алгоритмы, в которые изначально заложили выигрышные стратегии. Так и здесь: несмотря на успехи, Дарвин проиграл «Адаму». Это ещё одна нейросеть, которую Царьков создал, как он сам говорит, «по своему образу и подобию» (то есть выставил веса связей вручную).

Наконец, в третьем видео серии программист задался целью «испортить божественную природу Адама эволюцией». Царьков запустил в песочницу, уже заполненную «Дарвинами», одного «Адама». Два вида вступили в борьбу, как когда-то предки людей и неандертальцы. Спустя 14 миллионов ходов потомки более совершенного алгоритма вытеснили соперника: зелёная карта стала синей.

«Сломлено последнее сопротивление, и потомки Адама заполонили весь мир», — гласит мрачный комментарий.

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

Зелёным здесь обозначен «Дарвин», красным — «Адам». Дарвин был на поле с самого запуска симуляции. Он начал с нуля и достиг результата 160 на пике эволюции. Адама запрограммировали так, что его приспособленность оказалась 190. Но сразу после попадания в общую песочницу уровень Адама начал падать. Он соревновался с заведомо более слабым соперником и мог не напрягаться. Чтобы вытеснить Дарвина, Адаму хватило приспособленности 160-170 — чуть больше, чем у соперничающего вида.

Царьков дал видео подзаголовок «Идиократия». Это отсылка к знаменитой комедии, где герой попадает в будущее, населённое идиотами. В комментариях к ролику подписчики подняли серьёзные темы про пользу полового отбора и важность биоразнообразия. Один из комментаторов подвёл неутешительный итог: «Только искусственная эволюция спасёт человечество от деградации».

Из сказанного выше можно сделать и противоположный вывод: искусственное вмешательство в эволюцию не требуется для того, чтобы организмы могли найти полезные адаптации. Точно так же нет нужды жёстко направлять процесс обучения ребёнка, чтобы он принёс результаты.

Мозгу, организму, искусственному интеллекту необходимо предоставить определённую свободу и разрешить ошибаться. Связи, которые установятся в процессе стихийного развития, приведут к созданию чего-то, что ни один программист (селекционер, демиург) не мог заранее предусмотреть. Да, в процессе поиска решения придётся пару миллионов раз врезаться в стену и угробить тысячи своих копий. Но, видимо, такова цена свободы от создателя.

Статья создана участником Лиги авторов. О том, как она работает и как туда вступить, рассказано в этом материале.

#наука #игры #эволюция #нейросети #лонгриды #лигаавторов