На чем основаны генетические алгоритмы? Как происходит создание различных уровней в компьютерной игре? Каковы перспективы применения эволюционных алгоритмов? На эти и другие вопросы отвечает доцент Университета Иннополис Джозеф Браун.
Процедурная генерация контента в играх — это процесс автоматического создания различных ресурсов. Таким образом можно создавать повествование или сюжет игры или более простые объекты, такие как деревья. Или какие-нибудь элементы игрового процесса. Например, какие будут уровни. Этим я в основном и занимаюсь: как создать уровень, который отвечает некоторым ожиданиям игрока и некоторым ожиданиям в контексте повествования. Я использую много приемов из области, которая называется вычислительный интеллект. А вычислительный интеллект применяет биоинспирированные методы для решения сложных задач оптимизации.

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

Говоря простым языком, есть некая функция, для которой нужно найти подходящее значение. Эта функция может не быть в строгом смысле математической функцией. Могут быть некоторые критерии, которым она должна отвечать. И каждый результат можно будет оценить по этим критериям каким-то объективным способом. То есть я могу оценить качество уровня с помощью какой-нибудь исчислимой величины.

Это может быть уровень интереса игроков. Может, это критерий количества врагов, которых нужно победить, чтобы добраться до босса. Может, игроку нужен определенный предмет, чтобы пройти в следующую зону. То есть это необязательно очень точные математические функции. Но к ним можно выставить определенное значение приспособленности. А поскольку я могу выставить значение приспособленности для всех этих узлов, существ или хромосом, я могу объективно сказать, что одно из них лучше другого. Это позволяет мне решить, какие из них я хочу перенести в следующее поколение. Для этого я просматриваю свою популяцию и отдаю приоритет тем, у которых приспособленность лучше, чем у других. Затем их можно как-то рекомбинировать. Например, если у нас уровень состоит из комнат, то их можно как-то иначе между собой составить.

Эти рекомбинации затем дают нам новую популяцию, которую можно переранжировать, и продолжить процесс. Повторяя цикл много раз, пока не будет достигнуто определенное значение, я таким образом могу не только создать разнообразные уровни, ведь будет готовая структура, но я также буду знать, что они отвечают требованиям игрока и требованиям дизайнера.

Эти методы позволяют нам создать огромное количество уровней для видеоигры без дополнительных расходов на работу художника или другого специалиста.

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

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

Многие структуры также допускают так называемую эволюцию с человеком в контуре. То есть ранжированием популяции занимается человек. Он смотрит на рисунки, текстуры, размещение. Их можно оценить с точки зрения эстетики. Можно оценить, как они отвечают этим требованиям и как можно увлечь и заинтересовать человека. А затем попытаться высчитать искомую красоту в этом пространстве. С помощью подобных методов генератор и человек как бы совместными усилиями создают новую структуру.

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

Дисциплина как таковая возникла в 70-е годы XX века. Появились четыре основные группы, которые занимались разными подходами к симуляции эволюции. Это эволюционные стратегии, эволюционное программирование, генетические алгоритмы и генетическое программирование. Все четыре группы исследовали очень похожие типы структур при изучении работы этих алгоритмов: везде бралась популяция, везде в качестве шкалы бралась функция приспособленности, применялась какая-то манипуляция для направленного развития.

Эти четыре группы не могли договориться о том, что играет главенствующую роль. В результате все четыре стали собирательно называть генетическими алгоритмами. Но ключевой момент во всем этом — это анализ биологической работы. Иногда даже ошибочные биологические работы дают очень интересные алгоритмы. Например, по Ламарку, если я отличный бегун и я постоянно бегаю, то это зафиксируется у меня в генах, и любой мой ребенок будет бегать гораздо быстрее меня. Или другой пример этой теории — жираф. Жираф пытается достать листья повыше, и со временем его шея станет длинней. По законам известной биологии это неверная теория. Неверная гипотеза. Эволюция происходит в генетике, наследных чертах и естественном отборе.

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

Еще я работаю с алгоритмами, которые анализируют взаимодействие видов. Взять, например, исследования Дэвида Лэка на островах Галапагос, где обитают известные вьюрки. Эти вьюрки разделились по размеру клюва: одни колют орехи, другие добывают семена, третьи пьют кровь. Они все разделились на очень много видов. И они все бьются за одни и те же ресурсы. Мы можем создать симуляцию, в которой несколько популяций борются за очки приспособленности и делят пространство существования.

Словом, идеи из биологии вдохновляют нас на создание интересных алгоритмов для оптимизации наподобие той, что мы видим в живой природе.

Мы берем множество идей. И порой биологическое фиаско оказывается чудом информатики. Эволюционные алгоритмы применяют для решения разнообразных задач по оптимизации, для машинного творчества, для реализации различных биологических принципов в компьютерной среде.

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

Джозеф Браун, PhD in Computer Science, доцент Университета Иннополис, преподаватель факультета компьютерных наук Брокского Университета.
ПостНаука