Українська   English
ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

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

Тем не менее, основное ограничение на ИИ для игр является быстродействие и требуемые ресурсы в процессе. Поэтому, в игровом ИИ основным принципом состоит в том, что поведение имитируется. Другими словами, ИИ для игр является более искусственным, нежели интеллектом. Система ИИ может быть крайне проста и представлять собой набор правил или же может быть довольно сложной и выполнять роль командующего армии противника, с которой предстоит сражаться игроку [2].

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

Генетические алгоритмы (ГА) – это адаптивные методы поиска, которые в последнее время используются для решения задач оптимизации. В них используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде и основные понятия линейной алгебры. Предложенные сравнительно недавно – в 1975 году – Джоном Холландом [4] генетические алгоритмы основаны на принципах естественного отбора Ч. Дарвина. ГА относятся к стохастическим методам. Эти алгоритмы успешно применяются в различных областях деятельности (экономика, физика, технические науки и т.п.) [3].

1. Актуальность темы

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

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

2. Цели и задачи исследования

Целью данной магистерской диссертации является применение генетического алгоритма для создания игрового искусственного интеллекта, модификации генетического алгоритма и определение эффективности использования ГА для данной задачи на платформе игры жанра ККИ. Из задач можно выделить:

  1. Исследование ГА и выбор операторов с их последующими модификациями.
  2. Разработка игрового ИИ для платформы ККИ Dual choice на основе ГА.
  3. Разработка функций эффективности для функциональных генов (карт и способностей).
  4. Сравнение скорости и эффективности принятия решений ИИ на основе ГА и полного перебора.
  5. Путем динамической настройки ГА создать возможность выбора сложности ИИ.

3. Обзор исследований и разработок по теме

Существует в мире уже огромное количество модификаций генетических алгоритмов. Но каноничная схема его работы выглядит как представлено на рис. 1.

Блок-схема ГА

Рисунок 1 – Блок-схема работы каноничного генетического алгоритма

3.1 Обзор международных источников

Исследования генетического алгоритма началось уже давно и в последнее десятилетие ведутся каждым автором в разном направлении. Для ознакомления подробно и одновременно в общем плане можно выделить иностранного автора Митчелла Мелани в его книгах [8].

Если требуется ознакомиться только с базовыми понятиями ГА, то в этом может помочь статья Милены Богданович с названием On Some Basic Concepts of Genetic Algorithms as a Meta-Heuristic Method for Solving of Optimization Problems [6]. В данной статье освещены операторы ГА и их наиболее часто применимые модификации.

3.2 Обзор национальных источников

В учебном пособии Генетические алгоритмы автора Т.В. Панченко [3] ГА раскрыт подробно, а материал в нем предназначен для студентов старших курсов. Книга содержательна, насыщена большим количеством понятий, имеет как задания, так и решения на некоторые из них.

Для реализации ГА существует гибкая библиотека Genetic для языка программирования C# [5]. Она имеет необходимые операторы и по инструкции можно создавать различные варианты реализации ГА. Данная библиотека в базовом виде пригодится для реализации задач без привязки к другим алгоритмам.

Что касается игровых ИИ в целом, то универсальных алгоритмов создания их не существует. К примеру, в книге Алекса Дж. Шампандара Искусственный интеллект в компьютерных играх познакомит с принципами ввода в компьютерную игру синтетических игровых персонажей с реалистичными формами поведения [7].

3.3 Обзор локальных источников

Исследования в рамках генетического алгоритма в нашем университете проводят магистры. Так Трубаров А.А. в своей магистерской проводит исследования в сфере организации обучения нейронных сетей с помощью генетического алгоритма оптимизации [9]. Также Боровик В.В. проводит в своей работе исследования параллельного генетического алгоритма для решения задачи коммивояжера [11].

Изучением методов построения игрового искусственного интеллекта и разработка информационной технологии для ее реализации в пошаговых стратегиях занимается в своей работе Буга К.В. [10].

4. Собственные результаты

Изначально для бакалаврской работы была разработана игра жанра ККИ Dual choice. Внешний вид прототипа и эффектов можно увидеть на рис.2.

Скриншот игрового приложения

Рисунок 2 – Прототип коллекционно карточной игры Dual choice

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

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

Использовался генотип всего с 2 генами с возможными 30 их вариантами. Каждый ген выступает в виде действия ИИ (выбор карты). Положение гена в генотипе также изменяет его значение функции эффективности. При полном переборе будет всего 30*30=900 вариантов, а значит столько же возможных вычислений функций генов. Каждое вычисление функции занимает некоторое время, а если их слишком много – это время продолжительное, что для игрового ИИ неприемлемо.

В тестовой программе выбираем простые операторы:

  1. Мутация – 30% шанс изменить случайный ген в генотипе на случайный другой.
  2. Скрещивание (кроссовер) – одноточечный кроссовер.
  3. Селекция – выбор лучше приспособленных генотипов.

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

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

Популяция Кол. шагов Улучшение в быстродействии (%) Ухудшение в эффективности (%)
20107142,5
20106524.1
14147702
14148225
10209599
10208916
Среднее: 801Среднее: 4,77

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

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

5. Исследование внедрения модификации генетического алгоритма в ИИ

Работа измененного ГА упрощенно можно представить в анимации ниже. Формирование случайным образом особей и проводим некоторое количество итераций. K и D выступают в виде некоторых действий ИИ. K – разыгрывания определенной карты с индексом i или j, а D – это использование активной способности карты. Количество D может варьироваться от количества карт на столе с активными способностями.

Рисунок 3 – упрощенная работа ГА для данной задачи
(Анимация: 700 кадров, бесконечный цикл повторения с возможностью остановки и продолжения, 32 килобайта)

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

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

Формула 1

где A – атака карты; H – здоровье карты; C – стоимость карты.

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

Vanilla test должен применяться к картам существам и с картами заклинаний обстоят дела по-другому. Эффективность для заклинаний, которые наносят урон либо исцеляют, можно определить как:

Формула 2

где R – количественное влияние карты; a – коэффициент значимости; C – стоимость карты.

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

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

Формула 3

где AA – функция расчета полезности активной способности; PA – функция расчета полезности пассивной способности.

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

Функция активных способностей берет в приоритет количество маны стихии, у которой она берет заем способностью. Механика игры подразумевает, что если запаса маны не хватает у игрока, то существо берет ее извне. Этот источник неограничен, но позволяет игроку опираться на тактику не жертвования своих сил и вызывать существ впритык к своим ресурсам. Не менее важным является и результат применения способности. Способность поменять одну единицу запаса очков стихии на другую является не особо выгодно в некоторых моментах (если конечно игрок был на нуле и не потратил ничего из своего резерва), а значит и функция будет иметь смысл как AA->max. Стоит отметить, что данный расчет ведется на ход вызванного существа и высчитывается динамически.

Дальнейшие исследования будут проводиться в магистерской работе и данный обзор показывает лишь базовую опору, на которую будет ориентироваться ИИ игры Dual choice

Выводы

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

Другой важнейшей причиной использования ГА является значительное уменьшение использования ресурсов и времени вычисления хода ИИ. Исследования и получение предварительных результатов дали понять в целесообразности его использования.

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

  1. Описание и игры в жанре Карточная стратегия (ККИ) // Apptime Games and Gadget – Режим доступа : https://app-time.ru/spravochnik-igrovyih-mobilnyih-zhanrov... .
  2. Создание искусственного интеллекта для игр // Intel Software – Режим доступа : https://software.intel.com/ru-ru/articles/designing... .
  3. Панченко, Т. В. Генетические алгоритмы: учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. – Астрахань : Издательский дом Астраханский университет, 2007. – 87 с.
  4. Holland J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence. – Cambridge : The MIT Press, 1992. – 194 p.
  5. Библиотека для реализации генетических алгоритмов в .NET Framework 2.0 // jenyay.net – Режим доступа : http://jenyay.net/Programming/Genetic .
  6. Bogdanovic M. On Some Basic Concepts of Genetic Algorithms as a Meta-Heuristic Method for Solving of Optimization Problems // Journal of Software Engineering and Applications, 2011. – 4. – P. 482-486.
  7. Шампандар Алекс Дж. Искусственный интеллект в компьютерных играх: как обучить виртуальные персонажи реагировать на внешние воздействия / пер. с англ. – М. : Издательский дом Вильямс, 2007. – 768 с.
  8. Уилкинсон Б. Основы проектирования цифровых схем. – М. : Издательский дом Вильямс, 2004. – 320 с.
  9. Трубаров А.А. Организация обучения нейронной сети с помощью генетического алгоритма оптимизации // Портал Магистров ДонНТУ, 2009. – Режим доступа : http://masters.donntu.ru/2009/fvti/trubarov/... .
  10. Буга К.В. Изучение методов построения игрового искусственного интеллекта и разработка информационной технологии для ее реализации в пошаговых стратегиях // Портал Магистров ДонНТУ, 2013г. – Режим доступа : http://masters.donntu.ru/2013/fknt/buga/... .
  11. Боровик В.В. Параллельный генетический алгоритм для решения задачи коммивояжера // Портал Магистров ДонНТУ, 2013. – Режим доступа : http://masters.donntu.ru/2013/fknt/borovyk/... .