Дерево ходів і Альфа-бета відсікання
Альфа-бета відсікання - це оптимізація алгоритму обходу дерева ходів, заснований на знанні поточних кращих результатів отриманих на попередніх рівнях дерева.
Дерево ходів
На малюнку показано дерево можливих ходів. У круглих вузлах робимо вибір ми, а в квадратних – наш суперник.
На якийсь момент процес розгляду можливих ходів у відповідь припиняється. Дерево ходів має кінцевий розмір і для його листя робиться певна евристична оцінка.
Оціночна функція у шахах може бути заснована на тому, які фігури залишилися на дошці (зважена сума фігур білих мінус зважена сума фігур чорних).
Якщо ситуація хороша для білих – оцінна функція позитивна, якщо для чорних – негативна. Ми будемо вважати, що в інших іграх також один гравець є "білим", а інший "чорним". Наприклад, у хрестиках-нуліках "білим" гравцем призначимо хрестика.
Серед можливих ходів ми ("білий") вибиратимемо той хід, який приводить нас у позицію з максимумом оцінки, а думаючи за суперника, природно вибирати хід, що приводить у ситуацію з найменшою оцінкою.
* Score (position, depth) - оцінка ситуації position при глибині продумування depth.
Її зручно визначити рекурсивно:
- Score(position, 0) = HeuriscticScore?(position)
- Score(position, depth) = MAX < (Score(p, depth-1) >, якщо d непарне;
- Score(position, depth) = MIN < (Score(p, depth-1) >, якщо d парне;
- де p пробігає всі можливі позиції, які можна потрапити з позиції position.
Таким чином, якщо переглядаємо дерево ходів до глибини 4 (4 півходи), то
- Score(4) = MAX ( MIN (MAX (MIN ( оцінка ситуації аркуша ), ..), ..), ..)
Першиймаксимум шукається за можливими нашими ходами; наступний мінімум шукається за можливими відповідями суперника на наш хід; наступний максимум шукається за можливими нашими відповідями на відповідь суперника і т.д. Наведемо схематичний код C, в якому обчислюється Score (depth) :
Альфа-бета відсікання
Ідея оптимізації роботи функції Score(depth) починається з таких міркувань:
- S1: Нехай ми розглянули вже один свій хід MOVE1 і всі можливі відповіді суперника і почали розглядати свій другий хід MOVE2. Як тільки серед відповідей суперника, з'явиться такий хід, який ставить нас у ситуацію гірше, ніж найгірша ситуація, в яку може нас поставити суперник, якщо ми сходимо ходом MOVE1, то можна припиняти перебір можливих відповідей суперника на хід MOVE2 та переходити до розгляду наступного нашого ходу MOVE3.
- S2: МіркуванняS1 можна проводити на кожному рівні, розмірковуючи як за себе так і за суперника
- S3: По суті для реалізації ідеїS2 ми повинні пам'ятати найкращий результат, досягнутий на попередньому рівні. Назвемо найкращий результат із попереднього рівня параметром alpha.
- S4: А чи можна використовувати в своїх цілях найкращий результат з попереднього рівня? Так можна! Це буде параметр beta.
Таким чином, процедура score_alphabeta(int depth, int alpha, int beta) крім глибини продумування отримує ще два параметри alpha і beta .
Її сенс можна пояснити так: Знайти оцінку поточної ситуації (якась глобальна змінна X), припущення, що вона знаходиться між alpha і beta . Якщо це припущення не є вірним, і реальна оцінка ситуації є A, що лежить поза [alpha, beta] , то
- повернути beta+1 якщо A >= beta;
- повернути alpha-1, якщо A alpha.
Таким чином, якщо ми вгадаємо проміжок, в якому лежить реальна оцінка ситуації, то отримаємо правильну оцінку, інакше ми дізнаємося лише з якого боку від проміжку [alpha, beta] лежить правильна відповідь.
Функцію score_alphabeta можна викликати з параметрами alpha=-infty, beta=+infty та отримати точне значення. При обчисленні цього значення будуть здійснюватися рекурсивні дзвінки, для яких параметри вже не нескінченні. Тим глибший рівень рекурсії, тим більше в середньому зближуються аргумени alpha і beta.
Подальші оптимізації
Ось посканена версія статті з журналу "Програміст": Алгортими: пошук в іграх.doc