Кваліфікаційна роботапояснювальна записка сторінка 2

15
- штучний інтелект досить складно інтерпретувати, ігровий досвід зберігається у формі ваг в агенті нейронної мережі;
- потребує значних ресурсів відеокарти для навчання нейронної
мережі;
- вимагає значну кількість симуляцій для отримання результату.
1.3 Існуючі реалізації адаптивного ігрового штучного інтелекту
Досліджено існуючі реалізації ігрового штучного інтелекту для ігри
«Змійка». Можливо виділити загальні характеристики, що притаманні
розглянутим реалізаціям [7, 13, 26]:
- модель для навчання ігрового адаптивного агенту;
- баланс між дослідженням та використанням;
- використовувана евристика;
- аналіз планованих дій с точки зору їх прийнятності;
- функція оцінки;
- використання засобів програмування.
Серед моделей для навчання ігрового адаптивного агенту для ігри
«Змійка» найбільш популярним підходом є використання нейронних мереж,
які побудовані на основі згорткових нейронних шарів, наприклад, з
інтеграцією торусної згортки. Ця модель здатна показувати кращий результат по загальній метриці власника змагань порівняно з іншими аналогами які
використовують згорткові ШНМ [26].
При виборі політики ігрового штучного інтелекту існуючі реалізації
використовують наступні підходи [26]: жадібний (greedy), жадібний зі
схильністю використовувати ризик (risk averse greedy), прямий агент, прямий агент зі схильністю не ризикувати.
Поширеною практикою при розробці агентів є використання різноманітних евристик. Наприклад, провести гру власного ігрового агенту зі
трьома іншими, що змусить власного агенту уникати зіткнень з іншими

16
агентами одночасно. Під час гри декількох сторонніх агентів, основний агент здатний взаємодіяти з іншими та вчитися з урахуванням їх поведінки. Також особливістю евристики являється переймання досвіду для головного агенту від других агентів з точки зору максимізації кількості набраних балів під час
ігрової сесії.
Наприклад, якщо сторонні агенти мають схильність на ризик (у балансі
між дослідженням та використанням) і здатні швидко максимізувати кількість балів шляхом швидкого збирання фруктів, головний агент також буде переймати отриманий досвід. Головним недоліком даної евристики являється використання значних комп’ютерних ресурсів для навчання головного агенту, так як переймання досвіду від інших агентів потребує
значної кількості зіграних ігор [26]. Ще однією евристикою є використання алгоритму заливки (Flood fill) [26]. Це алгоритм, який враховує, наскільки далеко предмети чи гравці находяться від ігрового агенту.
При виборі варіантів майбутніх дій агенту, доцільним є прогнозування на декілька кроків уперед, з метою уникнення дій, які можуть призвести до погіршення загальної метрики під час виконання оптимізації та перенавчання. Щоб уникнути цього необхідно виконати фільтрацію небажаних кроків за допомогою алгоритму Monte-Carlo Search Tree [2].
У якості функції оцінки використана кількість балів, відповідно до числа зібраної їжі та часу присутності агенту на ігровому полі.
Більшість з
розглянутих реалізацій використовують мову програмування Python для створення агентів адаптивного ігрового штучного
інтелекту. Але реалізація Monte-Carlo Search Tree на мові програмування
Python являється ускладненою, тому особливістю розглянутих рішень є
реалізація цього алгоритму на мові програмування С++.
Розглянуті реалізації ігрового штучного інтелекту на основі таких підходів:
- на основі генетичних алгоритмів;
- на основі жадібної політики та згорткових ШНМ;

17
- на основі жадібної політики зі схильністю використовувати ризик та нейронної мережі на основі згорткових шарів;
- на основі жадібної політики та ШНМ на основі згорткових шарів у вигляді торуса та використання Flood fill алгоритму.
Кожен із аналогів представлений як рішення до задачі, яка описана в змаганні на платформі Kaggle (таблиця 1.1).
Таблиця 1.1 – Порівняльна таблиця існуючих рішень по створенню штучного
інтелекту для ігри «Змійка»
Назва рішення
Переваги
Недоліки
Ігровий штучний
інтелект на основі
генетичних алгоритмів
Простота реалізації.
Ефективність роботи при невеликій кількості
об’єктів
Невелика тривалість життя
Ігровий штучний
інтелект на основі
жадної політики та
ШНМ на основі
згорткових шарів
Агент здатен уникати колізій на протязі
більшого часу, у порівнянні з аналогами.
Алгоритм здатний збирати фрукти та не закінчувати гру на протязі 200 кроків
Великий час тренування моделі.
Середня здатність збирання фруктів під час ігрової сесії
порівняно із аналогами
Ігровий штучний
інтелект на основі
жадібної політики зі
схильністю використовувати ризик та ШНМ на основі
згорткових шарів
Ефективний алгоритм,
що дозволяє швидко збирати фрукти,
порівняно з аналогами.
Це надає можливість мати високий рахунок на початку гри
Невелика тривалість життя агенту

18
Продовження таблиці 1.1
Ігровий штучний
інтелект на основі
жадібної політики та нейронної мережі на основі згорткових шарів у вигліді
торуса та використання aлгориму Flood fill
Агент здатний уникати колізій на протязі великого проміжку часу порівняно з аналогами. Алгоритм здатний збирати фрукти та не закінчувати гру на протязі 230 кроків
Має більшу схильність до збору фруктів, ніж жадібний алгоритм
Значний час тренування моделі.
Найбільш поширеними недоліками аналогів є великий час тренування та дисбаланс між пошуком фруктів та часом життя «Змійки». Щоб зменшити дисбаланс вибору рішення, доречно використання ансамбль моделей:
штучний інтелект на основі жадної політики та згорткової штучної нейронної
мережі та моделі на основі жадної політики та штучної нейронної мережі на основі згорткових шарів у вигляді торуса та використання алгоритму Flood fill.
1.4 Постановка задачі
Метою та завданням кваліфікаційної роботи
є розробка демонстраційної комп’ютерної програми, яка містить в собі гру «Змійка» та агентів, побудованих на основі динамічного ігрового штучного інтелекту використовуючи навчання з підкріпленням та глибині нейронні мережі.
Агент повинен вчитися на основі попереднього досвіду і демонструвати результат під час гри с користувачем.
Досягнення поставленої мети можливе завдяки вирішенню наступних задач:

19
Аналіз предметної області. Потрібно дослідити базові принципи побудови ігор та створення для них штучного інтелекту. Також необхідно дослідити сучасні алгоритми динамічного навчання агентів. Це можливо виконати за допомогою Deep Q-Learning моделей та Monte-Carlo Search Tree.
Потрібно виконати дослідження використання функції по пеналізацізації на основі видалення нейронів за допомогою гаусового підходу [20].
Створення ігрового середовища для ігри «Змійка». Середовище повинне мати поле, яке може містити до 5 агентів одночасно, виключаючи головного гравця. Ігрове середовище повинне повністю повторювати правила, які використовуються в традиційній ігри. Середовище повинне бути використане з платформи Kaggle [8].
Агент повинен використати підхід до адаптації, побудований на основі
навчання з підкріпленням. Агент повинен використовувати Deep Q-Learning та Monte-Carlo search Tree [17].
Виконати тренування ігрового штучного інтелекту та налаштування кількості та видів нейронів для тренування. Штучний інтелект повинен виконувати прогнозування дій в реальному часі. Кількість шарів нейронної
мережі та їх види повинні бути задані самостійно.
Вибір найефективнішого агенту серед всіх можливих на основі функції
винагороди.
Інтеграція штучного інтелекту в ігрове середовище. Середовище повинне мати підтримку роботи багатьох агентів одночасно і слідувати за правилами ігри «Змійка».
Демонстрація роботи багатьох агентів під час однієї ігрової сесії.
Результатом роботи повинен стати прототип гри з ігровим середовищем та багатьма агентами, які можуть грати одночасно в полі з другими агентами.
Агенти повинні не закінчувати гру в короткий час, а забезпечити можливість того, щоб одна партія продовжувалась не менше 30 секунд.

20 2 ТЕХНОЛОГІЇ ТА МЕТОДИ ВИРІШЕННЯ ПОСТАВЛЕНОЇ ЗАДАЧІ
2.1 Опис методології CRISP-DM
Якість виконання проекту залежить від методології обраного процесу.
При розробці ігрового агенту використовується методологію CRISP-DM.
CRISP-DM [27] – це міжгалузевий процес аналізу даних. Методика CRISP-
DM забезпечує структурований підхід до планування проекту. Переваги цієї
методики в представленні чіткої послідовності дій, необхідних для створення успішного проекту.
Методологія CRISP-DM описується з точки зору ієрархічної моделі
процесу, що включає чотири рівні абстракції (від загального до конкретного):
фази (phases), загальні завдання (generic tasks), спеціалізовані завдання
(specialized tasks) та екземпляри процесу (process instances).
На найвищому рівні процес передачі даних організований у невелику кількість фаз. Кожна фаза складається з декількох загальних завдань другого рівня. Загальні завдання необхідно створювати таким чином, щоб вони були завершеними і стабільними. Завершеними завданнями вважаються завдання,
які покривають процес аналізу даних та всі можливі дані. Стабільними вважаються завданнями, при яких модель буде валідною при інтеграції нових видів моделей в ансамбль.
Життєвий цикл проекту складається з таких компонентів (рисунок 2.1):
- дослідження бізнес-області замовника;
- дослідження наявних даних;
- підготовка даних;
- створення моделей машинного навчання;
- оцінка результатів моделі на основі кросс-валідації та тестового датасету;
- публікація створеного алгоритму до програмного середовища.

21
Рисунок 2.1 – Життєвий цикл розробки проекту при використанні
методології CRISP-DM
Розглянуто детальний опис кожного кроку в життєвому циклі розробки при використанні методології CRISP-DM (рисунок 2.1).
Дослідження бізнес-області замовника. Це початковий етап, що спрямований на розуміння цілей та вимог проекту з точки зору бізнесу і
використання цих знань у визначення проблем аналізу даних та створення відповідного плану до проекту.
Дослідження наявних даних. Етап дослідження наявних даних починається зі збору даних та супроводжується такими процесами, як ознайомлення з даними, виявлення проблем з якістю даних, виконання початкового аналізу даних або виявлення фактів для формування гіпотез щодо прихованої інформації. Для формулювання проблеми аналізу даних та плану проекту необхідно обов’язково проводити дослідження наявних даних.
Підготовка даних. Етап підготовки даних охоплює створення кінцевого набору даних (дані, які будуть передані для тренування моделей, ансамблей,
проведення оцінки ефективності моделей на основі кросс-валідації,

22
проведення оцінки ефективності яка показує контрольний результат ефективності моделі) з необроблених даних. Завдання з підготовки даних,
виконується декілька разів, але не обов’язково в установленому порядку.
Завданнями підготовки даних є:
- вибір датасетів (наборів даних) для обробки даних;
- трансформація табличних значень;
- очищення даних від порожніх рядків, колонок, аномалій;
- створення нових атрибутів на основі бізнес аналізу області
використання даних замовника;
- трансформація даних для моделей, які будуть використовуватися.
Для лінійних моделей та нейронних мереж необхідно конвертувати дані за допомогою нормалізації;
- створення моделей машинного навчання;
- оцінка результатів моделі на основі кросс-валідації та тестового датасету;
- публікація створеного алгоритму до програмного середовища;
- отримані результати потрібно буде організувати та представити таким чином, щоб замовник міг ним скористатися.
2.2 Reinforcement learning
Reinforcement learning (RL) – це область машинного навчання, яка визначає, як агенти повинні сприймати дії в середовищі, щоб максимально розширити уявлення про сукупну винагороду [5].
Reinforcement learning передбачає навчання без вчителя з діями, щоб максимізувати винагороду. Це є проблемою замкнутого циклу, оскільки система навчання впливає на наступні результати. Агенту не повідомляється,
які дії він має вчинити, як у поширених формах машинного навчання. Агент повинен виконати дослідження, які дії приносять найбільшу винагороду,
випробовуючи їх. В складних випадках дії можуть вплинути не тільки на

23
винагороду, а й на наступну ситуацію і, відповідно, на всі наступні
винагороди. Агент немає прямих вказівок щодо того, які дії слід вжити, і які
наслідки цих дій, включаючи розмір винагороди, відтвореного протягом тривалого періоду часу.
Одна з проблем, що виникає у процесі reinforcement learning – це компроміс між дослідженням та експлуатацією [6]. Щоб отримати велику винагороду, підкріплюючий навчальний агент повинен віддавати перевагу діям, які він пробував в минулому і виявив свою ефективність в отриманні
винагороди. Але щоб виявити такі дії, він повинен спробувати дії, які він не вибрав раніше. Агент повинен використовувати те, що він уже знає, щоб отримати винагороду, але він також має досліджувати, щоб краще вибирати дії на майбутнє. Дилема полягає в тому, що ні розвідки, ні експлуатації не може бути виконано виключно без помилок у виконанні завдання. Агент повинен спробувати різні дії і поступово віддавати перевагу тим, які
здаються найкращими. В стохастичному завданні, кожну дію потрібно виконати багато разів, щоб отримати достовірну оцінку. Дилема «розвідка- експлуатація»
вивчалася математиками протягом багатьох десятиліть.
Проблема балансування розвідки та експлуатації не виникає в supervise і
unsupervised навчанні [6].
Ще однією ключовою особливістю навчання з підкріпленням є те, що враховується вся проблема взаємодії цільового агенту з невизначеним середовищем. Розроблені теорії планування з загальної цілі, але без урахування ролі планування у прийнятті рішень у реальному часі, або питання про те, у яких випадках прогнозувальні моделі необхідні для планування. Хоча ці підходи дали багато корисних результатів, їх зосередження на окремих підпроблемах є суттєвим обмеженням [10].
Навчання з підкріпленням пропонує адаптивний агент. Усі агенти навчання з підкріпленням мають явні цілі, які можуть використовувати аспекти свого оточення та обирати дії, щоб впливати на своє оточення. Агент повинен діяти, незважаючи на значну невизначеність середовища, з якою він

24
стикається. Коли навчання з підкріпленням передбачає планування, воно має
бути спрямоване на взаємодію між плануванням і вибором дій у реальному часі та врахуванням як вдосконалюються модель середовища. Коли навчання з підкріпленням передбачає supervised learning (навчання з вчителем), це відбувається з визначенням того, які можливості є критичними.
Навчання з підкріпленням також є частиною сучасної тенденції у штучному інтелекту до використання простих загальних принципів [12]. Слід прийняти, що інтелект натомість пояснюється володінням величезною кількістю процедур та евристик спеціального призначення. Методи,
засновані на загальних принципах, такі як пошук або навчання,
характеризувалися «слабкими методами», тоді як ті, що базуються на конкретних знаннях, називалися «сильними методами». Сучасний AI тепер включає багато досліджень, які шукають загальні принципи навчання,
пошуку та прийняття рішень, а також намагаються включити величезну кількість знань у цій галузі.
2.3 Q-learning
Q-learning – це алгоритм навчання з model-free підкріплення. «Q» у Q- learning означає якість, яка показує, наскільки корисна дана дія для отримання певної майбутньої винагороди.
Q-learning є алгоритмом value-based навчання [14]. Алгоритми на value- based оновлюють функцію значення на основі рівняння (зокрема рівняння
Беллмана). Алгоритми policy-based оцінюють значення функції за допомогою жадібної політики, отриманої з останнього оновлення політики.
Q-learning – це off-policy алгоритм. Це означає, що він дізнається значення оптимальної політики незалежно від дій агенту. З іншого боку, on- policy learner дізнається значення політики, яку виконує агент, включаючи етапи дослідження, і він знайде політику, яка є оптимальною, враховуючи дослідження, притаманне цій політиці [15, 15, 22].

25
Q*(s, a) – очікувана вартість (сукупна дисконтована винагорода)
виконання дії a в стані s і подальшого дотримання оптимальної політики.
Q-learning Temporal Differences (TD) для оцінки значення Q*(s, a).
Temporal Differences визначає, що агент навчається з середовища через епізоди без попереднього знання середовища.
Q-функція використовує рівняння Беллмана і приймає два вхідні
характеристики: стан (s) і дію (a) (рисунок 2.2).
Рисунок 2.2 – Рівняння Белмана
Алгоритм Q-learning у загальному випадку містить наступні етапи
(рисунок 2.3).
Рисунок 2.3 – Алгоритм роботи Q-Learning