Русский   English
ДонНТУ   Портал магістрів

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

Содержание

Введение

Ігрова індустрія зазнає бурхливе зростання в останні десятиліття. Продукти які створюють великі ігрові компанії показують, що створення ігор може виступати у вигляді деякого мистецтва. Комп'ютерні ігри дозволяють змагатися між гравцями або гравцями і комп'ютером. Комп'ютером в цьому випадку виступає ігровий штучний інтелект (ШІ). Основна роль він виконує це симуляція поведінки людини. Він може маскуватися під маскою людини, або виступати у вигляді простих ботів, у яких список програм сильно обмежений і примітивний. Завдання програмування других з'являється при створенні більшості ігрових проектів. Симуляція поведінки людини зазвичай є нетривіальним завданням. Але для тих і інших видів ШІ витрачається величезна кількість часу і ресурсів.

Проте, основне обмеження на ШІ для ігор є швидкодія і необхідні ресурси в процесі. Тому, в ігровому ШІ основним принципом полягає в тому, що поведінка імітується. Іншими словами, ШІ для ігор є більш штучним, ніж інтелектом. Система ШІ може бути вкрай проста і являти собою набір правил або ж може бути досить складною і виконувати роль командувача армії противника, з якою доведеться битися гравцеві [2].

У даній магістерській дисертації досліджується один з принципів створення ігрового ШІ для колекційної карткової гри. Колекційні карткові ігри – це один з жанрів комп'ютерних ігор, в яких мета полягає в накопиченні ігрових карт для подальшої гри ними з опонентом. В таких іграх поєднуються стратегічні елементи з елементами випадковості, і багато що залежить від тих карт, які потрапляють гравцеві, а також від того, як він зможе їх використовувати [1]. Підхід до створення ШІ обраний за допомогою генетичного алгоритму.

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

1. Актуальність теми

Генетичний алгоритм є одним з видів еволюційних алгоритмів. У канонічному вигляді даний алгоритм не використовують, а адаптують під умови поставленого завдання. Але загальні кроки алгоритму найчастіше залишаються незмінні. Генетичний алгоритм деякі відносять до розділу штучного інтелекту. Останнім часом ГА намагаються використовувати разом з нейронними мережами, а саме в навчанні тієї самої нейронної мережі.

На основі вищесказаного дана робота буде розглядати варіант побудови ігрового ШІ для протистояння з гравцем. Платформою для майбутніх досліджень виступає гра Dual choice, яка розроблена поки для гри на двох гравців. Відмінною рисою даної гри від інших представника жанру ККГ є обов'язковий розіграш двох карт за хід і не обов'язкове використання активних здібностей карт. Генетичний алгоритм допоможе ШІ вибрати цю комбінацію. Хоч дослідження і проводиться на вищевказаної платформі, її можна адаптувати до вирішення і інших завдань щодо прийняття рішень.

2. Мети і завдання дослідження

Метою даної магістерської дисертації є застосування генетичного алгоритму для створення ігрового штучного інтелекту, модифікації генетичного алгоритму та визначення ефективності використання ГА для даного завдання на платформі гри жанру ККГ. З завдань можна виділити:

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

3. Огляд досліджень і розробок на тему

Існує в світі вже величезна кількість модифікацій генетичних алгоритмів. Але канонічна схема його роботи виглядає як представлено на рис. 1.

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

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

3.1 Огляд міжнародних джерел

Дослідження генетичного алгоритму почалося вже давно і в останнє десятиліття ведуться кожним автором в різному напрямку. Для ознайомлення докладно і одночасно в загальному плані можна виділити іноземного автора Мiтчелла Меланi у його книгах [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].

Дослiдженням методів побудови ігрового штучного інтелекту і розробка інформаційної технології для її реалізації у покрокових стратегіях займається у своїй роботі Бугу К.В. [10]. [10].

4. Власні результати

Спочатку для бакалаврської роботи була розроблена гра жанру ККГ Dual choice. Зовнішній вигляд прототипу і ефектів можна побачити на рис.2.

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

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

Доки гра розрахована на двох гравців з передачею ходу. У даній роботі потрібно досліджувати і створити ігровий ШІ, щоб він міг замінити опонента.

Для початку потрібно знайти підхід до створення ШІ, досліджувати на доцільність його використання з подальшою реалізацією. Для цього розроблена спеціальна програма з дуже спрощеним варіантом подальшої реалізації ГА.

Використовувався генотип всього з 2 генами з можливими 30 їх варіантами. Кожен ген виступає у вигляді дії ШІ (вибір карти). Положення гена у генотипі також змінює його значення функції ефективності. При повному переборі буде всього 30 * 30 = 900 варіантів, а значить стільки ж можливих обчислень функцій генів. Кожне обчислення функції займає деякий час, а якщо їх занадто багато – це час тривалий, що для ігрового ШІ неприйнятно.

У тестовій програмі вибираємо прості оператори:

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

Задамо випадковим чином у інтервалі (0,2) вже розраховану підсумкову фітнес функцію для комбінації і також задамо випадкове час, за який вона у перший раз буде порахована. Використано псевдокешування функцій.

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

Популяцiя Кiл. кроків Поліпшення у швидкодії (%) Погіршення у ефективності (%)
20107142,5
20106524.1
14147702
14148225
10209599
10208916
Середнє: 801Середнє: 4,77

Згідно з попереднім експерименту подальше дослідження буде проводитися над ГА так, щоб підсумковий результат був приблизно таким же. При погіршенні ефективності менш 5% отримати збільшення швидкодії системи у 8 разів. Дана умова буде дотримуватися при кешуванні функцій.

Одним із завдань виступає налаштування складності ШІ. Даним методом можна створити імітацію складності ШІ шляхом налаштування кількістi кроків ітерацій, вибору популяції і, можливо, перевизначення деяких операторів ГА.

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 – функція розрахунку корисності пасивної здатності.

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

Функція активних здібностей бере в пріоритет кількість мани стихії, у якій вона бере позику здатністю. Механіка гри має на увазі, що якщо запасу мани не вистачає у гравця, то істота бере її ззовні. Це джерело необмежений, але дозволяє гравцеві спиратися на тактику не жертвування своїх сил і викликати істот впритул до своїх ресурсів. Не менше важливим є і результат застосування здатності. Здатність поміняти одну одиницю запасу очок стихії на іншу є не особливо вигідно в деяких моментах (якщо звичайно гравець був на нулі і не витратив нічого зі свого резерву), а значить і функція буде мати сенс як AAd-> 0. Варто зазначити, що даний розрахунок ведеться на хід викликаного істоти і вираховується динамічно.

Подальші дослідження будуть проводитися у магістерській роботі і даний огляд показує лише базову опору, на яку буде орієнтуватися ШІ гри 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/... .