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

Рис. 6.5. Альфа-бета-отсечение: общий случай. Если для Игрока узел m лучше чем п, то узел п никогда не встретится в игре

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

• а = значение наилучшего варианта (т.е. варианта с самым высоким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока мах;

• B = значение наилучшего варианта (т.е. варианта с самым низким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока MIN.

Алгоритм альфа-бета-поиска в процессе своей работы обновляет значения a и B, а также отсекает оставшиеся ветви в узле (т.е. прекращает рекурсивные вызовы), как только становится известно, что значение текущего узла хуже по сравнению с текущим значением а или B для игрока МАХ или MIN соответственно. Полный алгоритм приведен в листинге 6.2. Рекомендуем читателю проследить за его поведением применительно к дереву, показанному на рис. 6.4.