Головна

Альфа-бета-процедура

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

Основна ідея методу полягає в порівнянні найкращих оцінок, отриманих для повністю вивчених гілок, з найкращими передбачуваними оцінками для решти. Можна показати, що при певних умовах деякі обчислення є зайвими. Розглянемо ідею відсікання на прикладі рис. 3.6. Припустимо, позиція А повністю проаналізовано і знайдено значення її оцінки. Припустимо, що один хід з позиції Y призводить до позиції Z, оцінка якої за методом минимакса дорівнює z. Припустимо, що z. Після аналізу вузла Z, коли справедливо співвідношення y z s, гілки дерева, що виходять з вузла Y, можуть бути відкинуті (альфа-відсікання).


Мал. 3.6. - відсікання

Якщо ми захочемо опуститися до вузла Z, лежачого на рівні довільної глибини, що належить тій же стороні, що і рівень S, то необхідно враховувати мінімальне значення оцінки ?, одержуваної на ходах супротивника.

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

Правила обчислення та ? в процесі пошуку рекомендуються наступні:

  1. у MAX вершини значення дорівнює найбільшому в даний момент значенням серед остаточних повернутих значень для її дочірніх вершин;
  2. у MIN вершини значення ? одно найменшому в даний момент значенням серед остаточних повернутих значень для її дочірніх вершин.

Правила припинення пошуку:

  1. можна не проводити пошуку на поддереве, що росте з будь-якої MIN вершини, у якій значення ? не перевищує значення всіх її батьківських MAX вершин;
  2. можна не проводити пошуку на поддереве, що росте з будь-якої MAX вершини, у якій значення не менш значення ? всіх її батьківських MIN вершин.

На рис. 3.7 показані -? відсікання для конкретного прикладу. Таким чином, -?-алгоритм дає той же результат, що і метод минимакса, але виконується швидше.


Мал. 3.7. a-b відсікання для конкретного прикладу

Використання алгоритмів евристичного пошуку для пошуку на графі І, АБО виграшної стратегії в складніших завданнях і іграх (шашки, шахи) не реальний. За деякими оцінками ігрове дерево гри в шашки містить 1040 вершин, в шахах 10120 вершин. Якщо при грі в шашки для однієї вершини потрібно 1/3 наносекунди, то всього ігрового часу буде потрібно 1021 століть. У таких випадках вводяться штучні умови зупинки, засновані на таких факторах, як найбільша допустима глибина вершин в дереві пошуку або обмеження на час і обсяг пам'яті.

Багато з розглянутих вище ідей були використані А. Ньюеллом, Дж. Шоу і Г. Саймоном в їхній програмі GPS. Процес роботи GPS в загальному відтворює методи вирішення завдань, що застосовуються людиною: висуваються підцілі, які наближають до вирішення; застосовується евристичний метод (один, другий і т. д.), поки не буде отримано рішення. Спроби припиняються, якщо отримати рішення не вдається.

Програма STRIPS (STanford Research Institut Problem Solver) виробляє відповідний порядок дій робота в залежності від поставленої мети. Програма здатна навчатися на досвіді вирішення попередніх завдань. Велика частина ігрових програм також навчається в процесі роботи. Наприклад, знаменита шашечна програма Самюеля, яка виграла в 1974 році у чемпіона світу, "заучувала напам'ять" виграні партії і узагальнювала їх для вилучення користі з минулого досвіду. Програма HACHER Зуссмана, керуюча поведінкою робота, навчалася також і на помилках.

алгоритм минимакса | Методи пошуку рішень на основі числення предикатів


Методи пошуку рішень в просторі | Алгоритм найшвидшого спуску по дереву рішень | Алгоритм оціночних (штрафних) функцій | Пошук рішень в системах продукцій |

© 2016-2022  um.co.ua - учбові матеріали та реферати