Введение

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

Игровой искусственный интеллект (англ. Game artificial intelligence) — набор программных методик, которые используются в компьютерных играх для создания иллюзии интеллекта в поведении персонажей, управляемых компьютером. Игровой ИИ, помимо методов традиционного искусственного интеллекта, включает также алгоритмы теории управления, робототехники, компьютерной графики и информатики в целом.

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

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

·  неигровые персонажи (англ. Non-player character, NPC) — как правило, эти персонажи являются дружественными или нейтральными к человеческому игроку.

·  боты (англ. Bot) — враждебные к игроку персонажи, приближающиеся по возможностям к игровому персонажу; против игрока в любой конкретный момент сражаются небольшое количество ботов. Боты наиболее сложны в программировании.

·  мобы (англ. Mob) — враждебные к игроку «низко интеллектуальные» персонажи. Мобы убиваются игроками в больших количествах ради очков опыта, артефактов или прохождения территории.

Актуальность работы

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

Постановка задачи

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

Методы поиска экстремума функций

Градиентный метод

Любую совокупность вещественных чисел (v₁, v₂, … , v_k), взятых в определенном порядке, можно рассматривать как точку или вектор с теми же координатами в пространстве k измерений (k-мерном пространстве). Запись вида v = (v₁, v₂, … , v_k) обозначает точку или вектор v с указанными в скобках координатами. Если для k-мерных векторов  v и w справедливы основные алгебраические операции:

• Сложение и вычитание;
• Умножение на действительное число;
• Скалярное произведение.

То совокупность всех таких векторов называют k-мерным евклидовым пространством и обозначают E_k.

Длиной вектора v называют число, определяемое по формуле

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

Единичным называют вектор, определяемый по формуле

Пусть в E_k заданы некоторая точка v = (v₁, v₂, … , v_k), единичный вектор t и непрерывно дифференцируемая по всем аргументам функция f(V) = f(v₁, v₂, … , v_k). Производной в точке V от функции f(V) по направлению луча, определяемому вектором t, называется предел

или

 

Градиентом функции f(V) называют вектор f(V) с координатами, равными частным производным  по соответствующим аргументам

Градиент указывает направление наибольшего возрастания функции. Противоположное направление –f(V) называется антиградиентом, оно показывает направление наискорейшего убывания функции. В точке экстремума V^* градиент равен нулю f(V^*)= 0. Если аналитически производные определить невозможно, их вычисляют приближенно.

Симплекс метод

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

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

Преимущества метода:

·  сравнительная простота логической структуры метода и, соответственно, программы для ЭВМ;

·  используется сравнительно небольшое число заранее установленных параметров;

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

Недостатки метода:

·  возникает проблема масштабирования, поскольку все координаты вершин симплекса зависят от одного масштабного множителя. Чтобы избежать такого рода проблем в практических задачах, следует промасштабировать все переменные с тем, чтобы их значения были сравнимы по величине;

·  алгоритм работает достаточно медленно, т.к. полученная на предыдущих итерациях информация не используется для ускорения поиска;

    ·  не существует простого способа расширения симплекса. Требуется перерасчет значений целевой функции во всех точках образца.

Метод сопряженных направлений Пауэлла

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

Алгоритм метода:

Шаг 1. задать исходные точки х₁, х₂ и направление d. В частности, направление d может совпадать с направлением координатной оси;

Шаг 2. произвести одномерный поиск из точки х₁ в направлении d и получить точку у₁, являющуюся точкой экстремума на заданном направлении;

Шаг 3. произвести поиск из точки х₂ в направлении d и получить точку у₂;

Шаг 4. вычислить направление (у₂ – у₁);

Шаг 5. провести одномерный поиск из точки у₁ (либо у₂) в направлении (у₂ – у₁) с выходом в точку х^*.

Проектирование системы искусственного интеллекта

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

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

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

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

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

Таким образом, в каждую единицу времени можно оценить эффективность выполнения каждого из действий d, доступных агенту:

Для достижения максимальной эффективности агента необходимо в каждую единицу времени выполнять наиболее эффективное действие:

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

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

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

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

На рисунке, представленном ниже, изображена диаграмма потоков данных.

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

После проектирования данная система была протестирована на простейшей игре. Суть игры состоит в том, что на поле случайным образом расположены агенты, обладающие искусственным интеллектом и ресурсы, которые будут ими собираться. Один из агентов управляет игрок. Цель игры – собрать как можно больше «пищи», но при этом необходимо опасаться оппонентов, которые могут напасть на игрового агента. Скриншот игрового процесса представлен на рисунке ниже.

Поведение игровых агентов было довольно ожидаемо. Они практически всегда поступали так, как необходимо: сначала собирали «пищу», а при ее отсутствии – нападали друг на друга.

Выводы

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

В ходе выполнения работы были построены диаграмма потоков данных и диаграмма классов. Архитектура системы разработана таким образом, что ИИ может применяться в различных игровых жанрах. Такая универсальность обеспечивается независимым, так называемым «мозгом» системы, который принимает обобщенный набор данных, анализирует его и выдает результат.

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

Список источников

1.                Портал искусственного интеллекта [Электронный ресурс]. – Режим доступа : http://www.aiportal.ru/

2.                Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns / R. Helm, R. Johnson, J. Vlissides : Addison Wesley, 1994. – 416 с.

3.                Искусственный разум – принципиальная схема [Электронный ресурс]. – Режим доступа : http://habrahabr.ru/post/166333/

4.                Rabin S. AI Game Programming Wisdom / Rabin Steve : 2001. – 314c.

5.                Ножов И.М. Практическое применение искусственного интеллекта в компьютерных играх / Ножов И.М. – М. : РГГУ, 2008. – 140 с.

6.                Методы поиска экстремума функции [Электронный ресурс]. – Режим доступа : http://www.scriru.com/14/31294432384.php

7.                Метод Нелдера-Мида [Электронный ресурс]. – Режим доступа : http://ru.wikipedia.org/wiki/Метод_Нелдера_—_Мида