Программирование на языке Пролог для искусственного интеллекта


         

Альфа-бета алгоритм: эффективная реализация минимаксного принципа


Программа, показанная на рис. 15.3, производит просмотр в глубину дерева поиска, систематически обходя все содержащиеся в нем позиции вплоть до терминальных; она вычисляет статические оценки всех терминальных позиций. Как правило, для того, чтобы получить правильную минимаксную оценку корневой вершины, совсем не обязательно проделывать эту работу полностью. Поэтому алгоритм поиска можно сделать более экономным. Его можно усовершенствовать, используя следующую идею. Предположим, что у нас есть два варианта хода. Как только мы узнали, что один из них явно хуже другого, мы можем принять правильное решение, не выясняя, на сколько в точности он хуже. Давайте используем этот принцип для сокращения дерева поиска рис. 15.2. Процесс поиска протекает следующим образом:

    (1)        Начинаем с позиции  а.

    (2)        Переходим к   b.

    (3)        Переходим к   d.

    (4)        Берем максимальную из оценок преемников позиции  d,   получаем  V( d) = 4.

    (5)         Возвращаемся к  b   и переходим к  е.

    (6)         Рассматриваем первого преемника позиции  е  с оценкой 5. В этот момент МАКС (который как раз и должен ходить в позиции  е)  обнаруживает, что ему гарантирована в позиции  е  оценка не меньшая, чем 5, независимо от оценок других (возможно, более предпочтительных) вариантов хода. Этого вполне достаточно для того, чтобы МИН, даже не зная точной оценки позиции  е,   понял, что для него в позиции  b  ход в  е  хуже, чем ход в  d.

На основании приведенного выше рассуждения мы можем пренебречь вторым преемником позиции  е

  и приписать  е  приближенную оценку 5.

Содержание  Назад  Вперед