Создание игрового бота с GOAP

В этой статье детально разберём, как создать игрового ИИ с помощью Goal-Oriented Action Planning на TypeScript.

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

Мы применили этот подход к игре LandLords, создав бота, который самостоятельно планирует свои действия. В этой игре победа зависит от умения комбинировать различные стратегии. Бот постоянно анализирует ситуацию и адаптируется к непредсказуемым решениям соперников — это делает его сложным и интересным противником. Генеративность карты создаёт ещё больше возможностей для тактических манёвров и торговля ресурсами также добавляет элемент непредсказуемости. Всё это бот делает с помощью планировщика.

Этот планировщик и есть наш бот, это генератор планов действий, сердце ИИ системы. Планировщик это чистая функция, которая принимает на вход текущее состояние игрового мира и список доступных действий, а возвращает оптимальный план действий для достижения заданной цели. Давайте теперь подробнее рассмотрим, что представляет собой этот GOAP бот. Я буду использовать простые аналогии о пиве, чтобы это было понятным, cheers 🍻😄

Алгоритм планирования

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

1. isGoalReached — достигнута ли цель.
2. sortPlanQueue — сортировка планов.
3. perform — выполнение потенциального действия.

1. isGoalReached

Любое игровое состояние можно описать как набор фактов: булевы или числовые значения. И чтобы узнать, достигнута ли цель, мы проверяем, соответствует ли текущее состояние игры цели. Цель и состояние представляются в виде объектов типа GoalFacts. Проверка выглядит очень просто, булевы значения сравнимаем в лоб, а числовые как больше или равно.

type GoalFacts = Record<string, (boolean | number)>

const isGoalReached = (
  goal: GoalFacts,
  state: GoalFacts,
) => Object
  .entries(goal)
  .every(([key, value]) => (typeof value === 'number'
    ? state[key] as number >= value
    : state[key] as boolean == value))

Мы не можем купить пива, если у нас недостаточно денег и нет с собой документа, подтверждающего возраст :D

2. sortPlanQueue

Сортировка используется для нахождения самого выгодного плана действий. Мы сортируем очередь планов перед обработкой шага, чтобы минимизировать количество необходимых шагов и максимизировать их эффективность. Если два плана имеют одинаковую длину, мы отдаём предпочтение тому, у которого суммарная «награда» выше — то есть, который приносит больше пользы. В противном случае приоритет получает план с меньшим количеством шагов: мы стараемся достигать цели кратчайшим путём.

Звучит сложновато, но всё достаточно интуитивно. Если нам надо купить пива, то мы пойдём в тот магазин, где оно стоит дешевле. А если цена в магазинах одинаковая, пойдём в тот, который ближе :D

type ItemQueue = {
  state: GoalFacts
  plan: Action[]
  totalUtility: number
}

const sortPlanQueue = (a: ItemQueue, b: ItemQueue) => {
  return a.plan.length === b.plan.length
    ? b.totalUtility - a.totalUtility
    : a.plan.length - b.plan.length
}

3. perform

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

const perform = (
  facts: GoalFacts,
  effects: GoalFacts,
): GoalFacts => {
  const result = { ...facts }

  for (const key in effects) {
    const value = effects[key]

    result[key] = typeof value === 'number'
      ? value + (result[key] as number ?? 0)
      : value
  }

  return result
}

Перед походом за пивом мы в воображении представляем как идём в магазин, платим за него деньги, получаем пиво и обновляем свой инвентарь :D

Действия

Далее рассмотрим действия, они описываются типом Action. Действие — это атомарная единица работы, которую бот может выполнить для изменения состояния игры. Действие это базовый строительный блок, «сегмент лестницы», который мы используем для создания сценария. Каждое действие имеет свои условия для его совершения (preconditions), определяющие, когда оно может быть выполнено, и последствия (effects), которые вносят изменения в состояние игры. В процессе сортировки планов мы использовали поле totalUtility, которое является комбинацией двух значений reward и priority. Эти поля опциональны, но они помогают явно выразить награду. Можно было ограничиться только полем reward, но приоритет это как дополнительный коэффицент влияния: «Вот это надо сделать прям очень желательно и срочно, даже если очков награды даёт мало или вообще не даёт».

type Action = {
  name: string
  preconditions: GoalFacts
  effects: GoalFacts
  reward?: number
  priority?: number
}

Все действия могут быть сериализованы в JSON и это гарантия декларативности. Но мне больше нравится описание на JavaScript/TypeScript, так как можно использовать префикс + для числовых эффектов. Такая запись лучше отражает намерения и позволяет нам более интуитивно воспринимать изменения состояния игры как прибавление или уменьшение значений.

const action: Action = {
  name: 'BuyBeer',
  preconditions: { hasDocument: true, money: 10 },
  effects: { beer: +1, money: -10 },
}

Цель 🎯

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

const state = { beer: 2 } satisfies GoalFacts
const goal = { beer: state.beer + 1 } satisfies GoalFacts

Если вам надо получить ещё 1 пиво 🍺
А у вас уже есть 2 пива 🍺🍺
То ваша конечная цель — 3 пива! 🍺🍺🍺
Без упоминания о документах и деньгах :D

GOAP-solver

И это всё, что необходимо для создания интеллекта для бота. Я подготовил репозиторий с исходным кодом github/13luck/goap-solver, чтобы вы могли изучить всё самостоятельно. В репозитории есть несколько тестов, демонстрирующих торговлю на примере игры LandLords, ну и конечно же пример с покупкой пива. Кроме того, я опубликовал NPM пакет goap-solver, который можно установить и протестировать самостоятельно.

Этот планировщик работает со значениями number и boolean. Ключевая функция planner является чистой и работает предсказуемо: для одинаковых условий всегда строит один и тот же план. Благодаря этому её легко проверять с помощью unit-тестов.

Работа с планировщиком выглядит так:

import { planner, Action, GoalFacts } from 'goap-solver'

// определить игровое состояние
const state = {
  hasDocument: false,
  money: 0,
  beer: 2,
} satisfies GoalFacts

// определить, чего мы хотим достичь
const goal = { beer: state.beer + 1 } satisfies GoalFacts

// определить доступные действия
const a: Action = {
  name: 'GetDocument',
  preconditions: { hasDocument: false },
  effects: { hasDocument: true },
  priority: 1,
}
const b: Action = {
  name: 'GetMoney',
  preconditions: { money: 0 },
  effects: { money: +10 },
  priority: 2,
}
const c: Action = {
  name: 'BuyBeer',
  preconditions: { hasDocument: true, money: 10 },
  effects: { beer: +1, money: -10 },
}

const actions = [c, b, a]
const plan = planner(state, goal, actions)
const result = plan?.map(({ name }) => name)

expect(result).toEqual(['GetDocument', 'GetMoney', 'BuyBeer'])

Демо

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

Цель нашего агента 😊 — добраться до кружки с пивом 🍺. При каждом изменении лабиринта, планировщик ищет снова оптимальный путь от старта к цели. Попробуйте построить разные конфигурации лабиринта и посмотрите, как система находит решения.

Performance

К вопросу о сложности GOAP: чем больше фактов и действий, тем больше вариативность. Алгоритм действительно перебирает все варианты, что может привести к очень долгим вычислениям — общая сложность экспоненциальная из-за природы самой задачи планирования. Чтобы избежать этого, стоит придерживаться небольших пространств и ограниченного набора фактов. Тогда вычисления станут практически мгновенными и планировщик быстро найдёт решение, не углубляясь в широкий поиск. В игре LandLords экономические отношения выражаются минималистично — буквально единицами, что очень хорошо подходит для GOAP.

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

Игровой бот LandLords

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

Конечно же мы видели Catanatron, это единственный open-source бот для Catan, который, по утверждению разработчика, хорошо играет. Тем не менее, он нам не подошёл по нескольким причинам: сложность адаптации и дорогая поддержка. Гораздо проще написать собственное решение на GOAP, пусть оно изначально и не тянет на гроссмейстера, собственно так мы и поступили.

Также одной из причин отказа от Catanatron была необходимость специфичной серверной среды. Проще запускать вычисления бота непосредственно в браузере игрока. Однако, вычисления планов в браузере могут быть ресурсоёмкими, что может приводить к фризам интерфейса. Для решения этой проблемы мы использовали Web Worker ⚙️, который позволяет выполнять вычисления в отдельном потоке, не блокируя основной поток интерфейса.

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

Заключение

GOAP — это простой и мощный инструмент для создания автономных агентов, который можно использовать в самых разных областях, не ограничиваясь только играми. Его сила в том, что вы не хардкодите конкретные сценарии, а фокусируетесь на комбинируемых действиях, что оставляет вам больше времени для творчества. Я надеюсь, что смог понятно и дружелюбно объяснить его принципы, и этот материал поможет вам начать создавать своих ботов, а аналогии о пиве вас нисколько не смутили, cheers 🍻😄