Альфа-бета-отсечение

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

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

Image

Этот подход может также рассматриваться под другим углом — как упрощение формулы для получения минимаксного значения Minimax-Value. Допустим, что два преемника узла С на рис. 6.4, еще не обработанные в процессе вычисления, имеют значения х и у, и предположим, что z — минимальное значение среди х и у.В таком случае значение корневого узла можно найти следующим образом:

Image

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

Image

Рис. 6.5. Альфа-бета-отсечение: общий случай. Если для Игрока узел m лучше чем п, то узел п никогда не встретится в игре

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

  • а = значение наилучшего варианта (т.е. варианта с самым высоким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока МАХ;
  • Р = значение наилучшего варианта (т.е. варианта с самым низким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока MIN.

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


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

function Alpha-Beta-Search(state) returns действие action
  inputs: state, текущее состояние в игре
  v <— Max-Value (state, -«>, +oo)
return действие action из множества Successors(state) со значением v

function Max-Value(state, a, C) returns значение полезности
  inputs: state, текущее состояние в игре
  а, значение наилучшей альтернативы для игрока МАХ вдоль
  пути к состоянию state
  C, значение наилучшей альтернативы для игрока MIN вдоль
  пути к состоянию state
  if Terminal-Test(state) then return Utility(state)
  v <— -oo
  for a, s in Successors(state) do
  v <- Max(y, Min-Value(s, a, C))
  if v > C then return v
  a <- Max (a, v)
return v

function Min-Value(state, a, |3) returns значение полезности
  inputs: state, текущее состояние в игре
  а, значение наилучшей альтернативы для игрока МАХ вдоль
  пути к состоянию state
  C, значение наилучшей альтернативы для игрока MIN вдоль
  пути к состоянию state
  if Terminal-Test(state) then return Utility(state)
  for a, s in Successors(state) do
  v <r- Min(v, Max-Value(s, a, |3) )
  if v < a then return v
  P <r- Min(P, v)
return v


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

Если принять допущение, что это может быть сделано, то окажется, что в алгоритме альфа-бета-отсечения для определения наилучшего хода достаточно исследовать только 0(lf/2) узлов, а не О (If1) узлов, как при использовании минимаксного алгоритма. Это означает, что эффективный коэффициент ветвления становится равным-\/5, а не Ь; например, для шахмат он равен б, а не 35. Иными словами, за  такое же время альфа-бета-поиск позволяет заглянуть в дерево игры примерно в два раза дальше по сравнению с минимаксным поиском. А если исследование преемников происходит в случайном порядке, а не по принципу первоочередного выбора наилучших вариантов, то при умеренных значениях Ь общее количество исследованных узлов будет составлять примерно 0(Ь3тП). В случае шахмат применение довольно простой функции упорядочения (например, такой, в которой в первую очередь рассматриваются взятия фигур, затем угрозы, затем ходы вперед, а после этого ходы назад) позволяет оставаться в пределах, не превышающих удвоенное значение
результата 0(if/2), который может быть получен в наилучшем случае. Добавление инамических схем упорядочения ходов, в частности, таких, в которых в первую очередь проверяются ходы, обозначенные как наилучшие на предыдущем этапе, позволяют подойти совсем близко к этому теоретическому пределу.

Как было отмечено, наличие повторяющихся состояний в дереве поиска может вызвать экспоненциальное увеличение стоимости поиска. В играх повторяющиеся состояния встречаются часто из-за возникновения транспозиций — различных перестановок последовательностей ходов, которые оканчиваются в одной той же позиции. Например, если белые имеют в своем распоряжении ход al5 на оторый черные могут ответить ходом Ьх, а также еще один не связанный с ним ход а2 на другой стороне доски, на который может быть дан ответ Ь2, то обе последовательности, [alfblra2fb2] и [а1,Ь2,а2,Ь1], оканчиваются в одной и той же позиции (как и перестановки, начинающиеся с а2). Поэтому целесообразно сохранять оценку каждой конкретной позиции в хэш-таблице при первом ее возникновении, чтобы не приходилось вычислять ее повторно при последующих возникновениях. По традиции хэш-таблица с ранее встретившимися позициями называется таблицей транспозиций; она по сути идентична списку closed в алгоритме Graph-Search.

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