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

Привет, мой друг, тебе интересно узнать все про альфа-бета-отсечение, тогда с вдохновением прочти до конца. Для того чтобы лучше понимать что такое альфа-бета-отсечение , настоятельно рекомендую прочитать все из категории Математические методы исследования операций .Теория игр и расписаний..

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

История

Аллен Ньюэлл и Герберт Саймон, использовавшие то, что Джон Маккарти назвал «аппроксимацией» в 1958 году, написали, что альфа-бета-отсечение, «кажется, изобреталось неоднократно» . Артур Самуэль, Ричардс, Харт, Левин, Эдвардс независимо предлагали ранние версии этого алгоритма . Маккарти также выдвигал подобные идеи на Дартмутском семинаре в 1956 году, а затем, в 1961 году, предложил для исследования группе своих студентов в MIT, включая Алана Котока . Александр Брудно независимо открыл алгоритм и опубликовал свои результаты в 1963 году . В 1975 году Дональд Кнут и Рональд Мур усовершенствовали алгоритм, добавив «бета»-отсечения .

Оптимизация минимакса

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

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

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

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

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

Рис. 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 if v < a then return v
P 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.

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

Вау!! 😲 Ты еще не читал? Это зря!

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