Альфа-бета-отсечение

Альфа-бета-отсечение ускоряет поиск, выполняемый шахматным движком, программой, сравнивающей ходы и ответы. Поиск можно представить в виде дерева: каждый узел является позицией, а каждая ветвь соответствует допустимому ходу. Без отсечения программа исследовала бы множество продолжений, которые в итоге окажутся несущественными.

Во время поиска метод поддерживает две границы. Альфа представляет лучший результат, который одна сторона уже может гарантировать на текущем пути. Бета является границей, созданной альтернативой, уже доступной сопернику. Как только продолжение становится настолько плохим, что рациональный игрок никогда его не выберет, дальнейшее исследование не может изменить решение в вышестоящем узле.

Ветвь останавливается из-за логической границы в дереве, а не просто потому, что ход выглядит непривлекательно. При одинаковой глубине и одинаковых оценках на границе поиска альфа-бета возвращает тот же выбор, что и полный поиск, предполагающий лучшие ответы обеих сторон.

Экономия сильно зависит от порядка ходов. Раннее исследование сильных ходов быстрее устанавливает полезные границы и позволяет прекращать больше ветвей без углубления. Оценочная функция, присваивающая позиции численную оценку, предоставляет значения в точках завершения конечного поиска.