Главная arrow книги arrow Копия Глава 6. Поиск в условиях противодействия arrow Альфа-бета-отсечение
Альфа-бета-отсечение

Листинг 6.2. Алгоритм альфа-бета-поиска. Обратите внимание на то, что применяемые здесь процедуры остаются такими же, как и процедуры алгоритма Minimax, приведенного в листинге 6.1, за исключением двух строк, введенных как в процедуру Min-Value, так и в Max-Value, которые сопровождают значения ос и (3 (а также выполняют соответствующие действия по дальнейшей передаче этих параметров)

Эффективность алгоритма альфа-бета-отсечения в высшей степени зависит от того, в каком порядке происходит проверка преемников. Например, на рис. 6.4, d, e невозможно было бы вообще выполнить отсечение каких-либо преемников узла D, поскольку в первую очередь были бы сформированы наихудшие преемники (с точки зрения игрока MIN). А если бы в первую очередь был сформирован третий преемник, то была бы возможность отсечь двух остальных. На основании этого можно сделать вывод, что имеет смысл стремиться исследовать в первую очередь таких преемников, которые, по всей вероятности, могут стать наилучшими.