Змагальний пошук – це пошук, під час якого ми досліджуємо проблему, яка виникає, коли ми намагаємось планувати на випередження, а інші агенти планують проти нас.

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

Типи ігор в AI:

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

Примітка. У цій темі ми обговоримо детерміновані ігри, повністю спостережуване середовище, нульову суму та де кожен агент діє альтернативно.

Гра з нульовою сумою

• Ігри з нульовою сумою – це змагальний пошук, який передбачає чисту конкуренцію.
• У грі з нульовою сумою виграш або втрата корисності кожного агента точно врівноважується втратами або виграшами корисності іншого агента.
• Один гравець у грі намагається максимізувати одне значення, тоді як інший гравець намагається мінімізувати його.
• Кожен хід одного гравця в грі називається шаром.
• Шахи та хрестики-нулики є прикладами гри з нульовою сумою.

Гра з нульовою сумою: вбудоване мислення

Гра з нульовою сумою включала вбудоване мислення, у якому один агент або гравець намагався з’ясувати:

listnode

• Що робити.
• Як вирішити хід
• Треба думати і про суперника
• Суперник теж думає, що робити

Кожен з гравців намагається дізнатися реакцію суперника на їхні дії. Це вимагає вбудованого мислення або ретроспективних міркувань для вирішення проблем гри в ШІ.

Формалізація задачі:

Гру можна визначити як тип пошуку в ШІ, який можна формалізувати з таких елементів:

Початковий стан:Він визначає, як гра налаштована на початку.Гравець(и):Він визначає, який гравець перемістився в просторі станів.Дії:Він повертає набір допустимих ходів у просторі станів.Результат(и, а):Це модель переходу, яка визначає результат переміщень у просторі станів.Термінальний тест(и):Тест терміналу є істинним, якщо гра закінчилася, інакше він у будь-якому випадку є хибним. Стан, коли гра закінчується, називається термінальним станом.Корисність(и, p):Функція корисності дає кінцеве числове значення для гри, яка закінчується в кінцевих станах s для гравця p. Її також називають функцією виплати. Для шахів результатами є виграш, поразка або нічия, а значення виграшу — +1, 0, ½. А для хрестиків-нуликів значення корисності дорівнюють +1, -1 і 0.

Дерево гри:

Дерево гри – це дерево, де вузли дерева – це стани гри, а ребра дерева – ходи гравців. Дерево гри містить початковий стан, функцію дій і функцію результату.

Приклад: дерево гри в хрестики-нулики:

статична функція в java

На наступному малюнку показано частину ігрового дерева для гри в хрестики-нулики. Ось кілька ключових моментів гри:

• Є два гравці MAX і MIN.
• Гравці мають альтернативний хід і починають з МАКС.
• MAX максимізує результат дерева гри
• MIN мінімізує результат.

Приклад пояснення:

• З початкового стану МАКС має 9 можливих ходів, оскільки він починає першим. MAX розміщує x і MIN розміщує o, і обидва гравці грають по черзі, доки ми не досягнемо листкового вузла, де один гравець має три в рядку або всі квадрати заповнені.
• Обидва гравці обчислять кожен вузол, мінімакс, мінімаксне значення, яке є найкращою досяжною корисністю проти оптимального супротивника.
• Припустимо, обидва гравці добре знають хрестики-нулики і грають найкращу партію. Кожен гравець робить усе можливе, щоб не дати іншому виграти. MIN діє проти Макса в грі.
• Тож у дереві гри ми маємо шар Max, шар MIN, і кожен шар називається as пластовий . Макс ставить x, потім MIN ставить o, щоб запобігти виграшу Макса, і ця гра продовжується до термінального вузла.
• У цьому випадку виграє або MIN, або MAX, або нічия. Це дерево гри — це весь простір пошуку можливостей, у які MIN і MAX грають у хрестики-нулики та по черзі.

Отже, змагальний пошук мінімаксної процедури працює наступним чином:

репозиторій maven

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

У заданому дереві гри оптимальну стратегію можна визначити за мінімаксним значенням кожного вузла, яке можна записати як MINIMAX(n). MAX віддає перевагу переходу до стану максимального значення, а MIN віддає перевагу переходу до стану мінімального значення, тоді: