АЛЬФА-БЕТА-ОТСЕЧЕНИЕ
При минимаксном поиске проблема состоит в том, что количество состояний игры, которые должны быть исследованы в процессе поиска, зависит экспоненциально от количества ходов. К сожалению, такую экспоненциальную зависимость устранить невозможно, но фактически существует возможность сократить ее наполовину. Весь секрет состоит в том, что вычисление правильного минимаксного решения возможно без проверки каждого узла в дереве игры. Это означает, что можно позаимствовать идею отсечения, описанную в главе 4, чтобы исключить из рассмотрения большие части дерева. Конкретный метод, рассматриваемый в данной главе, называется альфа-бета-отсечением. Будучи применен к стандартному минимаксному дереву, этот метод возвращает такие же ходы, которые вернул бы минимаксный метод, но отсекает ветви, по всей вероятности, не способные повлиять на окончательное решение.
Снова рассмотрим дерево игры с двумя полуходами (см. рис. 6.2) и еще раз проведем расчет оптимального решения, на сей раз обращая особое внимание на то, что известно на каждом этапе этого процесса. Пояснения к данным этапам вычисления приведены на рис. 6.4. Результат состоит в том, что минимаксное решение можно выявить, даже не приступая к вычислению значений двух листовых узлов.
Этот подход может также рассматриваться под другим углом — как упрощение формулы для получения минимаксного значения Minimax-Value. Допустим, что два преемника узла С на рис. 6.4, еще не обработанные в процессе вычисления, имеют значения х и у, и предположим, что z — минимальное значение среди х и у. В таком случае значение корневого узла можно найти следующим образом:
Minimax-Value(root) = max(min(3, 12, 8), min(2, x, у), min(14, 5, 2)) = max(3, min(2, x, y), 2) = max(3 , z, 2) где z < 2
= 3
Иными словами, значение корневого узла, а следовательно, и минимаксное решение не зависит от значений отсеченных листовых узлов х и у.
Альфа-бета-отсечение может применяться к деревьям любой глубины; к тому же часто возникает возможность отсекать целые поддеревья, а не просто листья. Общий принцип состоит в следующем: рассмотрим узел л, находящийся где-либо в дереве (рис. 6.5), такой, что участник игры со стороны наблюдателя (назовем его Игрок) имеет возможность выбрать ход, ведущий к этому узлу. Но если Игрок имеет лучший выбор т либо в родительском узле узла л, либо в любой другой точке выбора, находящейся еще выше в дереве, то узел п никогда не будет достигнут в игре, происходящей в действительности. Поэтому после получения достаточной информации об узле л (путем исследования некоторых из его потомков) для того, чтобы с полной уверенностью прийти к этому заключению, можно выполнить его отсечение.
Напомним, что минимаксный поиск осуществляется в глубину, поэтому в любой момент времени достаточно рассматривать узлы вдоль единственного пути в дереве. Алгоритм альфа-бета-отсечения получил свое название по следующим двум параметрам, которые представляют пределы в зарезервированных значениях, присутствующих во всех узлах вдоль этого пути:
• а = значение наилучшего варианта (т.е. варианта с самым высоким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока МАХ;
• Р = значение наилучшего варианта (т.е. варианта с самым низким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока MIN.
Алгоритм альфа-бета-поиска в процессе своей работы обновляет значения ос и Р, а также отсекает оставшиеся ветви в узле (т.е. прекращает рекурсивные вызовы), как только становится известно, что значение текущего узла хуже по сравнению с текущим значением а или Р для игрока МАХ или MIN соответственно. Полный алгоритм приведен в листинге 6.2. Рекомендуем читателю проследить за его поведением применительно к дереву, показанному на рис. 6.4.
Листинг 6.2. Алгоритм альфа-бета-поиска. Обратите внимание на то, что применяемые здесь процедуры остаются такими же, как и процедуры алгоритма Minimax, приведенного в листинге 6.1, за исключением двух строк, введенных как в процедуру Min-Value, так и в Max-Value, которые сопровождают значения ос и Р (а также выполняют соответствующие действия по дальнейшей передаче этих параметров)
function Alpha-Beta-Search(state) returns действие action inputs: state, текущее состояние в игре
v
function Max-Value(state, a, P) returns значение полезности inputs: state, текущее состояние в игре
а, значение наилучшей альтернативы для игрока МАХ вдоль
пути к состоянию state Р, значение наилучшей альтернативы для игрока MIN вдоль пути к состоянию state
if Terminal-Test(state) then return Utility(state)
v
v <- Max(v, Min-Value(s, a, P))
if v > P then return v
a
а, значение наилучшей альтернативы для игрока МАХ вдоль
пути к состоянию state Р, значение наилучшей альтернативы для игрока MIN вдоль пути к состоянию state
if Terminal-Test(state) then return Utility(state) v <— +°°
for a, s in Successors(state) do
v <- Min(v, Max-Value(s, a, P))
if v < a then return v
P <- Min(P, v) return v
Эффективность алгоритма альфа-бета-отсечения в высшей степени зависит от того, в каком порядке происходит проверка преемников. Например, на рис. 6.4, d, е невозможно было бы вообще выполнить отсечение каких-либо преемников узла D, поскольку в первую очередь были бы сформированы наихудшие преемники (с точки зрения игрока MIN). А если бы в первую очередь был сформирован третий преемник, то была бы возможность отсечь двух остальных. На основании этого можно сделать вывод, что имеет смысл стремиться исследовать в первую очередь таких преемников, которые, по всей вероятности, могут стать наилучшими.
Если принять допущение, что это может быть сделано2, то окажется, что в алгоритме альфа-бета-отсечения для определения наилучшего хода достаточно исследовать только 0(1Г/2) узлов, а не О (If1) узлов, как при использовании минимаксного алгоритма. Это означает, что эффективный коэффициент ветвления становится равным-\/Б, а не Ь; например, для шахмат он равен 6, а не 35. Иными словами, за такое же время альфа-бета-поиск позволяет заглянуть в дерево игры примерно в два раза дальше по сравнению с минимаксным поиском. А если исследование преемников происходит в случайном порядке, а не по принципу первоочередного выбора наилучших вариантов, то при умеренных значениях Ь общее количество исследованных узлов будет составлять примерно 0(Ь3т/4). В случае шахмат применение довольно простой функции упорядочения (например, такой, в которой в первую очередь рассматриваются взятия фигур, затем угрозы, затем ходы вперед, а после этого ходы назад) позволяет оставаться в пределах, не превышающих удвоенное значение результата 0(if/2), который может быть получен в наилучшем случае. Добавление динамических схем упорядочения ходов, в частности, таких, в которых в первую очередь проверяются ходы, обозначенные как наилучшие на предыдущем этапе, позволяют подойти совсем близко к этому теоретическому пределу.
Как было отмечено в главе 3, наличие повторяющихся состояний в дереве поиска может вызвать экспоненциальное увеличение стоимости поиска. В играх повторяющиеся состояния встречаются часто из-за возникновения транспозиций — различных перестановок последовательностей ходов, которые оканчиваются в одной и той же позиции. Например, если белые имеют в своем распоряжении ход а1? на который черные могут ответить ходом Ьь а также еще один не связанный с ним ход а2 на другой стороне доски, на который может быть дан ответ Ь2, то обе последовательности, [alfblfa2fb2] и [а1, b2, а2, Ь±], оканчиваются в одной и той же позиции (как и перестановки, начинающиеся с а2). Поэтому целесообразно сохранять оценку каждой конкретной позиции в хэш-таблице при первом ее возникновении, чтобы не приходилось вычислять ее повторно при последующих возникновениях. По традиции хэш-таблица с ранее встретившимися позициями называется таблицей транспозиций; она по сути идентична списку closed в алгоритме Graph-Search (см. с. 139). Использование таблицы транспозиций может оказать чрезвычайно эффективное воздействие, которое иногда выражается в удваивании достижимой глубины поиска в шахматах. С другой стороны, если существует возможность вычислять оценки со скоростью в несколько миллионов узлов в секунду, то практически нет смысла хранить данные обо всех этих узлах в таблице транспозиций. Для выбора наиболее ценных из этих узлов были опробованы различные стратегии.