Повна версія

Головна arrow Інформатика arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ПОШУК В УМОВАХ ПРОТИДІЇ

У попередніх завданнях складність знаходження рішення визначалася тільки розмірністю простору станів. Існує клас задач, в яких присутній елемент невизначеності. До них відносяться всі ігрові завдання. Ми не будемо розглядати шахи (оцініть самі комбінаторних складність на перші 40 ходів, коефіцієнт розгалуження па першому ході - 20), а повернемося до гри в сірники.

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

Так, показана на рис. 2.15 ланцюжок «5 - 3 - 0» сірників нас влаштовує (вузли відображають число сірників, яке залишається після зробленого ходу), але противник так ніколи не буде ходити, а візьме замість трьох сірників дві, що призведе до нашого програшу.

Фрагмент дерева рішень в грі «23 сірники»

Мал. 2.15. Фрагмент дерева рішень в грі «23 сірники»

Щоб оцінити доцільність того чи іншого ходу, дамо нашій перемозі значення 1, а перемоги противника - значення 0. У такому випадку наша стратегія полягає в тому, щоб максимізувати результат, а стратегія супротивника - його мінімізувати. Назвемо для ясності противника - МІН, а себе - МАКС. Спускаючись але дереву рішень, ми можемо дати оцінку кожному вузлу на найнижчому рівні (рис. 2.16).

Припускаючи, що обидва гравці діють в своїх інтересах розумно, ми можемо дати оцінку кожному ходу гравців на кожен рівень вище, а саме: з усіх варіантів ходів МІН віддасть перевагу ті, які дадуть оцінку 0, а МАКС - ходи, що дають оцінку 1. Таким чином , оцінка кожного ходу МАКСа буде дорівнює мінімуму оцінок ходів МІ На і, навпаки, оцінка кожного ходу МІ На дорівнюватиме максимуму оцінок ходів МАКСА.

хв

Фрагмент дерева рішень в грі «23 сірники» (алгоритм минимакса)

Мал. 2.16. Фрагмент дерева рішень в грі «23 сірники» (алгоритм минимакса):

- виграш МАКС; - виграш міна

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

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

  • 1) вибір шкали оцінок результатів гри;
  • 2) спуск по дереву і привласнення оцінок кінцевим станам;
  • 3) послідовне присвоєння оцінок батьківським вузлів: для міна - максимальної з дочірніх, для МАКС - мінімальної;
  • 4) після присвоєння значення початкової позиції можна починати робити ходи.

Очевидним недоліком минимаксного алгоритму є його трудомісткість, оскільки необхідно виконати обхід всього дерева. Модифікацією даного алгоритму, істотно вкорочують його складність, є альфа-бета відсікання. Розглянемо ще раз той самий фрагмент, тепер уже з позиції МАКС, мета якого максимізувати результат. Спускаючись але дереву вглиб по лівим гілкам, ми можемо переконатися, що хід МАКСа «7-6» (взяття одного сірника при семи в наявності) дає можливість міну виграти ходом «6-5». А оскільки оцінка ходу МАКСа визначається мінімумом оцінок можливих відповідей міна, спускатися по сусідніх гілках «6-4» і «6-3» немає необхідності і можна відразу переходити до спуску по гілці «7-5».

Алгоритм минимакса з альфа-бета відсіканням

Мал. 2.17. Алгоритм минимакса з альфа-бета відсіканням

І навпаки, якщо ми бачимо, що хід МАКСа «7-5» має оцінку 1, нам немає необхідності перевіряти гілка «7-4».

Ефективність альфа-бета відсікання істотно залежить від порядку перевірки вузлів. Якби ми спочатку перевірили хід «7-5», то нам би не довелося перевіряти хід «7-6». Це означає, що спуск але дереву доцільно починати з найбільш перспективних ходів. Зрозуміло, це можливо, тільки якщо ми маємо в своєму розпорядженні відповідної інформацією.

 
<<   ЗМІСТ   >>