Зміст:

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 с.