Теперь, чтобы перенести оценку с уровня d на уровень 0, выполните следующие действия на всех уровнях, начиная с уровня d и кончая нулевым. Примените статическую оценочную функцию ко всем листьям на рассматриваемом уровне. Это дает разницу очков в листьях. Для нелистовых узлов постройте оценку разницы очков, найдя максимум оценок по всем непосредственным преемникам данного узла, если он находится на четном уровне, и минимум, если узел — на нечетном уровне. Такой способ действий отвечает стремлению Макса максимизировать разрыв и стремлению Мина минимизировать его (или сделать более отрицательным). После того как пройден весь путь до нулевого уровня и найдена разница очков в исходном узле, выберите любой из шести ходов, позволяющий получить эту разницу очков. Отметим, что, как правило, все листья будут находиться на уровне d. Кроме того, при построении дерева можно всегда проходить каждую ветвь сначала вглубь,т.е. строить дерево в порядке перебора в глубину, а не в порядке перебора в ширину, как описано[19]. На рис. 14.7 показана часть возможного дерева игры. До листьев доведена лишь одна ветвь. Изображены правильные значения, вычисленные исходя из показанной на рисунке информации. Максу следует выбрать ход из лунки 1.
Рисунок 14.7. Возможное дерево игры. Полностью показан только один путь до низа дерева. Предполагается, что значения в кружках получены из анализа нижних уровней.
По сути дела, мы сейчас описали минимаксную процедуру для игры двух лиц. Как нетрудно видеть, для анализа на d уровней вперед необходимо построить около
позиций. Ввиду очень быстрого роста этой функции желательно иметь какое-либо средство, экономящее усилия. Альфа-бета-процедура при том же объеме работы позволяет иногда провести анализ на вдвое большую глубину.
Идея этой процедуры обобщает рассмотренный пример. Допустим, что в некотором внутреннем узле А дерева ход должен сделать Макс и что он с помощью перебора в глубину уже построил полное дерево В для хода из лунки 1 и дерево С для хода из лунки 2. Предположим далее, что оценка, вычисленная при анализе дерева, равна 1 для узла В и 2 — для С. Тогда можно приписать узлу А предварительную оценку (ПО), равную 2. Что бы ни случилось, Макс может отвергнуть любой ход из А с оценкой меньше 2. Допустим теперь, что Макс начинает строить дерево для хода из лунки 3 в узел D. В узле D ход Мина. Как только D получит ПО, равную или меньшую 2, дальнейшее построение дерева ниже D окажется уже ненужным. Действительно, Мин заведомо не выберет ход с оценкой больше 2, если доступно значение 2 или меньше. Но тогда узел D не будет интересовать Макса, коль скоро он уже имеет возможность получить 2. Итак, можно прекратить раскрытие узла D. Обсуждавшееся дерево показано на рис. 14.8.
Рисунок 14.8. Часть дерева для альфа-бета-процедуры, описанного в тексте. Как только ПО в узле D опустится ниже 3, можно прекращать раскрытие узла D и его преемников.
Для выполнения альфа-бета-процедуры поиска минимакса начните с перебора дерева игры в глубину. Каждому узлу приписывается предварительная оценка (ПО) и окончательная оценка (ОО). Для листьев как ПО, так и ОО равна статической оценке. ПО во внутренних узлах Макса равна максимуму из ОО преемников этого узла, в узлах Мина — минимуму. Всякий раз, когда ПО меняется, мы проверяем, не следует ли прекратить раскрытие этого узла. (Первоначально ПО равна −∞ во внутренних узлах Макса и +∞ во внутренних узлах Мина). В узле Макса происходит отсечение всякий раз, как только ПО этого узла становится не меньше ПО какого-либо предшественника этого узла, принадлежащего Мину[20]. Аналогично в узле Мина отсечение происходит, когда его ПО становится не больше ПО какого-либо из предшественников, принадлежащего Максу. При отсечении узла его ПО становится его ОО. Вам следует убедиться, что альфа-бета-процедура всегда выбирает тот же ход, что и обычная минимаксная процедура.
Тема. Напишите программу для игры в калах, использующую альфа-бета-процедуру. Ваша программа должна уметь играть как против человека за терминалом, так и против самой себя. Следует предусмотреть возможность изменения глубины d просмотра, числа к камней в каждой лунке, а также замены игрока, делающего первый ход. Вывод позиций и ввод ходов следует представить в наиболее удобной форме. По требованию программа должна выдавать на печать дерево ходов. Чтобы с программой было интересно играть, она должна случайным образом выбирать ход из нескольких равноправных (как обычно, эту возможность следует отключать на время отладки).
20
Достаточно проверить только непосредственный предшественник, при этом будут найдены все отсечения. —