Содержание:

1. Введение
2. Актуальность темы работы
3. Существующие методы построения универсального искусственного интеллекта
4. Результаты исследования
5. Алгоритмы поиска пути
6. Результаты применения исследуемой архитектуры в простейшем игровом симуляторе
7. Выводы
8. Список литературы

Введение

Искусственный интеллект – наука и технология создания интеллектуальных машин, особенно интеллектуальных компьютерных программ. Искусственный интеллект можно определить как научную дисциплину, которая занимается моделированием разумного поведения. Это определение имеет один существенный недостаток – понятие интеллекта трудно объяснить. Проблема определения искусственного интеллекта сводится к проблеме определения интеллекта в целом: является ли он чем-то единым, или же этот термин объединяет набор разрозненных способностей. Искусственный интеллект предоставляет средство и испытательную модель для теорий интеллекта: эти теории могут быть сформулированы на языке компьютерных программ, а затем – испытаны. На сегодняшний день существует множество алгоритмов и подходов к созданию игрового искусственного интеллекта. Так, ИИ может быть основан на использовании Булевой алгебры и исчисления предикатов, в котором она расширена за счет введения предметных символов, отношений между ними, кванторов существования и всеобщности. Другим распространенным подходом к построению ИИ является структурный, который подразумевает моделирование структуры человеческого мозга. Одной из первых таких попыток был перцептрон Френка Розенблатта. Основной моделируемой структурной единицей в перцептронах (как и в большинстве других вариантов моделирования мозга) является нейрон. Довольно большое распространение получил и эволюционный подход. При построении систем ИИ по данному подходу основное внимание уделяется построению начальной модели, и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, это может быть и искусственная нейронная сеть, и набор логических правил и любая другая модель. В дальнейшем на основании проверки моделей отбираются лучшие из них, на основании которых по определённым правилам генерируются новые модели, из которых опять выбираются лучшие и т. д.

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

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

Существующие методы построения универсального искусственного интеллекта

Универсальный алгоритмический интеллект.

Сама идея данного подхода известна давно, но получил он признание сравнительно недавно в основном через работы [Hutter, 2001], [Schmidhuber, 2003] и другие работы этих авторов. В его рамках основной упор делается на модели универсальной индукции Соломонова, включенные в систему выбора действий в окружающей среде для максимизации некоторой оценивающей функции. Здесь анализ начинается с простой универсальной модели, на которую не накладываются ресурсные ограничения. Первый шаг подхода аналогичен, так как можно предположить, что свойство универсальности крайне желательно сразу вводить в модель универсального ИИ и поддерживать сохранение этого свойства при развитии модели, которое осуществляется путем ввода ресурсных ограничений. В современных версиях рассматриваемых подходов ресурсные ограничения также вводятся, но с сохранением максимальной непредвзятости универсального ИИ, что позволяет строить общие модели самооптимизации. Такой учет ограничений на ресурсы, однако, не вполне достаточен. Можно сказать, что он требует воспроизводства целиком эволюции, которая также начиналась как универсальный самооптимизирующийся поиск без какой-либо априорной информации. Очевидно, чтобы становление подобного универсального интеллекта могло быть осуществлено за обозримое время, необходимо в него закладывать как достаточно большой объем априорной информации о структуре внешнего мира, так и эвристики для сокращения перебора вариантов моделей и действий. Эти эвристики как раз можно почерпнуть из феноменологии когнитивных функций естественного интеллекта. С другой стороны, в сильный ИИ нерационально вручную закладывать слишком большой объем специфичных знаний, которые он может почерпнуть самостоятельно. Очевидно, необходимо достижение оптимального компромисса между этими двумя крайностями. Помимо этого, отдельный вопрос для обсуждения заключается в том, а действительно ли представленные модели являются универсальными. Для этого необходимо тщательно сравнить гипотетические возможности этих моделей с возможностями человека. Отчасти такие сравнения проводятся (например, [Hutter, 2005]), хотя их нельзя назвать бесспорными или исчерпывающими. Тем не менее, сомнения в действительной универсальности этих моделей вполне можно выдвинуть, что будет показано при анализе нашей собственной модели универсального алгоритмического интеллекта. Сейчас можно отметить лишь одно из таких сомнений, которое заключается в том, что интеллект лишь в нулевом приближении можно свести к максимизации априорно заданной целевой функции. Ведь если, скажем, задача интеллекта заключается в обеспечении выживания, то априорно заданная целевая функция (базирующаяся, скажем, на эмоциональных оценках) может быть лишь грубой эвристической аппроксимацией цели выживания. Это означает необходимость существования специальных механизмов, позволяющих каким-то образом уточнять целевую функцию в онтогенезе. Здесь можно привести следующую аналогию с шахматами. Пусть один интеллектуальный агент может сыграть только одну партию. Имея ограниченные вычислительные ресурсы, он не может осуществить полный перебор вариантов, чтобы предсказать победу или поражение. Рождаясь с минимумом априорных знаний о мире, он не может иметь сложную целевую функцию, которая бы позволяла эффективно отсекать неперспективные варианты на дереве игры. Исходная целевая функция может опираться лишь на какие-то непосредственно воспринимаемые стимулы, скажем на суммарную силу фигур (дающую ощущение боли и удовольствия при потере своей фигуры или съедении фигуры соперника). В процессе взросления (игры) агент может построить более сложные понятия, но самостоятельно (не прожив жизнь целиком) он в принципе не сможет определить, как на основе этих понятий можно улучшить целевую функцию. Эту информацию ему, однако, могут дать другие агенты, но только при условии, что имеется некий хороший механизм модификации целевой функции. Этот аспект имеет отношение и к проблеме дружественного ИИ…

Подход на основе обучения целевым функциям.

Проблема обучения целевым функциям иногда рассматривается в качестве основополагающей при построении сильного ИИ (или, точнее, дружественного ИИ [Yudkowsky, 2011]). В рамках этого подхода совершенно справедливо замечается, что максимизация априорной целевой функции недостаточна для того, чтобы искусственный интеллект оказался универсальным, особенно, в части эффективного (и желаемого) взаимодействия с социальным окружением, которое является таким же элементом объективной реальности, как и физическое окружение. Проблема наделения ИИ способностью к модификации собственной целевой функции нетривиальна в силу того, что не ясно, как целевая функция может оптимизироваться, если не под управлением другой целевой функции (или каких-то других априорных механизмов). Важность возможности модификации целевой функции связана не только с тем, что это необходимо для полноценной универсальности агента, но и с тем, что ИИ, стремящийся к максимизации априорной целевой функции, вполне может найти такие действия, оптимальные с точки зрения этой функции, которые окажутся крайне нежелательными для людей [Yudkowsky, 2011]. Хотя важность этих аспектов бесспорна, их рассмотрение вне конкретных моделей универсального интеллекта не позволяет наметить путь создания сильного ИИ (а, скорее, задает некоторые ограничения на пути его создания), поэтому данный подход следует считать комплементарным другим подходам. Возможность модификации целевой функции необходимо предусмотреть в архитектуре универсального интеллектуального агента, хотя в целом это можно рассматривать на том же уровне, что и другие когнитивные функции, а именно, как специфическую эвристику повышения эффективности развития «младенческого» ИИ до уровня «взрослого» ИИ.

Адаптивное поведение, самоорганизация и бионика в целом.

Существует большое направление исследований в области сильного ИИ, связанное с бионическим подходом. Здесь выделяются попытки (см., напр., [Garis, 2007] [Red’ko, 2007]) моделирования мозга на разных уровнях детальности, воспроизведения адаптивного поведения, начиная с простейших его форм к более сложным, моделирования эволюции, самоорганизации в целом. Зачастую этот подход носит имитационный характер и достаточно жестко противопоставляется алгоритмическому подходу, из-за чего оказывается недостаточно глубоким. В частности, разные имитационные модели эволюции и самоорганизации не приводят к неограниченному развитию по той простой причине, что их авторы даже не пытаются рассматривать вопросы, связанные с вычислительной сложностью решаемых оптимизационных проблем и алгоритмической полнотой тех форм поведения, которые в принципе могут получиться в ходе этого моделирования. Из-за этого весьма сомнительно, что бионический подход сам по себе может привести к созданию сильного ИИ. Однако в то же время он может служить важным источником продуктивных идей, пренебрегать которым было бы слишком расточительно.

Результаты исследования

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

Алгоритмы поиска пути

Существует немало методов нахождения пути между двумя вершинами графа. Одним из самых распространенных является алгоритм Дейкстры. Позднее была придумана модификация данного алгоритма. Им стал алгоритм А* (А стар), алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).

Рисунок 1 – Пример поиска с использованием алгоритма А* (анимация: объем – 58.2 КБайт, количество кадров – 25, размер – 280 х 285)

В 2011 году был представлен алгоритм Jump Point Search. Этот алгоритм является улучшенным алгоритмом поиска пути A*. JPS ускоряет поиск пути, “перепрыгивая” многие места, которые должны быть просмотрены. В отличие от подобных алгоритмов JPS не требует предварительной обработки и дополнительных затрат памяти.

Рисунок 2 – Схематическая схема работы алгоритма Jump Point Search

Алгоритм работает на неориентированном графе единой стоимости. Каждое поле карты имеет <= 8 соседей, которые могут быть проходимы или же нет. Каждый шаг по направлению (по вертикали или по горизонтали) имеет стоимость 1; шаг по диагонали имеет стоимость корень из 2. Движения через препятствия запрещены. Обозначение относится к одному из восьми направлений движения (вверх, вниз, влево и т.д.).

• Запись y = x + kd означает, что точка y может быть достигнута через k шагов из x в направлении d. Когда d – движение по диагонали, перемещение делится на два перемещения по прямой d1 и d2.
• Путь p = (n0, n1, …, nk) – упорядоченное перемещение по точкам без циклов из точки n0 до точки nk.
• Обозначение p \ x означает, что точка x не встречается на пути p.
• Обозначение len(p) означает длину или стоимость пути p.
• Обозначение dist(x, y) означает длину или стоимость пути между точками x и y.

Jump points

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

Рисунок 3 - Отсеченный сосед

Рисунок 4 – Принужденный сосед

Пример работы алгоритма Jump Point Search

Здесь добавляется точка x для рассмотрения, предком которой является p(x); направление движение от p(x) к x является прямолинейное перемещение вправо. (Левая картинка): Рекурсивно применяем правило отсечки и получаем у в качестве преемника прыжковой точки х. Эта точка интересна тем, что есть сосед z, в который можно попасть по оптимальному пути только через y. Промежуточные точки не генерируются и не рассматриваются. (Правая картинка): Рекурсивно принимаем диагональные правила отсечки. Обратите внимание, что перед каждым следующим диагональным шагом необходимо рекурсивно пройтись по прямым линиям (выделены пунктиром). Только если обе “прямые” рекурсии не могут определить точку следующего прыжка, то перемещаемся дальше по диагонали. Точка w – вынужденный сосед х, создаётся как обычный.

Рисунок 5 – Пример работы алгоритма Jump Point Search

Результаты применения исследуемой архитектуры в простейшем игровом симуляторе

Для исследования возможностей предложенной архитектуры была разработан простейший симулятор игрового мира, в котором на игровом поле размещаются агенты и «пища». Целью каждого агента является сборка максимального количества «пищи». При этом область карты, видимая агентом, ограничена. Помимо агентов и пищи на карте располагаются препятствия (черные квадраты). Как только вся «пища» на игровой карте собрана, игра заканчивается. Игроку-человеку предоставляется возможность управления одним из агентов. Игра случайным образом располагает агентов и «пищу» на игровом поле, и на каждой игровой итерации опрашивает агентов об их следующем шаге, затем перерисовывает игровое поле. Агент, получая право сделать движение, обновляет свою видимую зону игрового поля, затем вызывает принятие решения подсистемой ИИ. ИИ запрашивает у агента эффективность перехода в каждом из направлений. Значение функции тем выше, чем ближе к агенту «пища» после совершения хода в данном направлении. Причём близость рассматривается с учетом поиска пути до цели (использовался алгоритм Jump Point Search[4]) и возможностей для видимых объектов добраться до «пищи» за меньшее количество ходов. Таким образом, выбрав экстремум из всех значений, определяется следующий ход. Если же агент находится в открытой местности, где в поле видимости нет целей, то принимается случайное направление, но при этом учитываются предыдущие ходы агента, чтобы он не двигался по замкнутой траектории. На рис. 6 представлена экранная форма игры. Красными точками на ней изображены агенты, синими – ресурсы («пища»), поедаемые ими. А серыми рамками обведены области, которые видимы агентам.

Рисунок 6 – Экранная форма игрового процесса

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

Выводы

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

Список литературы

• Bandi, S., Cavazza, M., and Palmer, I. “Situated AI in Video Games”. / S. Bandi : University of Branford
• Ножов И.М. Практическое применение искусственного интеллекта в компьютерных играх / Ножов И.М. – М. : РГГУ, 2008. – 140 с.
• Портал искусственного интеллекта [Электронный ресурс]. – Режим доступу : http://www.aiportal.ru/
• Основы подхода к построению универсального интеллекта [Электронный ресурс]. – Режим доступу : http://habrahabr.ru/post/145467//
• Shortest path [Электронный ресурс]. – Режим доступу : http://harablog.wordpress.com/2011/09/07/jump-point-search//
• Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns / R. Helm, R. Johnson, J. Vlissides : Addison Wesley, 1994. – 416 с.
• Искусственный разум – принципиальная схема [Электронный ресурс]. – Режим доступу : http://habrahabr.ru/post/166333/
• Rabin S. AI Game Programming Wisdom / Rabin Steve : 2001. – 314c.
• Скатов Д.С. Искусственный интеллект/ Д.С. Скатов, В.В. Окатьев, Т.Е. Ратанова – Киев : Диктум, 2011. – 46 с.