[не]интересные идиоты

YPP (YPP_PUBLIC@MAIL.RU)

Спецвыпуск: Хакер, номер #064, стр. 064-038-4

На практике системы правил реализуются двумя способами. Первый — дерево принятия решений (decision tree), которое выглядит приблизительно так:

if ( условие1 )

действие1;

else

if ( условие2 )

действие2;

else

// и так далее...

Другой способ реализации системы правил опирается на скриптовые языки и является более гибким, так как в этом случае вся логика работы ИИ отделена от основного кода движка. Скриптовые системы правил применяются шире всего в стратегических играх, например Age of Empires.

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

по стопам дедушки дарвина

Применять генетические алгоритмы в играх начали сравнительно недавно. Они хорошо подходят в ситуациях, в которых нужно создать разнообразие существ, несколько схожих по внешнему виду и/или поведению. Примером тому могут служить пешеходы в гоночных симуляторах или население некого виртуального города/мира (как в GTA или The Sims).

Из школьного курса биологии нам всем известно, что в каждом из живых существ зашит некий генетический код (ДНК помнишь?). Причем существа в пределах одного вида имеют схожий по структуре код, разный по своим составляющим единицам — генам. Каждый ген кодирует некое свойство живого организма, например цвет глаз, тип волос. Генетический код каждого индивида является некой комбинацией генов его родителей плюс небольшой процент мутаций (вообще-то в биологии имеются более строгие правила наследования, но нам это не так важно). Основываясь на теории генов, Чарльз Дарвин вывел свою знаменитую теорию эволюции (что-то подсказывает мне, что Дарвин вообще ничего не знал о генах: когда Чарльз писал свои книги, Мендель еще не опубликовал даже свои опыты :) — прим. Лозовского). Суть теории Дарвина известна всем: выживает сильнейший, то есть самый приспособленный. У одних видов показателем «силы» может быть скорость, у других — устойчивость к морозам, у третьих — собственно физическая сила. На основе этих базовых концепций и создают ИИ в некоторых играх. Для начала зададим структуру ДНК как массив генов и их возможных значений. Не забудем учесть, что здесь понятие гена может быть намного шире и с его помощью удобно кодировать не только биологические свойства, но и, например, стиль одежды, черты характера, прическу и т.д. (см. таблицу 1).

Дальше генерируем первое поколение из N представителей данного вида выбором случайных значений из множества возможных (для каждого гена). Следующая процедура называется тестом на пригодность (fitness testing), она же является одной из самых сложных. Сгенерированных индивидов помещаем в реальный игровой мир и выбираем наиболее «способных». К примеру, для бойцов можно устраивать виртуальные поединки, чтобы решить, кто лучше. Потом генерируем второе поколение, создавав N индивидов как линейной комбинации ДНК отобранных. Также можно добавить небольшую степень мутаций. Дальше — снова тест на пригодность и т.д. В конечном счете получается, что чем больше номер поколения, тем лучше особи. И еще мысль: если продолжать «профотбор» и во время игры, то получится, что каждый следующий противник будет более приспособлен к конкретному игроку. Возникает некое подобие самообучения системы ИИ.