PART3 (Печатные лекции), страница 4

Будем придерживаться общепринятого соглашения, по которому значение статической оценочной функции тем больше, чем больше преимуществ имеет игрок ПЛЮС (над игроком МИНУС) в оцениваемой позиции. Очень часто оценочная функция выбирается следующим образом:

• статическая оценочная функция положительна в игровых конфигурациях, где игрок ПЛЮС имеет преимущества;

• статическая оценочная функция отрицательна в конфигурациях, где МИНУС имеет преимущества;

• статическая оценочная функция близка к нулю в позициях, не дающих преимущества ни одному из игроков.

Например, для шашек в качестве простейшей статической функции может быть взят перевес в количестве шашек (и дамок) у игрока ПЛЮС. Для игры «крестики-нолики» на фиксированном квадрате возможна такая статическая оценочная функция:

 + если P есть позиция выигрыша игрока ПЛЮС

E(P) =   если P есть позиция выигрыша МИНУСа

 (N_L⁺ +N_C⁺_­ +N_D⁺ )(N_L^ +N_C^ +N_D^) в остальных случаях

где +  очень большое положительное число;

  очень маленькое отрицательное число;

N_L⁺, N_C⁺, N_D⁺  соответственно число строк, столбцов и диагоналей, «открытых» для игрока ПЛЮС (т.е. где он еще может поставить выигрышные три крестика подряд),

N_L^, N_C^, N_D^  аналогичные числа для игрока МИНУС.

На рис.18 приведены две игровые позиции (на квадрате 44) и соответствующие значения статической оценочной функции.

Подчеркнем, что с помощью статической оценочной функции оцениваются только концевые вершины дерева игры, для оценок же промежуточных вершин (и начальной вершины) используется минимаксный принцип, основанный на следующей простой идее. Если бы игроку ПЛЮС пришлось бы выбирать один из нескольких возможных ходов, то он выбрал бы наиболее сильный ход, т.е. ход, приводящий к позиции с наибольшей оценкой. Аналогично, если бы игроку МИНУС пришлось бы выбирать ход, то он выбрал бы ход, приводящий к позиции с наименьшей оценкой.

Сформулируем теперь сам минимаксный принцип:

• ИЛИ-вершине дерева игры приписывается оценка, равная максимуму оценок ее дочерних вершин;

• И-вершине игрового дерева приписывается оценка, равная минимуму оценок ее дочерних вершин.

Минимаксный принцип положен в основу минимаксной процедуры, предназначенной для определения наилучшего (достаточно хорошего) хода игрока исходя из заданной конфигурации игры S при фиксированной глубине поиска N в игровом дереве. Предполагается, что игрок ПЛЮС ходит первым (начальная вершина есть ИЛИ-вершина). Основные этапы этой процедуры таковы:

1. Дерево игры строится (просматривается) одним из известных алгоритмов перебора (как правило, алгоритмом поиска вглубь) от исходной позиции S до глубины N ;

2. Все концевые вершины полученного дерева, то есть вершины, находящиеся на глубине N, оцениваются с помощью статической оценочной функции;

3. В соответствии с минимаксным принципом вычисляются оценки всех остальных вершин: сначала вычисляются оценки вершин, родительских для концевых, затем родительских для этих родительских вершин и так далее; таким образом оценивание вершин происходит при движении снизу вверх по дереву поиска  до тех пор, пока не будут оценены вершины, дочерние для начальной вершины, т.е. для исходной конфигурации S;

4. Среди вершин, дочерних к начальной, выбирается вершина с наибольшей оценкой: ход, который к ней ведет, и есть искомый наилучший ход в игровой конфигурации S.

На рис.19 показано применение минимаксной процедуры для дерева игры, построенного до глубины N=3. Концевые вершины не имеют имен, они обозначены своими оценками  значениями статической оценочной функции. Числовые индексы имен остальных вершин показывают порядок, в котором эти вершины строились алгоритмом перебора вглубь. Рядом с этими вершинами находятся их минимаксные оценки, полученные при движении в обратном (по отношению к построению дерева) направлении. Таким образом, наилучший ход – первый из двух возможных.

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

В принципе статическую оценочную функцию можно было бы применить и к промежуточным вершинам, и на основе этих оценок осуществить выбор наилучшего первого хода, например, сразу выбрать ход, максимизирующий значение статической оценочной функции среди вершин, дочерних к исходной. Однако считается, что оценки, полученные с помощью минимаксной процедуры, есть более надежные меры относительного достоинства промежуточных вершин, чем оценки, полученные прямым применением статической оценочной функции. Действительно, минимаксные оценки основаны на просмотре игры вперед и учитывают разные особенности, которые могут возникнуть в последующем, в то время как простое применение оценочной функции учитывает лишь статические свойства позиции как таковой. Это отличие статических и минимаксных оценок существенно для «активных», динамичных позиций игры (например, в шашках и шахматах к ним относятся конфигурации, в которых возникает угроза взятия одной или нескольких фигур). В случае же так называемых «пассивных», спокойных позиций статическая оценка обычно мало отличается от оценки по минимаксному принципу.

Альфа-бета процедура

Минимаксная процедура организована таким образом, что процесс построения частичного дерева игры отделен от процесса оценивания вершин. Такое разделение приводит к тому, что в целом минимаксная процедура  неэффективная стратегия поиска хорошего первого хода. Чтобы сделать процедуру более экономной, необходимо вычислять статические оценки концевых вершин и минимаксные оценки промежуточных вершин одновременно с построением игрового дерева. Этот путь приводит к так называемой альфа-бета процедуре поиска наилучшего первого хода от заданной позиции, на нем можно добиться существенного сокращения вычислительных затрат, прежде всего, времени вычисления оценок. В основе такого сокращения поиска лежит достаточно очевидное соображение: если есть два варианта хода одного игрока, то худший в ряде случаев можем сразу отбросить, не выясняя, насколько в точности он хуже.

Рассмотрим сначала идею работы альфа-бета процедуры на примере игрового дерева, приведенного на рис.19. Дерево игры строится до глубины N=3 алгоритмом перебора вглубь. Причем сразу, как это становится возможным, вычисляются не только статические оценки концевых вершин, но и предварительные минимаксные оценки промежуточных вершин. Предварительная оценка определяется соответственно как минимум или максимум уже известных (к настоящему моменту) оценок дочерних вершин, и она может быть получена при наличии оценки хотя бы одной дочерней вершины. Предварительные оценки затем постепенно уточняются по минимаксному принципу – по мере получения новых (предварительных и точных) оценок в ходе дальнейшего построения дерева.

Пусть таким образом построены вершины W₁^, W₂⁺ и первые три конечные вершины (листья)  см. рис.20. Эти листья оценены статической функцией, и вершина W₂⁺ получила точную минимаксную оценку 3, а вершина W₁^  предварительную оценку 3. Далее при построении и раскрытии вершины W₃⁺ статическая оценка первой ее дочерней вершины дает величину 4, которая становится предварительной оценкой самой вершин W₃⁺ . Эта предварительная оценка будет потом (после построения второй дочерней вершины) пересчитана, причем согласно минимаксному принципу она может только увеличиться (так как равна максимуму оценок дочерних вершин), но даже если она увеличится, это не повлияет на оценку вершины W₁^, поскольку последняя при уточнении по минимаксному принципу может только уменьшаться (она равна минимуму оценок дочерних вершин). Следовательно, можно пренебречь второй дочерней вершиной для W₃⁺, не строить и не оценивать ее (так как уточнение оценки вершины W₃⁺ не повлияет на оценку вершины W₁^). Такое сокращение процедуры поиска в дереве называется отсечением ветвей дерева.

Продолжим для нашего примера процесс поиска в глубину с одновременным вычислением предварительных (и точных, где это возможно) оценок вершин вплоть до момента, когда построены уже вершины W₄^ , W₅⁺ и две дочерних последней, которые оцениваются статической функцией. Исходя из оценки первой дочерней вершины начальная вершина W₀⁺, соответствующая исходной позиции игры, к этому моменту уже предварительно оценена величиной 3. Вершина W₅⁺ получила точную минимаксную оценку 3, а ее родительская W₄^ получила пока только предварительную оценку 3. Эта предварительная оценка вершины W₄^может быть уточнена в дальнейшем, но в соответствии с минимаксным принципом возможно только ее уменьшение, а это уменьшение не повлияет на оценку вершины W₀⁺, поскольку последняя, опять же согласно минимаксному принципу, может только увеличиваться. Таким образом, построение дерева можно прервать ниже вершины W₄^, отсекая целиком выходящие из нее вторую и третью ветви (и оставляя ее оценку предварительной).

На этом построение рассматриваемого игрового дерева заканчивается, полученный результат  лучший первый ход  тот же самый, что и при минимаксной процедуре. У некоторых вершин дерева осталась неуточненная, предварительная оценка, однако этих приближенных оценок оказалось достаточно для того, чтобы определить точную минимаксную оценку начальной вершины и наилучший первый ход. В то же время произошло существенное сокращение поиска: вместо 17 вершин построено только 11, и вместо 10 обращений к статической оценочной функции понадобилось всего 6.

Обобщим рассмотренную идею сокращения перебора. Сформулируем сначала правила вычисления оценок вершин дерева игры, в том числе предварительных оценок промежуточных вершин, которые для удобства будем называть альфа- и бета-величинами:

• концевая вершина дерева оценивается статической оценочной функцией сразу, как только она построена;

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

• предварительная оценка ИЛИ-вершины (альфа-величина) полагается равной наибольшей из вычисленных к текущему моменту оценок ее дочерних вершин;

• предварительная оценка И-вершины (бета-величина) полагается равной наименьшей из вычисленных к текущему моменту оценок ее дочерних вершин.

Укажем очевидное следствие этих правил вычисления: альфа-величины не могут уменьшаться, а бета-величины не могут увеличиваться.

Сформулируем теперь правила прерывания перебора, или отсечения ветвей игрового дерева:.

1. Перебор можно прервать ниже любой И-вершины, бета-величина которой не больше, чем альфа-величина одной из предшествующих ей ИЛИ-вершин (включая корневую вершину дерева);

2. Перебор можно прервать ниже любой ИЛИ-вершины, альфа-величина которой не меньше, чем бета-величина одной из предшествующих ей И-вершин.

При этом в случае А говорят, что имеет место альфа-отсечение (поскольку отсекаются ветви дерева, начиная с ИЛИ-вершин, которым приписана альфа-величина), а в случае В  бета-отсечение (поскольку отсекаются ветви, начинающиеся с бета-величин).

Важно, что рассмотренные правила работают в ходе построения игрового дерева вглубь; это означает, что предварительные оценки промежуточных вершин появляются лишь по мере продвижения от концевых вершин дерева вверх к корню и реально отсечения могут начаться только после того, как получена хотя бы одна точная минимаксная оценка промежуточной вершины.

В рассмотренном примере на рис. 20 первое прерывание перебора было бета-отсечением, а второе  альфа-отсечением. Причем в обоих случаях отсечение было неглубоким, поскольку необходимая для соблюдения соответствующего правила отсечения предварительная оценка (альфа- или бета-величина) находилась в непосредственно предшествующей (к точке отсечения) вершине. В общем же случае она может находиться существенно выше отсекаемой ветви – на пути от вершины, ниже которой производится отсечение, к начальной вершине, включая последнюю.

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

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