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

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

Дерево альфа-бета пошуку. Машина перевіряє ходи зліва направо, відсікає всі гілки та піддерева зі сірими ходами як гірші та припиняє пошук у них. Продовжує пошук лише в білих гілках

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

 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 викликає останній хід, альфа-бета прогляне стільки ж позицій, що і мінімакс. Швидкість прорахунку також дуже залежить на практиці від можливого діапазону оцінок. Наприклад, коли враховується тільки матеріал, то оцінка всім ходам, крім узяття, буде дорівнювати нулю. Це означає, що відсічень буде дуже багато, особливо якщо узяття розглядатимуться першими.