УДК 004.89
К.В. Буга, В.С. Ильченко, А.В. Жук
Донецкий национальный технический университет, г. Донецк
кафедра программного обеспечения информационных систем
ИССЛЕДОВАНИЕ МЕТОДОВ ПОСТРОЕНИЯ ИГРОВОГО ИСКУССТВЕННОГО ИНТЕЛЛЕКТА И РАЗРАБОТКА УНИФИЦИРОВАННОЙ ПРОГРАММНОЙ АРХИТЕКТУРЫ ДЛЯ ИХ РЕАЛИЗАЦИИ
Аннотация
Буга К.В., Ильченко В.С., Жук А.В. Исследование методов построения игрового искусственного интеллекта и разработка унифицированной программной архитектуры для их реализации. Рассмотрен подход к построению игрового искусственного интеллекта, основанный на пошаговом поиске оптимального решения для множества задач. Выполнено проектирование программной архитектуры, реализующей данный подход.
Ключевые слова: игровой искусственный интеллект, принятие решения, программная архитектура.
Постановка проблемы. В последнее десятилетие в связи с развитием индустрии компьютерных игр всё чаще возникает необходимость в создании виртуальных соперников для игрока-человека, эффективно имитирующих сознательную деятельность в рамках решения стоящих перед ними задач. И хотя поддержание атмосферы соперничества требует от разработчиков различных уловок эмпирического характера, игровой искусственный интеллект по сути своей оперирует теми же понятиями и методами, что одноименное научное направление. [1]
Искусственный интеллект – дисциплина, которая занимается моделированием разумного поведения.
Многообразие задач, встающих перед разработчиками игрового ИИ, порождает многообразие подходов к их решению. Существуют различные подходы к построению систем ИИ.
Так, ИИ может быть основан на использовании Булевой алгебры и исчисления предикатов, в котором она расширена за счет введения предметных символов, отношений между ними, кванторов существования и всеобщности.
Другим распространенным подходом к построению ИИ является структурный, который подразумевает моделирование структуры человеческого мозга. Одной из первых таких попыток был перцептрон Френка Розенблатта. Основной моделируемой структурной единицей в перцептронах (как и в большинстве других вариантов моделирования мозга) является нейрон.
Довольно большое распространение получил и эволюционный подход. При построении систем ИИ по данному подходу основное внимание уделяется построению начальной модели, и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, это может быть и искусственная нейронная сеть, и набор логических правил и любая другая модель. В дальнейшем на основании проверки моделей отбираются лучшие из них, на основании которых по определённым правилам генерируются новые модели, из которых опять выбираются лучшие и т. д.[2]
Следует отметить, что, несмотря на общность встающих в рамках разных игровых жанров задач, создание новой игры требует разработки очередной специализированной подсистемы ИИ.
Учитывая сказанное, актуальной является задача создания информационной технологии, предоставляющей архитектуру и набор методов и алгоритмов, применение которых позволило бы универсализировать процесс создания эффективных подсистем ИИ для игр различных жанров.
Постановка задачи исследования. Объектом исследования в данной работе является игровой искусственный интеллект. Предметом исследования – алгоритмы, реализующие игровой искусственный интеллект.
Целью данной работы является разработка архитектуры подсистемы игрового ИИ, обеспечивающей эффективный выбор оптимального решения в рамках поставленных задач, и, в то же время, оперирующей данными об эффективности на абстрактном уровне, не привязанном к характеру предметной области.
Проектирование системы. Разработчики игрового ИИ, в силу особенностей решаемой задачи вынуждены балансировать на грани двух крайностей. Чтобы игра была интересной, необходимо иметь полный контроль над каждым решением ИИ в каждой возможной игровой ситуации. В то же время, создание ИИ, имитирующего поведение человека-оппонента, зачастую требует учёта такого большого количества всевозможных факторов и их взаимного влияния друг на друга, что для их описания потребуется просто колоссальная база правил.[3]
Игровой ИИ может представлять из себя как реализацию поведения одного оппонента, так и множества оппонентов и союзников игрока-человека. Каждую такую сущность, ответственную за принятие решений, будем в дальнейшем называть агентом. Для реализации игрового ИИ необходим как минимум один агент. Агенты способны совершать некоторый ограниченный набор действий D, каждое из которых приводит к изменению состояния агента или игрового мира.
Перед каждым агентом стоит ряд задач T. В данной работе считается, что оптимальное решение каждой из этих задач является целью существования агента в игровом мире. Каждой из этих задач можно поставить в соответствие приоритет:
(1)
Чем выше приоритет, тем важнее задача и тем выше вероятность того, что действия, необходимые для её достижения, будут выполнены в первую очередь.
Для простоты предположим, что в одну единицу времени агент может выполнять только одно действие. Для каждой задачи это действие обладает некоторым показателем эффективности:
(2)
Вычисление данного показателя может быть выполнено различными способами в зависимости от типа действия и особенностей предметной области, для которой разрабатывается игра.
Таким образом, в каждую единицу времени можно оценить эффективность выполнения каждого из действий d, доступных агенту:
(3)
Для достижения максимальной эффективности агента необходимо в каждую единицу времени выполнять наиболее эффективное действие:
(4)
Проектирование архитектуры подсистемы игрового ИИ. В данной работе при проектировании подсистемы игрового ИИ приоритетной задачей являлось создание архитектуры, максимально абстрагированной от особенностей конкретной задачи. Этого можно достичь, отделив механизм принятия решения (3, 4) от механизма сбора информации о текущем состоянии игрового мира и об эффективности каждого действия (2).
В процессе проектирования системы игрового искусственного интеллекта была построена диаграмма потоков данных, представленная на рис. 1.
Система имитирует любое из доступных агенту действий, опрашивая его об эффективности. И лишь при достижении наилучшего состояния агента в контексте всех стоящих перед ИИ задач принимает решение о необходимости совершить именно это действие. Выбранное действие передается агенту.
В процессе проектирования системы игрового искусственного интеллекта была построена диаграмма классов, изображенная ниже на рис. 2. Класс Game является классом игры, он содержит в себе такие атрибуты как список агентов и карту мира. Боты могут различаться по своим характеристикам, но они должны обладать одним интерфейсом, чтобы ИИ мог обращаться к необходимым методам класса во время работы. Для этого создан абстрактный класс AbstractAgent, который содержит интерфейс для взаимодействия ИИ и агента.
Класс Agent представляет собой конкретную реализацию агента. Помимо данных, описывающих состояние агента в рамках заданной предметной области, он содержит указатель на объект движка искусственного интеллекта. В классе AI_Engine реализуется алгоритм работы ИИ. У данного класса есть указатель на агент, который является владельцем, и единственный метод – принятие решения.
Рисунок 1 – Диаграмма потоков данных
Классы AI_Engine и AbstractAgent могут быть вынесены в отдельную библиотеку, поскольку ИИ имеет лишь перечень доступных действий, которые может совершить агент, их приоритеты и текущее состояние агента. На основании этих данных принимается решение о дальнейших действиях агента. Таким образом, система искусственного интеллекта может быть вынесена в отдельную библиотеку, и быть использована при создании различных игр. Следует отметить, что такой подход позволяет объединить в себе все преимущества обработки различных игровых ситуаций на стороне агента с гибкостью учёта взаимного влияния задач, стоящих перед агентом, на стороне AI_Engine.
Рисунок 2 – Диаграмма классов
Использование предложенной архитектуры в простейшей игре. Для исследования возможностей предложенной архитектуры была разработан простейший симулятор игрового мира, в котором на игровом поле размещаются агенты и «пища». Целью каждого агента является сборка максимального количества «пищи». При этом область карты, видимая агентом, ограничена. Помимо агентов и пищи на карте располагаются препятствия (черные квадраты). Как только вся «пища» на игровой карте собрана, игра заканчивается. Игроку-человеку предоставляется возможность управления одним из агентов.
Игра случайным образом располагает агентов и «пищу» на игровом поле, и на каждой игровой итерации опрашивает агентов об их следующем шаге, затем перерисовывает игровое поле. Агент, получая право сделать движение, обновляет свою видимую зону игрового поля, затем вызывает принятие решения подсистемой ИИ. ИИ запрашивает у агента эффективность перехода в каждом из направлений. Значение функции тем выше, чем ближе к агенту «пища» после совершения хода в данном направлении. Причём близость рассматривается с учетом поиска пути до цели (использовался алгоритм Jump Point Search[4]) и возможностей для видимых объектов добраться до «пищи» за меньшее количество ходов. Таким образом, выбрав экстремум из всех значений, определяется следующий ход. Если же агент находится в открытой местности, где в поле видимости нет целей, то принимается случайное направление, но при этом учитываются предыдущие ходы агента, чтобы он не двигался по замкнутой траектории.
На рис. 3 представлена экранная форма игры. Красными точками на ней изображены агенты, синими – ресурсы («пища»), поедаемые ими. А серыми рамками обведены области, которые видимы агентам.
Рисунок 3 – Экранная форма игрового процесса
Основной целью агентов на игровом поле является сбор ресурсов. Но если в видимой области игрового поля агент не находит «пищи», то он следует за ближайшим к нему агентом и «поедает» его. При нажатии клавиши пробел происходит генерация точек «пищи» на игровом поле. Одно нажатие генерирует 10 объектов-ресурсов, которые располагаются на игровом поле случайным образом.
Игра тестировалась при различных количествах агентов и ресурсов на игровом поле. При этом во всех случаях все агенты имели именно такое поведение, которое было ожидаемо: в первую очередь собирались ресурсы, а если они отсутствовали в области видимости, то агенты «поедали» друг друга. При изменении приоритетов у данных целей, поведение агентов изменялось соответствующе. Во всех случаях спустя небольшой промежуток времени на поле оставался всего один агент, который свободно перемещался по игровому пространству в поиска «пищи».
Выводы. В рамках данной работы описана архитектура и основные модули спроектированной подсистемы игрового искусственного интеллекта. Представлены диаграмма потоков данных и диаграмма классов. Архитектура системы разработана таким образом, что ИИ может быть применен в различных игровых жанрах. Такая универсальность обеспечивается за счёт абстрагирования центрального модуля ИИ от характера входных данных, и делегирования функций по анализу этих данных агенту, который является неотъемлемой частью игрового мира.
Большая часть исследования была направлена именно на определение структуры передаваемых данных, а так же правильный, в то же время независимый процесс их обработки и принятия решения.
Список литературы
1. Ножов И.М. Практическое применение искусственного интеллекта в компьютерных играх / Ножов И.М. – М. : РГГУ, 2008. – 140с.
2. Различные подходы к построению систем ИИ [Электронный ресурс]. – Режим доступу : http://lii.newmail.ru/podh_ai.htm
3. Старостин А.С. Алгоритмы реализующие искусственный интеллект. Материалы международной конференции «AII» / А.С. Старостин, М.Г. Мальковский – М. : РГГУ, 2009. – 516с.
4. Алгоритм поиска пути Jump Point Search [Электронный ресурс]. – Режим доступу : http://habrahabr.ru/post/162915/