pokibor
25.11.2007, 13:12
Я, Pokibor, в здравом уме и трезвой памяти, взял на себя смелость начать писать небольшую статейку про искуственный интеллект (AI) в компьютерных играх. Первый пост будет потихоньку дополняться новыми методами, обо всех допущенных ошибках просьба стучать в личку.
Основы программирования AI в играх
Когда начинающий программист делает свою первую игру, зачастую перед ним сразу встаёт вопрос о создании искусственного интеллекта в той или иной его форме. Конечно, определённый класс игр (особенно аркады) не подразумевает наличия соперника с иллюзией присутствия мозгов в голове, однако кому не интересно сделать не очередной клон тетриса, а свою простенькую стратегию, action (не обязательно 3D) или даже RPG? В любом из этих случаев уже не достаточно наличия соперника с абсолютно случайным или напрямую прописанным поведением. Противник (будь то монстр или враждебный генерал), а порой - и союзник (свой собственный солдат, лишенный высочайшего внимания) должен уметь оценивать ситуацию и реагировать на её изменение таким образом, чтобы игроку его действия казались в какой-то мере осмысленными и логичными.
Впервые столкнувшись с такой проблемой, начинающий программист, как правило, всерьёз задумывается. Если он вообще не знаком с основными методами программирования AI, то совершенно не представляет, в каком направлении нужно делать следующий шаг. Если знаком - то долго думает, какой же метод применить в данном случае, чтобы потом не переписывать код целиком из-за одной ошибки в начале. Эта небольшая статейка призвана дать основные понятия о некоторых методах программирования AI в играх и помочь определиться с выбором конкретного алгоритма для каждого случая. Сразу замечу, что общее число различных методов чрезвычайно велико и всё время увеличивается. Многие компании имеют свои собственные наработки на этот счёт и не спешат их афишировать.
Тем не менее, основные алгоритмы построения AI достаточно известны, ну а все остальные являются в той или иной мере их вариациями и результатами смешивания. Причём смешивать различные методы не просто можно, но и зачастую нужно, чтобы добиться вменяемого результата. Например, глобальные действия армии можно описать прецедентами или даже задать скриптово, а вот для каждого конкретных действий каждого солдата использовать нечёткую логику. Тогда, выполняя данный генералом приказ, одновременно боец сможет создавать иллюзию осмысленных действий - искать укрытия, прикрывать товарищей, а когда дело запахнет керосином - забыть про приказы и драпануть с поля боя. К слову, наглядный пример применения нечёткой логики для описания действий солдат можно найти в Half-Life, где подобные «мозги» встроены в головы действительно разумно кувыркающимся спецназовцам.
Итак, от общих слов перейдём к делу. Со временем я буду добавлять в данный пост заметки о методах AI, ответы на часто задаваемые вопросы и, возможно, примеры реализации того или иного алгоритма на практики.
Прежде чем писать AI
Первой проблемой, встающей перед начинающими программистами при написании AI, является, как ни странно, никак не связанная с алгоритмами построения этого самого AI проблема. А именно - как организовать ощущение мира игры компьютерным персонажем (в дальнейшем будем его для краткости называть ботом вне зависимости от жанра игры и исполняемой роли)? Ведь любому алгоритму нужны какие-то данные для обработки - сведения о местоположении игрока, своей базе и войсках, карте, на которой происходит битва... Разумеется, реализовывать это «честно» (т.е. вычисляя боту видимый им самим экран и распознавая образы) не хватит никакого времени и ресурсов компьютера. Поэтому приходится идти на упрощения и откровенно жульнические приёмы. Причём чем больше данных получает бот, тем труднее писать и/или обучать его AI. Кстати, отчасти по этой причине в стратегиях компьютер, как правило, игнорирует туман войны на карте и хорошо ещё если рассчитывает видимость себе войск игрока. Заставить AI честно проводить разведку местности довольно трудно, потому и приходится подобным образом жульничать.
Из примера выше должно быть понятно, что ощущение ботом мира игры должно производится сугубо внутренними средствами программы и внутренним же представлением этого самого мира. Бот не может видеть игрока как модель напротив себя - он может лишь взять его координаты из памяти, построить отрезок «я-игрок» и проверить, не пересекает ли этот отрезок стены и укладывается ли в угол зрения. Если проверка пройдена - бот говорит себе «я вижу игрока» и делает соответствующие выводы, в противном случае он считает, что не видит противника. Иными словами, по конструкции программы бот, очевидно, должен иметь доступ к полной модели игры без ограничений и самостоятельно регулировать свою честность. Казалось бы, простая истинна - и тем не менее на первых парах программист может забыть об этом, в результате чего бот видит сквозь стены и палит в них из всего арсенала.
Итак, если мы делаем action, боты в простейшем варианте могут брать направления на все значимые предметы (возможно, находящиеся в пределах некоторого расстояния) и проверять, а видят ли они эти предметы. Из такой модели расчеты вытекает, что бот не может заметить игрока, высунувшегося из-за угла менее чем наполовину. Представления игрока кругом и расчет видимости противоположных точек окружности, очевидно, снимет эту проблему. Впрочем, подобные алгоритмы можно улучшать разными способами, что-то описывать здесь бессмысленно. Нужно лишь помнить, что любое усложнение алгоритма одновременно увеличивает потребление ресурсов процессора, так что если у нас много ботов - даже добавление в уравнение лишней пары членов может вылиться в серьёзное замедление программы. Везде необходим баланс.
Если мы делаем стратегию или RPG, то область видимости юнита у нас, как правило, составляет круг, а карта - плоская. В таких условиях рассчитывать видимость намного проще, что компенсируется куда большим количеством юнитов на карте. И вот тут-то как раз какие-то усложнения алгоритма вряд ли уместны, разве что в случае тактической стратегии или RPG с упором на реалистичность/stealth-элементами.
Во-вторых, нужно всегда помнить одну из главных заповедей игрового AI: «Задача бота - не выиграть, а красиво проиграть». Бот всегда превосходит человека реакцией, данными об игровой ситуации и наличием бонусов. В таких условиях сделать AI, размазывающий игрока ещё на старте, не так сложно. Но кому нужен подобный бот? Да, игроки бывают разной степени хардкорности. Да, они постоянно обвиняют AI в тупости. Но стоит переборщить - и в игру просто-напросто никто не станет играть, а вместо обвинений в тупости пойдут обвинения в читерстве (и, кстати, вполне законные - как уже было сказано, сделать AI, получающий данные подобно человеку, крайне сложно и накладно). Поэтому в ориентированной на более-менее честное противостояние с ботом игре (в-основном, стратегии, в меньшей степени action, ну а к RPG это почти не относится) стоит сделать несколько уровней сложности именно искусственного интеллекта, а не занижения-завышения игровых параметров бота/игрока. Хотя второй путь, конечно, проще, и им также часто пользуются (см., например, Heroes of Might & Magic V).
На этой «оптимистичной» ноте закончу вводную и перейду к описанию конкретных методов построения AI.
Скриптовый AI
Ну, тут особо говорить нечего. Обычно под скриптами понимают жёстко прописанные сценарии поведения бота, построенные по принципу конечного автомата. Разработчик заготавливает расписывает состояния, в который может находиться бот, задаёт условия перехода из состояния в состояние и приказ в каждой ситуации. Например:
Бот появляется на карте -> Респаун; Проверка видимости игрока
Проверка видимости игрока:
Игрок замечен -> Выстрелить; Проверка видимости игрока
Игрок не замечен -> Проверка получения повреждений
Проверка получения повреждений:
Повреждений не получено ->Проверка наличия цели движения
Повреждения некритические -> Повернуться в сторону источника повреждений; Проверка видимости игрока
Повреждений критические -> Гибель; Бот появляется на карте
Проверка наличия цели движения:
Цель движения есть -> Приблизиться к цели движения; Проверка видимости игрока
Цели движения нет -> Назначить цель движения; Проверка видимости игрока
Получается простейшая схема действий бота. Конечно, в реальности всё куда сложнее - если по этой схеме, например, бот при встрече игрока тупо останавливается и начинает в него стрелять, то в нормальном action’е такое недопустимо. В то же время сохраняется основной принцип - на каждое действие с учётом проверки условий приходится только один ответ, он же последующее действие.
Достоинством такого алгоритма, несомненно, являются простота реализации и быстродействие. Из всех вариантов AI скриптовый наиболее быстрый, потому он и используется в играх когда все доступные ресурсы кидаются на красоту картинки или реалистичность физики. Также данный алгоритм не требует мороки с обучением, при необходимости в конечный автомат элементарно вставляется новое состояние со всеми нужными условиями перехода.
В то же время для написания конечного автомата требуется именно программист, так как далёкие от программирования люди, как правило, мыслят более общими категориями и не способны толком написать скрипты, даже если им предоставить для этого средства. А «не видящий за деревьями леса» программист может недостаточно обще описать ситуации в целом, в результате чего AI будет не просто смотреться болванчиком - а, скорее, полным идиотом, в определённых ситуациях постоянно ведущим себя неверно. Собственно, наличие на одно действие с одним набором условий одного и только одного ответа и является наиболее бросающимся в глаза недостатком скриптов, за который их постоянно ругают. Приноровившись к такому AI, человек мысленно построит у себя в голове примерную схему его действий и уже способен будет предсказать реакцию бота на любое поведение. Результат - потеря интереса к игре, так как игрок отлично знает, что выкинет бот в данный момент.
Бросающееся в глаза улучшение алгоритма - придумать несколько вариантов ответов на одно и то же состояние и случайным образом выбирать один из них. Это, разумеется, будет выглядеть лучше - но искусственность AI всё равно будет бросаться в глаза. Скриптовый AI неспособен предпринимать неожиданных действий (а ведь порой глупые на первый взгляд действия человека благодаря эффекту неожиданности позволяют ему победить). Кстати, не стоит в данном случае тыкать пальцем в слово «победить» и напоминать автору про цель AI. Если бот нигде не будет побеждать, с ним будет не интересно играть. Да, постоянные глобальные победы AI над игроком недопустимы. И в то же время без локальных побед бота против него банально неинтересно играть.
Поэтому скриптовый AI - скорее, решение на крайний случай, когда иные варианты по тем или иным причинам считаются нецелесообразными. Скрипт не подведёт - но и не даст надолго заинтересовать игрока.
В то же время для небольших «крупинок» игры следует применять именно скрипты. Например, какая разница, насколько шаблонно ведёт себя отдельный пехотинец в армии из пяти десятков себе подобных, оставшись без приказов игрока? В таких случаях скриптовоть даже идёт в плюс - не замедляет излишне процессор и освобождает игрока от лишнего микроконтроля, так как он уверен в определённых действиях подчиненного, скажем, при внезапном нападении врага. Нереалистично? Зато дёшево, надёжно и практично.
Системы, основанные на правилах (Rule-based systems, далее RBS)
Тут я испытываю некоторые затруднения. С одной стороны, идея подобных систем достаточно близка к скриптам. С другой - назвать «скриптами» все программы на языке Prolog значит попасть под шквал заслуженной критики. И в то же время RBS представляет собой нечто вроде неоптимизированной версии достаточно объёмного скрипта. В общем, после некоторых раздумий я принял следующее решение: я не буду отдельно описывать системы, основанные на правилах. Следующим разделом идёт система с рассуждениями, основанными на прецедентах, из которой RBS получается некоторым упрощением. Там она, пожалуй, и будет рассмотрена. В противном случае кое-что придётся повторять дважды, а это бессмысленно.
Рассуждения, основанные на прецедентах (Case-based reasoning, далее CBR)
При написании этой части статьи использован диплом Connor’а, зарегистрированного на этом форуме как L’ombre (http://forum.igromania.ru/member.php?u=100261).
CBR можно считать некоторым шагом вперёд по сравнению со скриптами и, соответственно, с упомянутой выше RBS. В основе CBR лежит идея использования предыдущего опыта решения определённых задач для последующих выводов. Такой подход примерно соответствует человеческому мышлению - принимая решения, мы постоянно основываемся на полученном за прожитые года опыте. В судебных системах некоторых стран (например, США, к России же это не относится) в законодательном порядке закреплено использование прежних судебных решений-прецедентов как основы для новых вердиктов. Таким образом, CBR-системы довольно естественны и, что важно, в отличие от скриптов и RBS способны к обучению. В них отсутствует необходимость строить на основе новых знаний какие-либо общие правила - при использовании CBR правила обобщаются автоматически, в процессе применения накопленного опыта к дальнейшим проблемам.
Центральным объектом любой CBR-системы является база знаний (более узкое название - база прецедентов). Именно в ней в форме некой структуры хранится накопленный системой опыт. Конкретный вид подобной структуры (прецедента) зависит от решаемой задачи, однако конкретный экземпляр всегда включает в себя сведения об исходной ситуации и принятом в этих условиях решении.
Собственно, построение подобной структуры - одна сложностей при создании CBR-системы. Она должна быть достаточно общей для описания всех возможных ситуаций, и в то же время достаточно простой для автоматического построения по ситуации соответствующего ей экземпляра структуры.
Например, для бота в шутере эта структура может быть следующей:
Описание ситуации:
- Текущее состояние здоровья (хиты, броня, бонусы - всё, что влияет на жизнеспособность).
- Текущее состояние оружейного арсенала (пушки, кол-во патронов, бонусы - всё, что влияет на способность к уничтожению противника).
- Некое обобщенное описание положения на уровне - допустим, удаленность от ближайших бонусов «оздоровительного» типа, «нападательного» типа, положение видимых противников. Всё это по обобщённ0ым категориям (допустим, справа-слева-прямо).
- Известные данные по противникам - их состояние здоровья и арсенал.
- Если есть союзники - похожие данные по ним.
Видно, что в подобной структуре можно в с достаточной степенью точности описать ситуацию для стандартных deathmatch’а и teamplay’а. В случае более сложных типов игр (например, захвата флага или того сложнее - стратегии) описание ситуации, разумеется, будет ещё сложнее. Однако главное - это некая общность, так как конкретики вроде записи в базу данных координат допускать ни в коем случае нельзя.
Описание принятого решения:
Здесь всё гораздо проще. Скорее всего, для шутера это будет обобщенный приказ юниту, например, «атаковать противника с наименьшим числом хитов», «сменить оружие на такое-то», «бежать к такому-то типу бонуса» и т.п. Для стратегии решение будет, наверное, более разветвлённым, возможно - содержащим несколько направлений развития и агрессии, на которых боту следует сосредоточиться. Исполнение таких приказов обычно прописывается более простой моделью искусственного интеллекта либо вообще забивается напрямую. Иными словами, в играх CBR довольно трудно применять «в чистом виде»; обычно прецеденты работают на глобальном уровне, тогда как на локальном данные системой приказы исполняются другими методами.
Если в системе предусмотрено обучение, описание принятого решения может включать в себя также некий коэффициент его «разумности», выведенный в процессе работы системы.
С базой знаний вроде разобрались. Теперь можно переходить к процессу принятия решений, обычно называемого «четыре ‘R’» по числу пунктов (Retrieve, Reuse, Revise, Retain). Итак:
- Retrieve или извлечение. На этом этапе просматривается вся база знаний и из неё выбираются прецеденты с условиями, похожими (подобными) на текущую ситуацию. Как правило, тут происходит не сравнение по принципу «похож-не похож», а используется некое значение похожести. Например, этот прецедент похож на текущую ситуацию на 50%, этот - аж на 90%, а тот - всего на 15%. Написание функции, сравнивающей два описания ситуации - вторая сложность при создании CBR-системы. Тут следует вводить для каждого поля структуры прецедента некие коэффициенты, которые потом можно было бы легко изменить, и впоследствии играть с ними, подбирая подходящую. Кстати, такая функция вполне может задавать характер компьютерного игрока. У агрессивного, например, относящиеся к нападению коэффициенты будут больше, а у бота защитного типа - наоборот, ниже.
В результате применения функции похожести каждому прецеденту из содержащихся в базе в соответствие поставлен некий коэффициент похожести. Далее большинство прецедентов с низкими коэффициентами отбрасываются (тут, очевидно, следует задать некую границу либо иной способ определения остающихся прецедентов). Оставшиеся же формируют так называемое конфликтное множество. На этом этап извлечения заканчивается.
- Reuse или повторное использование. Для каждого из находящихся в конфликтном множестве прецедентов берётся соответствующее ему решение и каким-то образом адаптируется к конкретной ситуации, если это нужно. Например, тут можно чётко определить тип бонуса, к которому, собственно, боту предстоит бежать, выбрать конкретного противника для атаки и т.п.
- Revise или пересмотр. Из конфликтного множества на основании некого критерия выбирается определённый прецедент, и программа пытается применить его адаптированное решение применяется к текущей ситуации. Возможно, это не удастся либо заведомо приведёт к неверной ситуации - тогда выбирается (возможно, на основании иного критерия) другой прецедент и попытка применения повторяется.
- Retain или сохранение. Выведенное только что решение сохраняется в базе знаний для будущего использования. Вот это - как раз обещанное обучение. Сохраняется могут как верные решения, так и неудачи, причём в случае, когда разумность решения видна не сразу, принятые прецеденты разумнее записывать в базу только в конце партии. Также возможно не сохранять новые решения, а модифицировать «коэффициенты разумности» уже существующим, тем, что были приняты в ходе партии, либо делать и то, и другое.
Разумеется, этап сохранения можно отделить от остальных - в таком случае некий эксперт записывает условие прецедента и его решение, после чего прецедент заносится в базу. Как уже было сказано, описание прецедента обладает определенной степенью общности - стало быть, экспертом может быть не только программист, но и, например, проектировщик игры - как раз та личность, что «не замечает деревьев в лесу».
Очевидным достоинством CBR-системы является её прозрачность и мощность. Всегда можно открыть базу знаний, модифицировать некие коэффициенты и, при необходимости, добавить новые прецеденты, равно как и организовать обучение в процессе игры с пользователем. Однако «глобальность» базы знаний, содержащей сотни (а то и тысячи) прецедентов требует хорошей организации поиска и сравнения условий друг с другом, уже не говоря о сложности написания структуры для хранения прецедента и функции вычисления похожести. Тем не менее, для решения глобальных задач вроде принятия решения о текущей стратегии развития/нападения/защиты CBR-системы потенциально мощны, так как позволяют отойти от шаблонов скриптов и правил, да ещё и приноравливаться к игроку в ходе игры с ним.
Теперь, как обещал, поговорю о системе, основанной на правилах. В ней также наличествует база знаний (точнее, база правил), построенная по принципу «условие-действие». Конфликтного множества как такового нет, как и функции вычисления похожести. Правила перебираются друг за другом и при полном совпадении условия с текущим выполняется соответствующее действие, после чего процесс уже применяется к результату. Об обучении речи не идёт, все правила изначально забиты в систему создателями и не изменяются. Таким образом, RBS можно считать «облегченной версией» CBR, когда нужно организовать что-то посложнее явно прописанного конечного автомата-скрипта, но не хочется разбираться с функциями похожести и организовывать обучение.
Основы программирования AI в играх
Когда начинающий программист делает свою первую игру, зачастую перед ним сразу встаёт вопрос о создании искусственного интеллекта в той или иной его форме. Конечно, определённый класс игр (особенно аркады) не подразумевает наличия соперника с иллюзией присутствия мозгов в голове, однако кому не интересно сделать не очередной клон тетриса, а свою простенькую стратегию, action (не обязательно 3D) или даже RPG? В любом из этих случаев уже не достаточно наличия соперника с абсолютно случайным или напрямую прописанным поведением. Противник (будь то монстр или враждебный генерал), а порой - и союзник (свой собственный солдат, лишенный высочайшего внимания) должен уметь оценивать ситуацию и реагировать на её изменение таким образом, чтобы игроку его действия казались в какой-то мере осмысленными и логичными.
Впервые столкнувшись с такой проблемой, начинающий программист, как правило, всерьёз задумывается. Если он вообще не знаком с основными методами программирования AI, то совершенно не представляет, в каком направлении нужно делать следующий шаг. Если знаком - то долго думает, какой же метод применить в данном случае, чтобы потом не переписывать код целиком из-за одной ошибки в начале. Эта небольшая статейка призвана дать основные понятия о некоторых методах программирования AI в играх и помочь определиться с выбором конкретного алгоритма для каждого случая. Сразу замечу, что общее число различных методов чрезвычайно велико и всё время увеличивается. Многие компании имеют свои собственные наработки на этот счёт и не спешат их афишировать.
Тем не менее, основные алгоритмы построения AI достаточно известны, ну а все остальные являются в той или иной мере их вариациями и результатами смешивания. Причём смешивать различные методы не просто можно, но и зачастую нужно, чтобы добиться вменяемого результата. Например, глобальные действия армии можно описать прецедентами или даже задать скриптово, а вот для каждого конкретных действий каждого солдата использовать нечёткую логику. Тогда, выполняя данный генералом приказ, одновременно боец сможет создавать иллюзию осмысленных действий - искать укрытия, прикрывать товарищей, а когда дело запахнет керосином - забыть про приказы и драпануть с поля боя. К слову, наглядный пример применения нечёткой логики для описания действий солдат можно найти в Half-Life, где подобные «мозги» встроены в головы действительно разумно кувыркающимся спецназовцам.
Итак, от общих слов перейдём к делу. Со временем я буду добавлять в данный пост заметки о методах AI, ответы на часто задаваемые вопросы и, возможно, примеры реализации того или иного алгоритма на практики.
Прежде чем писать AI
Первой проблемой, встающей перед начинающими программистами при написании AI, является, как ни странно, никак не связанная с алгоритмами построения этого самого AI проблема. А именно - как организовать ощущение мира игры компьютерным персонажем (в дальнейшем будем его для краткости называть ботом вне зависимости от жанра игры и исполняемой роли)? Ведь любому алгоритму нужны какие-то данные для обработки - сведения о местоположении игрока, своей базе и войсках, карте, на которой происходит битва... Разумеется, реализовывать это «честно» (т.е. вычисляя боту видимый им самим экран и распознавая образы) не хватит никакого времени и ресурсов компьютера. Поэтому приходится идти на упрощения и откровенно жульнические приёмы. Причём чем больше данных получает бот, тем труднее писать и/или обучать его AI. Кстати, отчасти по этой причине в стратегиях компьютер, как правило, игнорирует туман войны на карте и хорошо ещё если рассчитывает видимость себе войск игрока. Заставить AI честно проводить разведку местности довольно трудно, потому и приходится подобным образом жульничать.
Из примера выше должно быть понятно, что ощущение ботом мира игры должно производится сугубо внутренними средствами программы и внутренним же представлением этого самого мира. Бот не может видеть игрока как модель напротив себя - он может лишь взять его координаты из памяти, построить отрезок «я-игрок» и проверить, не пересекает ли этот отрезок стены и укладывается ли в угол зрения. Если проверка пройдена - бот говорит себе «я вижу игрока» и делает соответствующие выводы, в противном случае он считает, что не видит противника. Иными словами, по конструкции программы бот, очевидно, должен иметь доступ к полной модели игры без ограничений и самостоятельно регулировать свою честность. Казалось бы, простая истинна - и тем не менее на первых парах программист может забыть об этом, в результате чего бот видит сквозь стены и палит в них из всего арсенала.
Итак, если мы делаем action, боты в простейшем варианте могут брать направления на все значимые предметы (возможно, находящиеся в пределах некоторого расстояния) и проверять, а видят ли они эти предметы. Из такой модели расчеты вытекает, что бот не может заметить игрока, высунувшегося из-за угла менее чем наполовину. Представления игрока кругом и расчет видимости противоположных точек окружности, очевидно, снимет эту проблему. Впрочем, подобные алгоритмы можно улучшать разными способами, что-то описывать здесь бессмысленно. Нужно лишь помнить, что любое усложнение алгоритма одновременно увеличивает потребление ресурсов процессора, так что если у нас много ботов - даже добавление в уравнение лишней пары членов может вылиться в серьёзное замедление программы. Везде необходим баланс.
Если мы делаем стратегию или RPG, то область видимости юнита у нас, как правило, составляет круг, а карта - плоская. В таких условиях рассчитывать видимость намного проще, что компенсируется куда большим количеством юнитов на карте. И вот тут-то как раз какие-то усложнения алгоритма вряд ли уместны, разве что в случае тактической стратегии или RPG с упором на реалистичность/stealth-элементами.
Во-вторых, нужно всегда помнить одну из главных заповедей игрового AI: «Задача бота - не выиграть, а красиво проиграть». Бот всегда превосходит человека реакцией, данными об игровой ситуации и наличием бонусов. В таких условиях сделать AI, размазывающий игрока ещё на старте, не так сложно. Но кому нужен подобный бот? Да, игроки бывают разной степени хардкорности. Да, они постоянно обвиняют AI в тупости. Но стоит переборщить - и в игру просто-напросто никто не станет играть, а вместо обвинений в тупости пойдут обвинения в читерстве (и, кстати, вполне законные - как уже было сказано, сделать AI, получающий данные подобно человеку, крайне сложно и накладно). Поэтому в ориентированной на более-менее честное противостояние с ботом игре (в-основном, стратегии, в меньшей степени action, ну а к RPG это почти не относится) стоит сделать несколько уровней сложности именно искусственного интеллекта, а не занижения-завышения игровых параметров бота/игрока. Хотя второй путь, конечно, проще, и им также часто пользуются (см., например, Heroes of Might & Magic V).
На этой «оптимистичной» ноте закончу вводную и перейду к описанию конкретных методов построения AI.
Скриптовый AI
Ну, тут особо говорить нечего. Обычно под скриптами понимают жёстко прописанные сценарии поведения бота, построенные по принципу конечного автомата. Разработчик заготавливает расписывает состояния, в который может находиться бот, задаёт условия перехода из состояния в состояние и приказ в каждой ситуации. Например:
Бот появляется на карте -> Респаун; Проверка видимости игрока
Проверка видимости игрока:
Игрок замечен -> Выстрелить; Проверка видимости игрока
Игрок не замечен -> Проверка получения повреждений
Проверка получения повреждений:
Повреждений не получено ->Проверка наличия цели движения
Повреждения некритические -> Повернуться в сторону источника повреждений; Проверка видимости игрока
Повреждений критические -> Гибель; Бот появляется на карте
Проверка наличия цели движения:
Цель движения есть -> Приблизиться к цели движения; Проверка видимости игрока
Цели движения нет -> Назначить цель движения; Проверка видимости игрока
Получается простейшая схема действий бота. Конечно, в реальности всё куда сложнее - если по этой схеме, например, бот при встрече игрока тупо останавливается и начинает в него стрелять, то в нормальном action’е такое недопустимо. В то же время сохраняется основной принцип - на каждое действие с учётом проверки условий приходится только один ответ, он же последующее действие.
Достоинством такого алгоритма, несомненно, являются простота реализации и быстродействие. Из всех вариантов AI скриптовый наиболее быстрый, потому он и используется в играх когда все доступные ресурсы кидаются на красоту картинки или реалистичность физики. Также данный алгоритм не требует мороки с обучением, при необходимости в конечный автомат элементарно вставляется новое состояние со всеми нужными условиями перехода.
В то же время для написания конечного автомата требуется именно программист, так как далёкие от программирования люди, как правило, мыслят более общими категориями и не способны толком написать скрипты, даже если им предоставить для этого средства. А «не видящий за деревьями леса» программист может недостаточно обще описать ситуации в целом, в результате чего AI будет не просто смотреться болванчиком - а, скорее, полным идиотом, в определённых ситуациях постоянно ведущим себя неверно. Собственно, наличие на одно действие с одним набором условий одного и только одного ответа и является наиболее бросающимся в глаза недостатком скриптов, за который их постоянно ругают. Приноровившись к такому AI, человек мысленно построит у себя в голове примерную схему его действий и уже способен будет предсказать реакцию бота на любое поведение. Результат - потеря интереса к игре, так как игрок отлично знает, что выкинет бот в данный момент.
Бросающееся в глаза улучшение алгоритма - придумать несколько вариантов ответов на одно и то же состояние и случайным образом выбирать один из них. Это, разумеется, будет выглядеть лучше - но искусственность AI всё равно будет бросаться в глаза. Скриптовый AI неспособен предпринимать неожиданных действий (а ведь порой глупые на первый взгляд действия человека благодаря эффекту неожиданности позволяют ему победить). Кстати, не стоит в данном случае тыкать пальцем в слово «победить» и напоминать автору про цель AI. Если бот нигде не будет побеждать, с ним будет не интересно играть. Да, постоянные глобальные победы AI над игроком недопустимы. И в то же время без локальных побед бота против него банально неинтересно играть.
Поэтому скриптовый AI - скорее, решение на крайний случай, когда иные варианты по тем или иным причинам считаются нецелесообразными. Скрипт не подведёт - но и не даст надолго заинтересовать игрока.
В то же время для небольших «крупинок» игры следует применять именно скрипты. Например, какая разница, насколько шаблонно ведёт себя отдельный пехотинец в армии из пяти десятков себе подобных, оставшись без приказов игрока? В таких случаях скриптовоть даже идёт в плюс - не замедляет излишне процессор и освобождает игрока от лишнего микроконтроля, так как он уверен в определённых действиях подчиненного, скажем, при внезапном нападении врага. Нереалистично? Зато дёшево, надёжно и практично.
Системы, основанные на правилах (Rule-based systems, далее RBS)
Тут я испытываю некоторые затруднения. С одной стороны, идея подобных систем достаточно близка к скриптам. С другой - назвать «скриптами» все программы на языке Prolog значит попасть под шквал заслуженной критики. И в то же время RBS представляет собой нечто вроде неоптимизированной версии достаточно объёмного скрипта. В общем, после некоторых раздумий я принял следующее решение: я не буду отдельно описывать системы, основанные на правилах. Следующим разделом идёт система с рассуждениями, основанными на прецедентах, из которой RBS получается некоторым упрощением. Там она, пожалуй, и будет рассмотрена. В противном случае кое-что придётся повторять дважды, а это бессмысленно.
Рассуждения, основанные на прецедентах (Case-based reasoning, далее CBR)
При написании этой части статьи использован диплом Connor’а, зарегистрированного на этом форуме как L’ombre (http://forum.igromania.ru/member.php?u=100261).
CBR можно считать некоторым шагом вперёд по сравнению со скриптами и, соответственно, с упомянутой выше RBS. В основе CBR лежит идея использования предыдущего опыта решения определённых задач для последующих выводов. Такой подход примерно соответствует человеческому мышлению - принимая решения, мы постоянно основываемся на полученном за прожитые года опыте. В судебных системах некоторых стран (например, США, к России же это не относится) в законодательном порядке закреплено использование прежних судебных решений-прецедентов как основы для новых вердиктов. Таким образом, CBR-системы довольно естественны и, что важно, в отличие от скриптов и RBS способны к обучению. В них отсутствует необходимость строить на основе новых знаний какие-либо общие правила - при использовании CBR правила обобщаются автоматически, в процессе применения накопленного опыта к дальнейшим проблемам.
Центральным объектом любой CBR-системы является база знаний (более узкое название - база прецедентов). Именно в ней в форме некой структуры хранится накопленный системой опыт. Конкретный вид подобной структуры (прецедента) зависит от решаемой задачи, однако конкретный экземпляр всегда включает в себя сведения об исходной ситуации и принятом в этих условиях решении.
Собственно, построение подобной структуры - одна сложностей при создании CBR-системы. Она должна быть достаточно общей для описания всех возможных ситуаций, и в то же время достаточно простой для автоматического построения по ситуации соответствующего ей экземпляра структуры.
Например, для бота в шутере эта структура может быть следующей:
Описание ситуации:
- Текущее состояние здоровья (хиты, броня, бонусы - всё, что влияет на жизнеспособность).
- Текущее состояние оружейного арсенала (пушки, кол-во патронов, бонусы - всё, что влияет на способность к уничтожению противника).
- Некое обобщенное описание положения на уровне - допустим, удаленность от ближайших бонусов «оздоровительного» типа, «нападательного» типа, положение видимых противников. Всё это по обобщённ0ым категориям (допустим, справа-слева-прямо).
- Известные данные по противникам - их состояние здоровья и арсенал.
- Если есть союзники - похожие данные по ним.
Видно, что в подобной структуре можно в с достаточной степенью точности описать ситуацию для стандартных deathmatch’а и teamplay’а. В случае более сложных типов игр (например, захвата флага или того сложнее - стратегии) описание ситуации, разумеется, будет ещё сложнее. Однако главное - это некая общность, так как конкретики вроде записи в базу данных координат допускать ни в коем случае нельзя.
Описание принятого решения:
Здесь всё гораздо проще. Скорее всего, для шутера это будет обобщенный приказ юниту, например, «атаковать противника с наименьшим числом хитов», «сменить оружие на такое-то», «бежать к такому-то типу бонуса» и т.п. Для стратегии решение будет, наверное, более разветвлённым, возможно - содержащим несколько направлений развития и агрессии, на которых боту следует сосредоточиться. Исполнение таких приказов обычно прописывается более простой моделью искусственного интеллекта либо вообще забивается напрямую. Иными словами, в играх CBR довольно трудно применять «в чистом виде»; обычно прецеденты работают на глобальном уровне, тогда как на локальном данные системой приказы исполняются другими методами.
Если в системе предусмотрено обучение, описание принятого решения может включать в себя также некий коэффициент его «разумности», выведенный в процессе работы системы.
С базой знаний вроде разобрались. Теперь можно переходить к процессу принятия решений, обычно называемого «четыре ‘R’» по числу пунктов (Retrieve, Reuse, Revise, Retain). Итак:
- Retrieve или извлечение. На этом этапе просматривается вся база знаний и из неё выбираются прецеденты с условиями, похожими (подобными) на текущую ситуацию. Как правило, тут происходит не сравнение по принципу «похож-не похож», а используется некое значение похожести. Например, этот прецедент похож на текущую ситуацию на 50%, этот - аж на 90%, а тот - всего на 15%. Написание функции, сравнивающей два описания ситуации - вторая сложность при создании CBR-системы. Тут следует вводить для каждого поля структуры прецедента некие коэффициенты, которые потом можно было бы легко изменить, и впоследствии играть с ними, подбирая подходящую. Кстати, такая функция вполне может задавать характер компьютерного игрока. У агрессивного, например, относящиеся к нападению коэффициенты будут больше, а у бота защитного типа - наоборот, ниже.
В результате применения функции похожести каждому прецеденту из содержащихся в базе в соответствие поставлен некий коэффициент похожести. Далее большинство прецедентов с низкими коэффициентами отбрасываются (тут, очевидно, следует задать некую границу либо иной способ определения остающихся прецедентов). Оставшиеся же формируют так называемое конфликтное множество. На этом этап извлечения заканчивается.
- Reuse или повторное использование. Для каждого из находящихся в конфликтном множестве прецедентов берётся соответствующее ему решение и каким-то образом адаптируется к конкретной ситуации, если это нужно. Например, тут можно чётко определить тип бонуса, к которому, собственно, боту предстоит бежать, выбрать конкретного противника для атаки и т.п.
- Revise или пересмотр. Из конфликтного множества на основании некого критерия выбирается определённый прецедент, и программа пытается применить его адаптированное решение применяется к текущей ситуации. Возможно, это не удастся либо заведомо приведёт к неверной ситуации - тогда выбирается (возможно, на основании иного критерия) другой прецедент и попытка применения повторяется.
- Retain или сохранение. Выведенное только что решение сохраняется в базе знаний для будущего использования. Вот это - как раз обещанное обучение. Сохраняется могут как верные решения, так и неудачи, причём в случае, когда разумность решения видна не сразу, принятые прецеденты разумнее записывать в базу только в конце партии. Также возможно не сохранять новые решения, а модифицировать «коэффициенты разумности» уже существующим, тем, что были приняты в ходе партии, либо делать и то, и другое.
Разумеется, этап сохранения можно отделить от остальных - в таком случае некий эксперт записывает условие прецедента и его решение, после чего прецедент заносится в базу. Как уже было сказано, описание прецедента обладает определенной степенью общности - стало быть, экспертом может быть не только программист, но и, например, проектировщик игры - как раз та личность, что «не замечает деревьев в лесу».
Очевидным достоинством CBR-системы является её прозрачность и мощность. Всегда можно открыть базу знаний, модифицировать некие коэффициенты и, при необходимости, добавить новые прецеденты, равно как и организовать обучение в процессе игры с пользователем. Однако «глобальность» базы знаний, содержащей сотни (а то и тысячи) прецедентов требует хорошей организации поиска и сравнения условий друг с другом, уже не говоря о сложности написания структуры для хранения прецедента и функции вычисления похожести. Тем не менее, для решения глобальных задач вроде принятия решения о текущей стратегии развития/нападения/защиты CBR-системы потенциально мощны, так как позволяют отойти от шаблонов скриптов и правил, да ещё и приноравливаться к игроку в ходе игры с ним.
Теперь, как обещал, поговорю о системе, основанной на правилах. В ней также наличествует база знаний (точнее, база правил), построенная по принципу «условие-действие». Конфликтного множества как такового нет, как и функции вычисления похожести. Правила перебираются друг за другом и при полном совпадении условия с текущим выполняется соответствующее действие, после чего процесс уже применяется к результату. Об обучении речи не идёт, все правила изначально забиты в систему создателями и не изменяются. Таким образом, RBS можно считать «облегченной версией» CBR, когда нужно организовать что-то посложнее явно прописанного конечного автомата-скрипта, но не хочется разбираться с функциями похожести и организовывать обучение.