Продолжаю мой цикл про игровой ИИ. В предыдущей части мы закончили с деревьями поведения (Behaviour Tree). В этой части мы начнем изучать ИИ, основанный на полезности (Utility Based AI).Также не забывайте подписываться на мой канал, чтобы не пропустить следующие части.

Полезность (Utility)

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

Подобный подход мы уже использовали в наших тестовых ИИ, когда искали точки для  передвижения Агента, используя систему EQS Unreal Engine. Этот подход можно расширить и на выбор поведения.

Диапазон полезности

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

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

Функция полезности.

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

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

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

В данном случае мы используем линейную функцию полезности. Следующим шагом будет изменение множителя на кривую. Очень популярными кривыми для функции полезности (кроме линейных) являются функции степени и логистические функции. Эти функции обладают параметрами, позволяющими их удобно настраивать, и при этом они удобно ведут себя в диапазоне значений и аргументов от 0 до 1. Хотя, конечно, никто не мешает вам использовать любые функция и любые кривые.

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

Теперь наш ИИ начинает лечиться только при низких значениях здоровья, а атаковать - когда враг подошёл достаточно близко.

Комбинация атрибутов

Давайте теперь определим, что может являться атрибутом для нашего поведения. Самым простым атрибутом является число, соответствующее какой-то характеристике нашего персонажа.(например здоровье или мана). Более сложным атрибутом будет некоторое значение, связанное с поведением ИИ (например соотношение расстояния от противника до нашего ИИ, или соотношение текущего здоровья противника к максимальному значению). Атрибутом может выступать некое выражение или функция, например количество противников или союзников вокруг нашего ИИ или противника. Атрибутом может выступать булевый флаг, определяющий есть или нет та или иная способность. Главное для атрибута то, что он должен быть способен вернуть нормализованное значение полезности элемента, которому он принадлежит.

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

Первый интуитивный способ - это перемножить результаты наших атрибутов.

Такой подход отлично работает, поэтому часто применяется. Перемножение позволяет одному атрибуту “убить” результирующую полезность просто вернув 0. Поскольку перемножаем мы числа от 0 до 1, то результирующая полезность всегда будет убывать. Поэтому, если число атрибутов разное для разных поведений, наш ИИ будет выбирать поведения с меньшим числом атрибутов.

Следующим подход к комбинации - это среднее арифметическое.

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

Еще одним способом к комбинации атрибутов является среднее геометрическое.

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

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

Бинарные атрибуты (фильтры)

Некоторые из атрибутов, определяющих полезность наших поведений, могут принимать только два значения - 0 или 1. Для нашего примера выше таким атрибутом может выступать наличие или отсутствие аптечки у персонажа. Так как такие атрибуты являются дискретными, их комбинирование с другими может вызвать неожиданные последствия. Например для среднего арифметического и среднего геометрического каждый дискретный атрибут будет повышать результирующее значение. Если количество дискретных атрибутов превышает количество обычных, среднее всегда будет стремиться к 1, что будет нарушать логику выбора поведения.

Логичным решением такого подхода будет разделить атрибуты на две категории: оценивающие атрибуты (scoring) и фильтры (filter). При подсчете результирующей полезности мы сначала анализируем фильтры, затем мы вычисляем общую полезности, используя оценивающие атрибуты.

В следующий раз мы рассмотрим как подход полезности можно использовать вне выбора поведения, также для анализа и выбора из множества однотипных объектов необходимых для проведения.