Презентація на тему:
Ігрові задачі

Тема №10 Ігрові задачі

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

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

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

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

Дерево аналізу кожна вершина відповідає позиції; корінь дерева відповідає позиції, яка аналізується; листки - завершальним позиціям; дуги відповідають ходам гравців. Точніше, якщо існує хід з позиції А до позиції В, то В є сином А.

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

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

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

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

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

Приклад: дерево гри 2 2 -24 17 1 -4 -8 35 -2

Аналіз дерева гри 2 2 -24 17 1 -4 -8 35 -2 2 17 -4 35 2 -4 2

Складність алгоритму Чому не всі ігри можуть бути успішно проаналізовані? Основна характеристика складності - кількість завершальних позицій, які аналізуються.

Оцінка складності мінімаксної процедури Якщо коефіцієнт розгалудження (кількість ходів з кожної позиції) дорівнює b, а глибина дерева аналізу (кількість півходів на кожному варіанті) дорівнює d, то потрібно проаналізувати bd завершальних позицій.

Обмеження глибини перебору Звичайний підхід, який дозволяє провести аналіз дерева за прийнятний час (хоч цей аналіз буде наближеним: він дозволяє отримати оптимальний варіант лише для усікненого дерева аналізу, а не для повного дерева аналізу). Ідея - обмежити кількість півходів у кожному варіанті, тобто припиняти аналіз, коли довжина варіанту стає більшою за задану величину d (наз. глибина перебору). Отже, до усікненого дерева аналізу включаються лише позиції, відстань від яких до кореня дерева аналізу не перевищує d. При невеликій глибині перебору (8-14 півходів) дерево гри в шахи скорочується до розміру, що є прийнятним для аналізу на сучасних комп’ютерах.

Горизонт: деякі визначення Горизонтом називається множина позицій, відстань від яких до кореня дерева аналізу точно дорівнює глибині перебору d. Ясно, що позиції, які лежать на горизонті, як правило, не є завершальними для повного дерева (хоча можуть виявитися такими). З іншого боку, не всі позиції, що є завершальними для усікненого дерева, лежать на горизонті. Абсолютно завершальними називатимемо позиції, в яких гра завершується, тобто позиції, завершальні для повного дерева аналізу. Відносно завершальними називатимемо позиції, які є завершальними для скороченого дерева гри, але не для повного дерева.

Статичні оціночні функції Основна проблема: для відносно завершальних позицій результат гри ще не є відомим. Тому замість функцій виграшу для оцінки таких позицій використовуються статичні оцінки, отримані на основі статичних оціночних функцій. Статичною оціночною функцією називається функція, яка залежить виключно від самої позиції та не враховує динаміки гри. Часто використовуються лінійні статичні оціночні функції: зважені суми значень факторів, які впливають на оцінку позиції. Статичні функції залежать від самої гри. Вони повинні бути підібрані належним чином. Існують підходи до автоматизованого підбору статичних оціночних функцій (приклад - програма Семюеля для гри в шашки; 1968 р).

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

Значення глибини перебору Як впливає глибина перебору на якість гри?

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

Альфа-бета-відтинання: формалізований опис Відтинанням у деякій вершині називається припинення аналізу цієї вершини разом з усіма її наступниками. Аналіз дерева схожий на базову мінімаксну процедуру, але з деякими змінами. З кожною вершиною пов’язується попередня оцінка, яка змінюється в ході аналізу. На початку роботи алгоритму попередня оцінка альфа-вершини дорівнює -∞; бета-вершини - +∞. Надалі попередня оцінка альфа-вершини може тільки зростати, бета-вершини - тільки зменшуватися. Оцінка вершини стає остаточною, коли проаналізовані всі її наступники або коли в цій вершині відбулося відтинання. Попередня оцінка альфа-вершини дорівнює максимумові з остаточних оцінок синів, бета-вершини - мінімумові. Вона переглядається щоразу, коли дочірня вершина набуде остаточної оцінки.

Правила відтинань Відтинання в альфа-вершині відбувається, коли попередня оцінка цієї вершини стає не меншою, ніж деякого бета-попередника цієї вершини. Відтинання в бета-вершині відбувається, коли попередня оцінка цієї вершини стає не більшою, ніж деякого альфа-попередника цієї вершини. Варіант: не будь-якого бета (альфа) - попередника, а тільки батька.

Альфа-бета-відтинання: ілюстрація A B C D E -∞ -∞ -∞ +∞ +∞

В проаналізовано A 4 B C D E -∞ -∞ -∞ +∞

Попередня оцінка А змінюється A 4 B C D E 4 -∞ -∞ +∞

Проаналізовано D; змінюється попередня оцінка С A 4 B C D 2 E 4 -∞ 2

Відбувається відтинання; С набуває остаточної оцінки A 4 B C D 2 E 4 -∞ 2

А набуває остаточної оцінки A 4 B 2 C D 2 E -∞ 4 4

Важливі запитання Чи обов’язково остаточна оцінка, отримана в результаті відтинань, співпадає з мінімаксною оцінкою, яка була б отримана в результаті повного аналізу? Чи залежить ефективність альфа-бета-відтинань від порядку перебору ходів?

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

Оцінка максимальної ефективності альфа-бета-відтинань Кількість завершальних позицій, які доводиться аналізувати: 2bd/2 -1 для парних d; b(d+1)/2 + b(d-1)/2 -1 для непарних d. Приблизно - подвоєний квадратний корінь від загальної кількості завершальних вершин. Зокрема, при заданих часових обмеженнях приблизно вдвічі збільшується глибина перебору.

Рекомендація щодо порядку перебору Загальний принцип - упорядкувати позиції-наступники відповідно до певних робочих оцінок. Найпростіший підхід - в першу чергу розглядати дочірні вершини з найкращими статичними оцінками. Неглибокий пошук. Можливим є і динамічне перевпорядкування.

Графовий аналіз ігрових задач Розстановка міток λ(n) - оцінка виграшу гравця, який має право ходу в даній позиції; Аналіз починається від завершальних позицій. Нехай G(n) - множина всіх безпосередніх наступників вершини n. Тоді λ(n) = -minm G(n) λ(m)

“Людський” підхід до гри Людина грає зовсім не так. Виділення найважливіших особливостей позиції; аналіз цілей; евристики і т.п. Дослідження Ботвинника (“ПІОНЕР”) - багаторівневе керування з неточною метою. Втім, спроби відійти від повного перебору були не дуже успішними.

Деякі можливості ігрових програм Шашки (програма Семюеля); шахи. Деякі застосування шахових програм: власне гра (стрімкий прогрес; чемпіонати світу серед шахових програм; ігри проти людей, найбільш відомий приклад - виграш програми Deep Blue в матчі проти Каспарова. Типові прийоми -дебютні бібліотеки; метод форсованих варіантів; служба кращих ходів; аналіз шахових закінчень; перевірка шахових задач.