Використання евристик в іграх
Таким чином, альфа-бета-усікання виражає відношення між вузлами рівнів n і n +2. При цьому з розгляду можуть бути виключені цілі піддерева з корінням на рівні n+1. Наприклад, на мал. 8 зображений простір пошуку з мал. 3, до якого застосований алгоритм альфа-бета-усікання. Відмітимо, що результуюче значення, що повертається, ідентичне отриманому в алгоритмі мінімакса, але при цьому процедура альфа-бета-усікання значно економічніше мінімакса.
При вдалому порядку станів в області пошуку процедура альфа-бета-усікання може ефективно подвоювати глибину пошуку в даному просторі при фіксованих просторово-часових характеристиках комп'ютера [Nilsson, 1980]. Якщо ж вузли розташовані невдало, процедура альфа-бета-усікання здійснює пошук в такому ж просторі, як і звичайний мінімакс. Проте пошук проводиться тільки за один прохід.
3. Стратегії пошуку в просторі станів на основі даних і від цілі
Пошук в просторі станів можна вести в двох напрямах: від початкових даних завдання до цілі і у зворотному напрямі від цілі до початкових даних.
При пошуку на основі даних (data-driven search — пошук, керований даними), який іноді називають прямим ланцюжком (forward chaining), дослідник починає процес рішення задачі, аналізуючи її умову, а потім застосовує допустимі ходи або правила зміни стану. В процесі пошуку правила застосовуються до відомих фактів для отримання нових фактів, які, у свою чергу, використовуються для генерації нових фактів. Цей процес продовжується до тих пір, поки ми, якщо повезе, не досягнемо цілі.
Можливий і альтернативний підхід
Підведемо підсумки: пошук на основі даних починається з умов задачі і виконується шляхом застосування правил або допустимих ходів для отримання нових фактів, ведучих до цілі. Пошук від цілі починається із звернення до цілі і продовжується шляхом визначення правил, які можуть привести до цілі, і побудови ланцюжка підцілей, що веде до початкових даних задачі.
Нарешті відмітимо, що в обох випадках (і при пошуку на основі даних і при пошуку від цілі) дослідник працює з одним і тим же графом простору станів, проте порядок і число станів в процесі пошуку можуть розрізнятися. Яку стратегію пошуку віддати перевазі, залежить від самої задачі. При цьому слід враховувати складність правил, "форму" простору станів, природу і доступність даних задачі. Все це може змінюватися від задачі до задачі.
Як приклад залежності складності пошуку від вибору стратегії розглянемо задачу, в якій потрібно підтвердити або спростувати твердження "Я — нащадок Томаса Джефферсона". Позитивним рішенням є шлях по генеалогічному дереву від "Я" до "Томас Джефферсон". Пошук на цьому графові можна вести в двох