by Mark Lewis Baldwin and Bob Rakosky
Вступление
При разработке искусственного интеллекта (ИИ) для стратегической игры вы всегда должны четко помнинть конечную цель — то есть, победу в игре. На самом деле, конечно, наша цель — развлечь игрока =) Но с точки зрения ИИ, цель его — именно победа над игроком. Как правило, победа в игре достигается достижением определённых условий. Для этого компьютер должен скоординированно и изощренно контролировать определённый набор ресурсов — юнитов и др.
Чтобы обозначить некую точку отсчёта, мы будем обсуждать Project AI как некий варгейм с несколькими подконтрольными юнитами. Каждый из них должен принять независимые решения и продвинутся куда-то в каждый ход (или цикл). В принципе, это относится не обязательно к варгеймам — а к любым играм, где необходимо управление различными взаимосвязанными ресурсами / юнитами.
Существуют разные подходы к проблеме, и мы не будем зацикливаться на каком-то одном. В Project AI методология должна позволять компьютеру решать задачи как стратегические, так и тактические задачи. Но сперва нам нужно постепенно построить механизм принятия ИИ решений. Каждый уровень, описанный ниже, базируется на предыдущем уровне.
Первый уровень…
Подход таков: каждый ход (или цикл) рассматриваем каждого юнита, который должежн быть перемещён (назовём это узлом принятия решений), строим список возможных решений и выбираем одно из них случайным образом. Иными словами — осматриваемся вокруг и куда-то двигаемся. Или не двигаться никуда; бездействие — это тоже действие.
Недостатки: пока что действия компьютера ни на сколько не продвигают его к победе. Однако такое хаотичное движение уже может запутать соперника =)
Второй уровень…
Решение таково: при выборе из возможных способов движения (из списка решений) для каждого юнита выбираем шаг, приближающий одно из условий победы. Поконкретнее: оглядитесь вокруг. Существуют ли условия победы, которые юнит может достичь (например, может ли он пройди в победную локацию)? Если да — реализовать.
Недостатки: Если вдруг возможны несколько разных действий, ведущих к достижению одной цели — у нас нет никаких фильтров, разбирающих два равных (или почти равных) действия. Кроме того, почти никогда условие победы не может быть достигнуто всего лишь одним действием, что возвращает нас обратно к первому уровню.
Третий уровень…
Решение: сравнить каждое из возможных перемещения за ход (цикл) на предмет того, как сильно оно продвинет нас к конечной цели. Каждое движение должно оцениваться не как TRUE / FALSE, а как числовое значение, вытекающее из анализа, насколько это движение продвинет нас на пути к цели. Например, движение, которое продвинет нас к победе за 2 хода, предпочтительнее, чем движение, после которого для достижения цели нам потребуется ещё 20 ходов.
Недостатки: Этот метод не обеспечивает действий, которые сами себе победы не достигают, но способствуют повышению шансов на победу (например, убийство юнита-конкурента, если это не является условием победы)
Четвертый уровень…
Решение: необходимо определить конкретные промежуточные цели, которые способствуют достижению основной цели, но сами по себе не являются условием победы. При каждом принятии решения юнит оценивает возможность достижения этих под-целей. Такими целями могут быть, например, убийство вражеских юнитов, защита дружественных, поддержка линии обороны, достижение стратегических позиций и т.д. Выполнение каждой из этих подцелей затем учитывается в оценке дерева решений. А затем уже из этих вариантов выбирается лучший. В общем-то, на этой основе уже можно делать полу-интеллектуальные игры.
Недостатки: каждый юнит принимает решения независимо от остальных. Это как в до-Наполеоновских войнах средневековья — хорошо работает, пока твой противник не начнет координировать собственные силы.
Пятый уровень…
Решение: дать юниту возможность принимать решение, изучив действия других дружественных юнитов. Взвесьте возможные результаты действий других юнитов и сопоставьте с текущим деревом решений юнита.
Недостатки: это позволит компьютеру координировать действия юнитов, но не даст возможности стратегического управления. Тем не менее, именно этот уровень ИИ — уже реальность во многих играх на сегодняшний день.
Кроме того, может возникнуть проблема: два юнита, опираясь на разные решения друг друга, будут изменять своё. Потом — ещё раз, и так в бесконечном цикле. Поэтому как минимум необходимо продумать и добавить немного рандома.
Шестой уровень…
Решение: создание структуры, принимающей стратегические (или крупные тактические) решения, которая может контролировать юнитов, которые, в свою очередь, скоординированы между собой.
Это приводит нас к проблеме управления разнообразными стратегическими ресурсами для достижения нескольких под-целей. Назовём это принятием решения стратегического уровня. Помочь в решении этой проблемы может опыт принятия таких решений в реальной жизни — то есть в бизнесе или на поле боя.
Решение на основе реальной армии — это несколько иерархических слоёв, каждый со своим управлением (принятием решений). Например, взводы 1, 2 и 3 контролируется «командиром», который в свою очередь находится под контролем более высокого уровня иерархии. Вся информация, как правило, идёт вверх по иерархии (то есть, взводу не будут постоянно сообщать о действиях другого взвода, находящегося в 20 километрах), в то время как контроль идёт вниз по иерархии.
В результате юнит нижнего уровня в стратегических задачах должен выполнять решения своего «командира» выше по иерархии. Сами они таких решений принять не могут, потому что: а) у него нет столько информации для принятия решения, как у юнита уровнем выше, и б) «нижний» юнит может принять стратегическое решение, отличное от своего «соседа», что приведёт к хаосу вместо координации.
Ок, первое решение готово. Мы строим нашу собственную иерархическую систему управления, либо делая одного из юнитов «командиром» рандомно, либо, если в игре есть фактическая система управления, подчиняя нижних юнитов их фактическим командирам. Даём возможность взаимодействовать этим «штабам» с другими наподобие этаких «мегаюнитов», координируя действия между собой. Они, в свою очередь, могут докладывать информацию выше и получать команды от своих, более высоких по иерархии командиров.
Замечу, что это был мой первый подход к проблеме.
Но, похоже, и в нём есть некоторые проблемы. Иерархическая система команд из реального мира не позволяет оптимально использовать ресурсы. Из-за иерархической структуры слишком много ресурсов могут быть направлены на решение какой-то одной отдельно взятой задачи, или ресурсы в параллельных ветвях иерархии не будут взаимодействовать. Например, два юнита могли бы легко захватить победную локацию, будь они вместе, но т.к. они подчиняются разным командным иерархиям (мега-юнитам), они не будут координировать свои действия для достижения того, что легко могли бы сделать, будь они в одной ветви иерархии. Иными словами, подобная искусственная структура может быть недостаточно гибкой для достижения оптимальных результатов. В реальной жизни, кстати, такое встречается сплошь и рядом =)
А игрок-человек не имеет подобных ограничений.
Во-первых, можно спросить себя: если иерархическая структура принятия решений имеет такие недостатки, почему такой подход используется бизнесменами и военными? Разница заключается в различии ситуаций. На поле боя информация, известная одному командиру при принятии решения, не может быть известна другому командиру в совсем другом месте в тот же момент. Кроме того, даже если бы вся возможная информация стала бы вдруг известна всему миру — все люди не могли бы принять одно и то же решение. Однако в игре может быть только одно решение, и принимает его либо игрок, либо AI, и ему известна вся информация. Это даёт гораздо больше простора для принятия решений и контроля над ситуацией, чем в военной иерархии.
Иными словами, бизнес- и военная модель принятия стратегических решений не является лучшей моделью для нас. В жизни эта модель существует из-за невозможности непрерывонго и мгновенного обмена информацией, но в стратегической игре эти ограничения отсутствуют и, следовательно, мы может построить более эффективную систему стратегического управления.
А мы для нашего искуственного интеллекта хотим реализовать лучшую из возможных техник, поэтому продолжим атаковать проблему на шестом уровне…
Project AI (Уровень 6, Альтернатива)
Вот мы и подошли к технике, которую реализуем в Проекте ИИ. Методология проекта экстраполирует военную иерархическую модель управления в нечто гораздо более гибкое.
Основная идея Project AI заключается в создании временных контролирующих структур (мега-юнитов, так называемых Project), предназначенных для выполнения конкретной задачи. Юниты передаются Project`у по мере необходимости, используются для достижения цели, а затем, когда более не нужны, освобождаются. Сами «Проекты» существуют временно для выполнения конкретной задачи, затем исчезают.
Таким образом проходя через цикл принятия решения каждого юнита, мы рассматриваем проект, за которым этот юнит закреплён (если вообще закреплён за каким-нибуть). Проект будет содержать информацию, необходимую для выполнения юнитом своей собственной задачи в рамках структуры Проекта.
Отметим, что эти задачи — не окончательные условия победы в игре, а очень конкретизированные промежуточные мини-цели, которые могут привести к окончательной победе. К примеру, очевидная победная цель — захват победной локации, но помещение юнита на высоту с хорошим обзором также вполне может быть целью, хоть и менее ценной.
Давайте немного подробнее рассмотрим эти самые Проекты и то, как они будут взаимодействовать.
Какие у них могут быть характеристики?
— Тип проекта — чего Проект пытается достичь — например, защитить город, убить врага, защитить другой юнит, захватить географический пункт и т.д.
— Специфика проекта — что есть конкретная задача для каждого проекта? Например, «Уничтожить 239-ю танковую дивизию», «Захватить город Сен-Вит» и т.д.
— Приоритет проекта — насколько важной является проект с точки зрения окончательной победы. Этот приоритет должен учитываться в глобальном приоритезировании, и проекты с низким приоритетом должны уничтожаться, чтобы не распылялись силы.
— Формула для рассчета добавочного значения закрепления юнита за проектом. Иными словами — даны юнит и большое число проектов. Мы должны как-то решить, к какому проекту прикрепить юнита. Эта формула оперировать множеством различных факторов, такими как: эффективность юнита в данном конкретном проекте, время доставки юнита к месту действия проекта, другие ресурсы, уже выделенные на проект, ценность проекта и т.д.
На практике мы привязали формулу к типу проекта, и каждый проект просто подставлял в неё свои значения. Такие значения могут включать в себя силы противника против проекта, минимум сил, необходимых для выполнения проекта, и вероятность успеха.
— Список юнитов, закрепленных за проектом.
— Другие вторичные данные
Ок. А теперь — как же использовать эти проекты. Вот один из вариантов…
1) Каждый ход рассматриваем множество возможных проектов, обновляем данные о текущих проектах, удалив старые проекты, которые уже не актуальны или имеют слишком низкий приоритет, и инициализируем новые проекты. Например, мы только что заметили, что вражеский юнит угрожает одному из наших городов. Мы создаём новый проект, цель которого заключается в защите города, или, если проект уже существует — возможно, придется пересмотреть свои ресурсы с учётом новых угроз.
2) Проходим циклом по всем юнитам, присваивая каждого из них к тому проекту, что имеет лучшее добавочное значение для закрепления за ним юнита. Обратите внимание, что это итерационный процесс, и с присвоением/освобождением юнитов могут изменится приоритеты присвоения юнитов другим проектам. Кроме того, у некоторых проектов может быть недостаточно ресурсов для достижения поставленной цели и они могут освободить имеющиеся ресурсы.
3) Обработать все юниты, запланировав их действие, принимая во внимание проект, к которому они привязаны, и действия других юнитов из того же проекта. Опять же, это может быть итеративный процесс.
В результате всего этого структура самого Project AI становится очень гибкой и позволяет любым юнитам корректировать действия между собой для достижения конкретных целей. Как только эти цели достигнуты, ресурсы могут быть перераспределены для достижения других целей, которые обычно появляются во время игры.
Одна из проблем реализации Project AI может заключаться в колебании юнитов между проектами. Другими словами, юнит закрепляется за одним проектом в один ход, в результате у конкурирующего проекта на следующий ход возникает больший приоритет и юнит переходит уже к нему. Это может привести к тому, что юнит будет бесконечно блуждать между двумя целями, ни разу не приблизившись ни к одной. Такую возможность необходимо предвидеть и нейтрализовать. Хоть может быть по меньшей мере несколько конкретных решений этой проблемы, существует и по меньшей мере одно общее решение. Ранее мы упоминали формулу для рассчета добавочных значений для добавления юнита к проекту. Решение заключается в этой формуле. В формулу нужно добавить немного «веса» юниту, если он уже принадлежит какому-то проекту (то есть, юнит должен «предпочитать» остаться в текущем проекте, а не перебежать в другой). Ключевая проблема тут — назначить вес, достаточный, чтобы избежать проблемы «перебеганий», но достаточно малый, чтобы не мешать действительно необходимым переходам между проектами. Поэтому скорее всего придется не раз изменять параметры «веса» для достижения удовлетворительного результата.
Седьмой уровень
Можно экстраполировать Project так же, как мы делали до этого. Одна экстраполяция может быть многослойным уровнем проектов и подпроектов. Есть и другие возможности для обдумывания и изучения.
© Copyright 1997 — Mark Baldwin and Robert Rakosky