Вступ

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

Ігровий штучний інтелект (англ. Game artificial intelligence) – набір програмних методик, які використовуються в комп'ютерних іграх для створення ілюзії інтелекту в поведінці персонажів, які керуються комп'ютером.

Ігровий ШІ, окрім методів традиційного штучного інтелекту, включає також алгоритми теорії управління, робототехніки, комп'ютерної графіки та інформатики в цілому.

Реалізація ШІ сильно впливає на ігровий процес, системні вимоги і бюджет гри. Розробники балансують між цими вимогами, намагаючись зробити цікавий і невимогливий до ресурсів ШІ малою ціною. Тому підхід до ігрового ШІ серйозно відрізняється від підходу до традиційного ШІ – широко застосовуються різного роду спрощення, обмани і емуляції. Наприклад, з одного боку, в шутерах від першої особи безпомилковий рух і миттєве прицілювання, притаманне ботам, не залишає жодного шансу людині, тому ці здібності штучно знижуються. З іншого боку – боти повинні робити засідки, діяти командою тощо, для цього застосовуються «милиці» у вигляді контрольних точок, розставлених на рівні.

Персонажі комп'ютерних ігор, що керуються ігровим штучним інтелектом, поділяються на:

-     неігрові персонажі (англ. Non-player character, NPC) – як правило, ці персонажі є дружніми або нейтральними до людського гравця.

-     боти (англ. Bot) – ворожі до гравця персонажі, що наближаються за можливостями до ігрового персонажу; проти гравця в будь-який конкретний момент грає невелика кількість ботів. Боти найбільш складні в програмуванні.

-     моби (англ. Mob) – ворожі до гравця «низько інтелектуальні» персонажі. Гравці вбивають мобів у великій кількості заради очок досвіду, артефактів або проходження території.

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

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

Постановка завдання

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

Методи пошуку екстремуму функцій

Градієнтний метод

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

-         додавання і віднімання;

-         множення на дійсне число u;

-         скалярний добуток.

Сукупність всіх таких векторів називають 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) називають вектор N f (V) з координатами, рівними окремим похідним за відповідними аргументами

Градієнт вказує напрямок найбільшого зростання функції. Протилежний напрямок – N f (V) називається антіградієнтом, він показує напрямок найшвидшого зменшення функції. У точці екстремуму V * градієнт дорівнює нулю N f (V *) = 0. Якщо аналітично похідні визначити неможливо, їх обчислюють наближено.

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

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

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

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

-          порівняльна простота логічної структури методу і, відповідно, програми для ЕОМ;

-          використовується порівняно невелика кількість заздалегідь встановлених параметрів;

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

 

Недоліки методу:

-        виникає проблема масштабування, оскільки всі координати вершин симплекса залежать від одного масштабного множника. Щоб уникнути такого роду проблем у практичних завданнях, слід промасштабувати всі змінні з тим, щоб їх значення були порівняні по величині;

-        алгоритм працює досить повільно, тому що отримана на попередніх ітераціях інформація не використовується для прискорення пошуку;

-             не існує простого способу розширення симплекса. Потрібен перерахунок значень цільової функції у всіх точках зразка.

Метод сполучених напрямків Пауелла

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

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

Крок 1. задати вихідні точки х₁, х₂ і напрям d. Зокрема, напрям d може співпадати з напрямом координатної вісі;

Крок 2. провести одновимірний пошук з точки х₁ в напрямку d і отримати точку у1, що є точкою екстремуму на заданому напрямку;

Крок 3. провести пошук з точки х₂ в напрямку d і отримати точку у₂;

Крок 4. обчислити напрямок (у₂ - у₁);

Крок 5. провести одновимірний пошук з точки у₁ (або у₂) в напрямку (у₂ - у₁) з виходом в точку х*.

Проектування системи штучного інтелекту

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

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

Чим вище пріоритет, тим важливіше завдання і тим вища ймовірність того, що дії, необхідні для його досягнення, будуть виконані в першу чергу.

Для простоти припустимо, що в одну одиницю часу агент може виконувати тільки одну дію. Для кожного завдання така дія володіє деяким показником ефективності:

Обчислення даного показника може бути виконано різними способами залежно від типу дії та особливостей предметної області, для якої розробляється гра.

Таким чином, в кожну одиницю часу можна оцінити ефективність виконання кожної з дій d,які доступні агенту:

Для досягнення максимальної ефективності агента необхідно в кожну одиницю часу виконувати найбільш ефективну дію: