6.4 Теорія ігор.

Тео́рія і́гор — теорія математичних моделей прийняття оптимальних рішень в умовах конфлікту. Оскільки сторони, що беруть участь в більшості конфліктів, зацікавлені в тому, щоб приховати від супротивника власні наміри, прийняття рішень в умовах конфлікту, зазвичай, відбувається в умовах невизначеності. Навпаки, фактор невизначеності можна інтерпретувати як противника суб'єкта, який приймає рішення (тим самим прийняття рішень в умовах невизначеності можна розуміти як прийняття рішень в умовах конфлікту). Зокрема, багато тверджень математичної статистики природнім чином формулюються як теоретико-ігрові.

Теорія ігор — розділ прикладної математики, який використовується в соціальних науках (найбільше в економіці), біології, політичних науках, комп'ютерних науках (головним чином для штучного інтелекту) і філософії. Теорія ігор намагається математично зафіксувати поведінку в стратегічних ситуаціях, в яких успіх суб'єкта, що робить вибір залежить від вибору інших учасників. Якщо спочатку розвивався аналіз ігор, в яких один із супротивників виграє за рахунок інших (ігри з нульовою сумою), то згодом почали розглядати широкий клас взаємодій, які були класифіковані за певними критеріями. На сьогоднішній день «теорія ігор щось на кшталт парасольки чи універсальної теорії для раціональної сторони соціальних наук, де соціальні можемо розуміти широко, включаючи як людських так не-людських гравців (комп'ютери, тварини, рослини)» (Роберт Ауманн, 1987)

7. Приклад.

Приклад побудови моделі динамічного програмування та прийняття рішення за результатами проведення тестів над побудованою моделю.

В якості прикладу була взята программа PathFinder. Припустимо, що ми програмуємо деяку комп'ютерну гру. Ігрове поле гри буде у вигляді графа. У грі будуть використовуватися алгоритми пошуку шляху. Існує велика кількість алгоритмів пошуку шляху, і не можна визначити який алгоритм буде кращим в тій чи іншій ситуації. У грі буде щонайменше 3 типових ситуації:

• Пошук шляху між двома вершинами графа в лабіринті - в даному випадку ігрове поле побудоване у вигляді лабіринту. Нам потрібно знайти найкоротший шлях між двома вершинами графа, які лежать на різних кінцях лабіринту.

• Пошук шляху між двома вершинами графа на відкритому полі - в ігровому полі незначна кількість перешкод.

• Пошук найближчих ресурсів - фінішна вершина не відома. Відомо лише, що вона знаходиться в деякому околі стартової вершини.

Дослідимо 4 алгоритми пошуку шляху:

1. алгоритм Дійкстри

2. алгоритм А*

3. хвильовий алгоритм

4. хвильовий* алгоритм

Середовище програми PathFinder дозволяє змоделювати кожну з цих типових ситуацій.

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

Лабіринт побудований у середовищі програми PathFinder

Результати наведені у таблиці:

Алгоритм	Знайдений шлях	Витрачений час
Алгоритм Дійкстри	Вірний	432 ум. одиниць часу
Алгоритм А*	Вірний	570 ум. одиниць часу
Хвильовий алгоритм	Не вірний	147 ум. одиниці часу
Хвильовий* Алгоритм	Вірний	370 ум. одиниць часу

Якщо побудувати граф без діагональних шляхів, в якому вартість проходження по всіх ребрах фіксована та однакова, то отримаємо наступні результати:

Алгоритм	Знайдений шлях	Витрачений час
Алгоритм Дійкстри	Вірний	426 ум. одиниць часу
Алгоритм А*	Вірний	553 ум. одиниць часу
Хвильовий алгоритм	Вірний	145 ум. одиниці часу
Хвильовий* Алгоритм	Вірний	266 ум. одиниць часу

Якщо побудувати поле без перешкод з ребрами фіксованої довжини, то отримаємо наступні результати:

Алгоритм	Знайдений шлях	Витрачений час
Алгоритм Дійкстри	Вірний	787 ум. одиниць часу
Алгоритм А*	Вірний	139 ум. одиниць часу
Хвильовий алгоритм	Вірний	161 ум. одиниці часу
Хвильовий* Алгоритм	Вірний	440 ум. одиниць часу

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

Алгоритм	Знайдений шлях	Витрачений час
Алгоритм Дійкстри	Вірний	788 ум. одиниць часу
Алгоритм А*	Вірний	114 ум. одиниць часу
Хвильовий алгоритм	Не вірний	163 ум. одиниці часу
Хвильовий* Алгоритм	Вірний	779 ум. одиниць часу

За результатами тестування моделі можна зробити наступні висновки:

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

Тому можна винести наступні рішення, котрі надалі використовувати при програмуванні гри:

1. На ігрових полях без великої кількості перешкод використовувати алгоритм А*.

2. У лабіринті, в залежності від типу ребер графа:

• Якщо ребра одиничної довжини - хвильовий алгоритм;

• Якщо переважна кількість ребер одиничної довжини, але є ребра не одиничної довжини - хвильовий* алгоритм;

• Якщо ребра довільної довжини - алгоритм Дійкстри.

3. Для пошуку ресурсів, в залежності від типу ребер графа:

• Якщо ребра одиничної довжини - хвильовий алгоритм;

• Якщо переважна кількість ребер одиничної довжини, але є ребра не одиничної довжини - хвильовий* алгоритм;

• Якщо ребра довільної довжини - алгоритм Дійкстри.

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