Главная arrow книги arrow Копия Глава 6. Поиск в условиях противодействия arrow Обсуждение изложенных сведений
Обсуждение изложенных сведений

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

Рис. 6.11. Дерево игры с двумя полуходами, для которого минимаксный поиск может оказаться неподходящим

Альфа-бета-поиск все еще вырабатывает и оценивает большое и полностью бесполезное дерево поиска. Безусловно, можно предусмотреть в этом алгоритме какую-то проверку подобной ситуации, но она просто замаскирует основную проблему: многие вычисления, выполняемые в альфа-бета-алгоритме, практически ничего не дают для решения задачи. Ситуация, в которой имеется только один допустимый ход, ненамного отличается от той, где имеется несколько допустимых ходов, притом что один из них является правильным, а остальные — явно катастрофическими. В подобной ситуации наличия "четко выраженного фаворита" было бы желательно быстро достигать решения после проведения небольшого объема поиска, чем терять время, которое можно было бы использовать продуктивнее в дальнейшем, в более проблематичной позиции. Это ведет к идее полезности развертывания узла. Хороший алгоритм поиска должен выбирать варианты развертывания узлов с высокой полезностью, т.е. те варианты, которые, со всей вероятностью, приведут к обнаружению гораздо лучшего хода. Если же отсутствуют варианты развертывания узлов, полезность которых превышает их стоимость (измеряемую в затратах времени), то алгоритм должен прекратить поиск и выбрать ход. Следует отметить, что такое усовершенствование касается не только ситуаций с явными фаворитами, но и тех случаев, когда имеются симметричные ходы, для которых сколь угодно большой объем поиска не позволит показать, что один ход лучше другого.