Відсічення альфа-бета

Алгоритми пошуку графами та деревами
α–β A* B* Бахромовий Беллмана — Форда Британського музею Борувки В глибину В ширину Гілок та меж D* Двоспрямований Дейкстри Джонсона Едмондса З вертанням зворотний перехід З ітеративним заглибленням З обмеженням глибини IDA* Крускала Лексикографічний у ширину На стрибкових точках Перший-найліпший Прима Променевий SMA* Сходження на вершину Флойда — Воршелла
Переліки
Алгоритми на графах Алгоритми пошуку Список алгоритмів на графах
Пов'язані теми
Динамічне програмування Пошукова гра Пошук по графу Обхід дерева

Альфа-бета відсічення — алгоритм пошуку, що зменшує кількість вузлів, які необхідно оцінити в дереві пошуку мінімаксного алгоритму і при цьому дозволяє отримати ідентичний результат. Цей алгоритм використовується в програмуванні настільних ігор, де грають два гравці (хрестики-нулики, шахи, ґо). Використовуючи цей алгоритм, програма повністю припиняє оцінювати хід, якщо знайшла доказ, що цей хід гірший, ніж оцінений раніше. Такі ходи не потребують подальшої оцінки.

Приклад здійснення

 private int AlphaBeta(int color, int Depth, int alpha, int beta) {
    if (Depth == 0) return Evaluate(color); 
    int bestmove;
    Vector moves = GenerateMoves();
    for(int i = 0; i < moves.size(); i++) {
        makeMove(moves.get(i));
        eval = -AlphaBeta(-color, Depth-1, -beta, -alpha);
        unmakeMove(moves.get(i));

        if(eval >= beta)
          return beta;

        if(eval > alpha) {
          alpha = eval;
          if (Depth == defaultDepth) {
            bestmove = moves.get(i);  
    }
   }
  }
    return alpha;
 }

Приклад першого виклику:

 AlphaBeta(1, 6, Integer.MIN_VALUE, Integer.MAX_VALUE);

При першому виклику метод (функція) викликається з максимальним вікном. При рекурсивних викликах змінні alpha і beta міняються місцями з інверсією знаку і «звужують» обшир пошуку.

Альфа-бета алгоритм, при найкращому порядку ходів, побудує значно менше дерево перебору. Це приблизно дорівнює кореню квадратному з числа позицій, що переглядаються при повному переборі. Альфа-бета дуже чутливий до порядку ходів. Тому потрібно врахувати, що при найгіршому порядку ходів, тобто коли відсічення за beta викликає останній хід, альфа-бета прогляне стільки ж позицій, що і мінімакс. Швидкість прорахунку також дуже залежить на практиці від можливого діапазону оцінок. Наприклад, коли враховується тільки матеріал, то оцінка всім ходам, крім узяття, буде дорівнювати нулю. Це означає, що відсічень буде дуже багато, особливо якщо узяття розглядатимуться першими.