Искусственные нейронные сети

Искусственные нейронные сети

Введение

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

Шутер (от англ. shoot - стрелять) - популярный жанр видео игр, игровой процесс которых основан на сражениях в режиме реального времени с использованием, как правило, огнестрельного оружия. Программирование игрового искусственного интеллекта в шутерах сводится, главным образом, к разработке модели поведения ботов. Ботами принято называть враждебных к игроку персонажей, которые контролируются компьютером. Для того, чтобы игровой процесс шутера был интересным и реалистичным, боты должны быть запрограммированы таким образом, чтобы с одной стороны, их было сложно переиграть, но с другой стороны, у человека оставались шансы на победу. В идеале, боты должны действовать подобно персонажам, контролируемым реальными людьми. В связи с этим, возникает ряд непростых задач, таких как реализация тактики командного ведения боя ботами; моделирование прицеливания, стрельбы, перемещения ботов по карте; реализация алгоритма выбора оружия ботом в зависимости от игровой ситуации. В данной работе рассматривается решение последней из перечисленных задач.

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

нейронный сеть алгоритм шутер

1. Основные подходы к реализации модели поведения бота

В ходе изучения предметной области, был проанализирован ряд материалов, касающихся деталей разработки искусственного интеллекта в видео играх, в основном, в шутерах от первого лица.

Во многих современных играх поведение ботов характеризуется высокой предсказуемостью. Это связано с тем, что разработчики делают упор на эффективность применяемых алгоритмов, не задумываясь непосредственно о модели принятия решений бота. Так, в шутерах Left 4 Dead и Killzone для расчета траектории перемещения ботов используется алгоритм A*. При этом, модели поведения ботов основаны на использовании конечных автоматов (Oude, 2011). В результате, поведение ботов полностью детерминировано, в отличие от поведения игровых персонажей, контролируемых реальными людьми. Безусловно, такой подход к созданию игрового искусственного интеллекта существенно снижает интерес пользователей к проекту.

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

if( enemy.distance < 5 )

{WITH-KNIFE()

}if( enemy.distance >= 5 AND enemy.distance <= 30 )

{WITH-SUBMACHINE-GUN()

}

{WITH-RIFLE()

}

(Данный пример взят из источника (Cole, Sushil, & Miles)).

Помимо предсказуемости принимаемых ботом решений, недостатком такого подхода является большое количество параметров, которые необходимо подбирать (В описанном выше примере таким параметром является enemy.distance, т. е. расстояние между ботом и врагом). Для того, приблизить поведение бота к реальности, нужно учитывать много факторов, и настройка экспертной системы становится сложной задачей. Авторы статьи, из которой был взят приведенный выше пример, предлагают использовать генетические алгоритмы для решения этой задачи.

. Обучение с подкреплением

Обучение с подкреплением - совокупность методов машинного обучения, в ходе которых агент обучается, взаимодействуя с некоторой окружающей средой. Агент взаимодействует с окружением (Environment), применяя различные действия (Actions) в зависимости от значений определенных параметров (State) и получая награду (Reward) (Sutton & Barto, 2012). Ниже приведена схема, иллюстрирующая описанное взаимодействие агента с окружающей средой.

Рисунок 1

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

. Искусственные нейронные сети. Типы ИНС

Искусственная нейронная сеть (ИНС) - математическая модель <https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C>, построенная по принципу организации сетей нервных клеток <https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD> живого организма. Нейронные сети широко применяются в различных областях. В частности, они активно используются в анализе данных, например, при решении задач классификации данных, кластеризации данных, аппроксимации непрерывных функций.

В зависимости от характера обучения, ИНС принято разделять на обучающиеся с учителем и обучающиеся без учителя. (Головко, 2001). Также, в последнее время, как правило, отдельно выделяют нейронные сети, обучающиеся с подкреплением. Каждый из перечисленных типов ИНС предназначен для решения определенного класса задач. Обучение с учителем применяется, когда заранее известны выходные значения сети при определенных входных значениях. Нейронные сети данного типа подходят для решения таких задач, как классификация данных. Среди алгоритмов обучения таких сетей наиболее известен метод обратного распространения ошибки (backpropagation). Нейронные сети, обучающиеся без учителя, имеет смысл использовать в тех случаях, когда нет никакой априорной информации о том, какими должны быть выходные значения сети. Такие нейронные сети, как правило, применяются для решения задач кластеризации данных. В данной работе была использована нейросетевая модель FALCON, обучающаяся с подкреплением. Подробное описание архитектуры данной нейронной сети, ее алгоритма обучения и особенностей применения, приведено далее.

Нейронная сеть FALCON

FALCON (Fusion Architecture for Learning, Cognition, and Navigation) - самоорганизующаяся нейронная сеть, обучающаяся с подкреплением. Данная нейронная сеть была использована при создании бота для известного шутера от первого лица Unreal Tournament (Wang & Tan, 2015).

Нейронная сеть FALCON характеризуется двухслойной архитектурой. Она состоит из когнитивного поля (Cognitive field) и трех полей ввода: Sensory field - отвечает за текущие состояния, Motor field - отвечает за действия, которые агент может выбирать и применять, поле Feedback field - отвечает за получаемые награды.

Ниже приведена схема архитектуры FALCON.

Рисунок 2

Далее используются следующие обозначения:

· - Sensory field.

· - Motor field.

· - Feedback field.

· - Cognitive field.

· - вектор состояний (state vector), .

· - вектор действий (action vector), .

· - вектор наград (reward vector), .

·вектор относится к полю , (входные векторы).

· - вектор весовых коэффициентов на входе j-го нейрона поля , относящийся к полю , .

· - параметры выбора (choice parameters), ,

· - параметры скорости обучения (learning rate parameters), , .

· - параметры вклада (contribution parameters), ,

· - параметры бдительности (vigilance parameters), , .

4. Алгоритм обучения FALCON

Изначально, когнитивное поле содержит m нейронов, где m - размерность вектора действий A. Весовые коэффициенты нейронов инициализируются случайными значениями, близкими к 1. Все значения, подаваемые на вход сети, должны лежать на отрезке [0; 1].

В начале каждой итерации использования нейронной сети на вход подаются следующие значения:

= S - данные о текущем состоянии агента;

= (1;...;1); - вектор, состоящий из единиц.

= (1; 0) - вектор, соответствующий максимальной награде, которую может получить агент.

Нейроны когнитивного поля обрабатывают значения, поступающие с полей ввода, при помощи специальной функции - функции выбора (choice function):

здесь и далее операция и норма определена |.| определены следующим образом:

;

Далее, выбирается нейрон J, для которого значение функции выбора максимально, и проверяется на предмет выполнения следующего критерия (vigilance criterion):

Если критерий не выполняется, то значение функции выбора нейрона J () полагается равным нулю, затем повторно выбирается нейрон когнитивного поля с максимальным значением функции выбора, для которого также проверяется выполнение этого критерия. Данная процедура продолжается до тех пор, пока не будет найден нейрон, удовлетворяющий условиям критерия.

Если для выбранного нейрона J критерий выполняется, то нейрон J считается выбранным. В случае, если нейрон J был выбран впервые (не был выбран на предыдущих итерациях использования нейронной сети), в когнитивное поле добавляется новый нейрон со случайными значениями весовых коэффициентов, близкими к 1. Далее, действие, соответствующее индексу максимального весового коэффициента нейрона J, считается выбранным. Оно применяется агентом, после чего становится известно значение награды r (. Далее, на поле ввода нейронной сети подаются значения: , после чего весовые коэффициенты нейрона J модифицируются по следующему правилу:

.

. Модификации алгоритма обучения FALCON

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

.Для нейрона когнитивного поля были определены два целочисленных параметра.

Первый параметр изначально инициализируется нулем. Каждый раз, когда нейрон выбирается для обучения и выбора действия, в случае, если примененное действие принесло положительную награду, значение этого параметра увеличивается на 1. В противном случае (если награда нулевая), значение параметра уменьшается на 1. Если значение параметра становится отрицательным, то такой нейрон подлежит немедленному удалению из когнитивного поля сети. Данный параметр позволяет боту не запоминать ненужную информацию и удалять устаревшие знания об окружающей среде.

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

.Сложность одной итерации использования FALCON составляет O(n2), где n - количество нейронов когнитивного поля сети. Поэтому, если в когнитивном поле накапливается слишком много нейронов, сеть начинает работать медленно, что не позволяет использовать ее в режиме реального времени. Для решения этой проблемы был введен параметр, отвечающий за максимальное возможное количество нейронов когнитивного поля. В случае, если число нейронов превышает данный параметр, то нейроны когнитивного поля сортируются по убыванию относительно средней награды, полученной во время их активности, затем половина нейронов (с меньшим значением средней награды) удаляется. Это позволяет сохранять компактность структуры нейронной сети на протяжении ее использования, не теряя при этом важных знаний, полученных при взаимодействии с окружающей средой.

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

На поле состояний нейронной сети State field было решено подавать значения следующих параметров окружающей среды:

1.distance - расстояние между ботом и противником.

.1 - distance.

3.velocity - модуль проекции вектора скорости противника на плоскость, перпендикулярную линии прицела бота.

.1 - velocity.

Все данные величины нормированы, и лежат на отрезке . Вместе с каждым параметром подается обратная величина 1 - . Это вызвано особенностями формул, используемых в алгоритме обучения сети.

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

·урон (от одного патрона): 8

·предельная дистанция: 1500

·задержка между выстрелами: 0.5 c

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

·урон (от одной дробинки): 5

·предельная дистанция: 700

·задержка между выстрелами: 2.0 c

.винтовка - дальнобойное оружие, наносящее относительно небольшой урон одиночными выстрелами. Эффективно на дальней дистанции.

·урон (от одного патрона): 15

·предельная дистанция: 1500

·задержка между выстрелами: 0.5 c

Действию соответствует использование оружия с индексом i.

Одним из самых нетривиальных вопросов при использовании нейронной сети, обучающейся с подкреплением, является подбор функции награды. Очевидно, что награда, получаемая ботом после использования оружия, должна зависеть в первую очередь от урона, нанесенного врагу. При этом, бот должен иметь возможность получить достаточно большую награду в любой игровой ситуации. Кроме того, значение награды должно принадлежать отрезку [0; 1], как любое значение, которое подается на вход FALCON.

В итоге, было принято решение рассчитывать значение награды следующим образом:

Здесь - нормированное расстояние между ботом и его противником; - нормированная величина урона, нанесенного противнику при выстреле.

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

. Игровой движок Unreal Engine

Unreal Engine - написанный на языке С++ игровой движок, который разрабатывается и поддерживается компанией Epic Games. Данный проект представляет собой полный набор инструментов для разработки игр, и позволяет создавать приложения для различных операционных систем и платформ. Первая игра, созданная при помощи движка Unreal Engine, вышла в 1998 году. Это был 3D-шутер "Unreal", разработанный компанией Epic Games (тогда компания называлась Epic MegaGames). Дополнительную информацию о данном движке можно получить из источника (Epic Games).

При разработке 3D-шутера, предназначенного, в частности, для тестирования описанного выше алгоритма выбора оружия, был сделан выбор в пользу именного этого игрового движка. Это связано с рядом особенностей Unreal Engine 4. Во-первых, данный игровой движок позволяет напрямую использовать в проекте файлы с исходным кодом на языке С++, на котором была написана непосредственно нейронная сеть. Во-вторых, Unreal Engine 4 предоставляет свои собственные инструменты, крайне удобные при разработке игрового искусственного интеллекта, такие, как деревья поведения. В-третьих, Unreal Engine - проект, который разрабатывается, поддерживается и постоянно обновляется уже на протяжении 18 лет, что обеспечивает стабильную работу, удобный интерфейс редактора и широкий набор различных инструментов. Еще одним важным и до сих пор не упомянутым преимуществом Unreal Engine 4 является то, что на сегодняшний день данный игровой движок является бесплатным (разработчики должны передавать 5 % от прибыли игры компании Epic Games, если доходы игры составляют более $3000 за квартал).

7. Описание проекта в Unreal Engine 4

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

Реализация бота в Unreal Engine 4 состоит из нескольких компонент:

.Файл, в котором хранятся основные характеристики бота, его конструктор (при необходимости), и события, на которые бот должен реагировать.

2.Behavior Tree - дерево поведения - класс, отвечающий непосредственно за поведение бота. Представляет из себя иерархическую структуру, состоящую из узлов различного типа. Узлы дерева поведения содержат скрипты, реализованные в Blueprint. (Epic Games).

3.Black Board предназначен для хранения параметров бота, используемых в дереве поведения.

4.AI Controller- класс, предназначенный для реализации непосредственно управления бота компьютером. В данном случае работа контроллера сводится к запуску дерева поведения бота.

.файлы с исходным кодом реализации нейронной сети: FALCON.h и FALCON.cpp.

Ниже приведен скриншот, на котором отображено реализованное дерево поведения бота.

Поскольку данный проект создавался исключительно с целью тестирования алгоритма выбора оружия, поведение бота сводится к патрулированию карты, и, в случае, если бот видит врага, ведению прицельного огня. Вызовы функций нейронной сети производятся в узле дерева поведения Fire. Сам узел, как и остальные, реализован в Blueprint.

Ниже приведен скриншот, отображающий фрагмент Blueprint-скрипта, на котором видно обращение к нейронной сети (вызов функции performFalcon, принимающей на вход параметры, отображающие текущее состояние окружающей среды и возвращающей индекс выбранного оружия).

Рисунок 3

На следующем скриншоте отображен момент игрового процесса: бот стреляет в игрового персонажа из дробовика).

Рисунок 4

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

В ходе тестирования проекта был проведен сравнительной анализ работы нейронной сети, обучающейся по модифицированному алгоритму, и работы сети, обучающейся по оригинальному алгоритму (без модификаций). Таблицы с результатами приведены ниже. В обоих случаях нейронная сеть начинала обучаться "с нуля"; тестирование проводилось в течении 2 минут.

Таблица 1. Результаты (оригинальный алгоритм):

оружиеЧисло примененийСредняя дистанция Средняя скорость противникаЧисло успешных примененийСредняя наградаавтомат340.290.21280.44дробовик270.260.28130.24винтовка410.350.12390.57

Таблица 2. Результаты (модифицированный алгоритм):

оружиеЧисло примененийСредняя дистанция Средняя скорость противникаЧисло успешных примененийСредняя наградаавтомат270.280.17220.45дробовик250.180.24180.36винтовка480.390.21440.6

Результаты тестирования показали, что в обоих случаях нейронная сеть работает адекватно. Данный вывод можно сделать, исходя из достаточно высокой доли успешных применений оружий, а также, из средних значений параметров внешней среды: на ближней дистанции бот предпочитал использовать дробовик, на дальней - винтовку, на средней - автомат. Во второй таблице можно наблюдать более четкое разделение случаев применения оружий в зависимости от дистанции, и более высокие средние значения полученной награды. Кроме того, бот, тактика выбора оружия которого была основана на нейронной сети, обучаемой по оригинальному алгоритму, за 2 минуты не смог обучиться правильно использовать дробовик: из 27 случаев его применения успешными оказались только 13; в случае применения модифицированного алгоритма эта проблема не наблюдается: 25 случаев применения дробовика, 18 из которых - успешные.

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

Заключение

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

Стоит добавить, что боты, поведение которых основано на обучении с подкреплением, имеют хороший потенциал для успешного прохождения теста Тьюринга для компьютерных игр - испытания, в ходе которого судьи в процессе игры определяют, кем контролируется тот или иной персонаж: человеком или компьютером. (Hingston, 2009)

Литература

1.Cole, N., Sushil, J., & Miles, C. Using Genetic Algorithm to Tune First-Person Shooter Bots. University of Nevada.

.Epic Games. (n.d.). Behavior Tree Quick Start Guide. Retrieved 1 15, 2016, from https://docs.unrealengine.com/latest/INT/Engine/AI/BehaviorTrees/QuickStart/

.Epic Games. (n.d.). Unreal Engine. Retrieved December 20, 2015, from https://www.unrealengine.com

.Hingston, P. (2009). A Turing Test for computer game bots. IEEE Transactions on Computational Intelligence and AI in Games, 169-186.

.Oude, M. (2011). Artifitial Intelligence techniques used in First-Person Shooter and Real-Time Stragegy games. University of Twente.

.Sutton, R., & Barto, A. (2012). Reinforcement Learning: An Introduction. Cambridge: The MIT Press.

.1Wang, D., & Tan, A.-H. (2015). Di Wang, Ah-Hwee Tan "Creating Autonomous Adaptive Agents in a Real-Time First-Person Shooter Computer Game". IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES.

.Головко, В. (2001). Нейронные сети: обучение, организация и применение. Москва: ИПРЖР.