Альфа – бета обрезка - Alpha–beta pruning

Альфа – бета обрезка
Класс	Алгоритм поиска
Наихудшая производительность
Лучшая производительность

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

История

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

Основная идея

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

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

Чтобы проиллюстрировать это на примере из реальной жизни, предположим, что кто-то играет в шахматы, и теперь его очередь. Движение «А» улучшит позицию игрока. Игрок продолжает искать ходы, чтобы не пропустить лучший. Ход «B» также является хорошим ходом, но затем игрок понимает, что он позволит противнику форсировать мат за два хода. Таким образом, другие исходы хода B больше не нужно рассматривать, поскольку противник может форсировать победу. Максимальное количество очков, которое противник может набрать после хода «B», равно отрицательной бесконечности: проигрыш для игрока. Это меньше минимальной позиции, которая была найдена ранее; ход «А» не приводит к принудительному поражению за два хода.

Улучшения по сравнению с наивным минимаксом

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

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

С (среднего или постоянная) ветвящимся фактором из Ь , и глубиной поиска из д слоев , максимальное количество узловых положений листа оценивало (когда упорядочение шага pessimal ) является O ( б × б × ... × б ) = O ( b ^d ) - то же, что и простой минимаксный поиск. Если порядок ходов для поиска оптимален (то есть лучшие ходы всегда ищутся первыми), количество оцененных позиций конечных узлов составляет около O ( b × 1 × b × 1 × ... × b ) для нечетной глубины и O ( b × 1 × b × 1 × ... × 1) для четной глубины, или . В последнем случае, когда уровень поиска является четным, эффективный коэффициент ветвления уменьшается до его квадратного корня , или, что то же самое, поиск может идти вдвое глубже с тем же объемом вычислений. Объяснение b × 1 × b × 1 × ... состоит в том, что все ходы первого игрока должны быть изучены, чтобы найти лучший, но для каждого необходим только лучший ход второго игрока, чтобы опровергнуть все, кроме первого (и лучший) ход первого игрока - альфа-бета гарантирует, что другие ходы второго игрока не учитываются. Когда узлы рассматриваются в случайном порядке (т. Е. Алгоритм рандомизирует), асимптотически ожидаемое количество узлов, оцениваемых в однородных деревьях с двоичными значениями листьев, равно . Для одних и тех же деревьев, когда значения присваиваются значениям листьев независимо друг от друга и говорят, что ноль и один равновероятны, ожидаемое количество оцениваемых узлов равно , что намного меньше, чем работа, выполняемая рандомизированным алгоритмом, упомянутым выше, и снова является оптимальным для таких случайных деревьев. Когда значение листа выбраны независимо друг от друга , но из интервала равномерно случайным образом , ожидаемое число узлов оцениваются возрастает до в пределе, что опять - таки оптимальный для таких рода случайных дерев. Обратите внимание, что фактическая работа для "малых" значений лучше приблизительно определяется с помощью . ${\ Displaystyle О (Ь ^ {d / 2}) = О ({\ sqrt {Ь ^ {d}}})}$ ${\ Displaystyle \ Theta (((b-1 + {\ sqrt {b ^ {2} + 14b + 1}}) / 4) ^ {d})}$ ${\ Displaystyle \ Theta ((b / 2) ^ {d})}$ ${\ displaystyle [0,1]}$ ${\ displaystyle \ Theta (b ^ {d / log (d)})}$ ${\ displaystyle d \ to \ infty}$ ${\ displaystyle d}$ ${\ displaystyle 0.925d ^ {0.747}}$

Шахматная программа, которая ищет четыре слоя со средним числом 36 ветвей на узел, оценивает более одного миллиона конечных узлов. Оптимальная альфа-бета-обрезка устранит все, кроме примерно 2000 конечных узлов, то есть сокращение на 99,8%.

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

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

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

Псевдокод

Псевдокод для минимакса с ограничением глубины с альфа-бета-обрезкой выглядит следующим образом:

Реализации альфа-бета-отсечения часто можно определить по тому, являются ли они «безотказными» или «отказоустойчивыми». При отказоустойчивой альфа-бета функция алфавита может возвращать значения (v), которые превышают (v <α или v> β) границы α и β, установленные ее аргументами вызова функции. Для сравнения, отказоустойчивый альфа-бета ограничивает возвращаемое значение своей функции включительным диапазоном значений α и β. Основное различие между отказоустойчивой и отказоустойчивой реализациями заключается в том, обновляются ли α и β до или после проверки отсечки. Если они обновляются до проверки, то они могут превышать начальные границы, и алгоритм работает без сбоев.

Следующий псевдокод иллюстрирует отказоустойчивый вариант.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then
                break (* α cutoff *)
            β := min(β, value)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Следующий псевдокод иллюстрирует отказоустойчивую альфа-бета.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if value ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if value ≤ α then
                break (* α cutoff *)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Эвристические улучшения

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

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

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

Другие алгоритмы

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

С другой стороны, такие алгоритмы, как SSS * , используют стратегию « лучший - первый» . Это потенциально может сделать их более эффективными по времени, но, как правило, с большими затратами на экономию места.

Смотрите также

использованная литература

Библиография

Джордж Т. Хейнеман; Гэри Поллис; Стэнли Селкоу (2008). «Глава 7: Поиск пути в AI». Об алгоритмах в двух словах . Oreilly Media . С. 217–223. ISBN 978-0-596-51624-6.
Judea Pearl , Heuristics , Addison-Wesley, 1984.
Джон П. Фишберн (1984). «Приложение A: Некоторые оптимизации поиска α-β». Анализ ускорения в распределенных алгоритмах (редакция кандидатской диссертации 1981 г.) . UMI Research Press. С. 107–111. ISBN 0-8357-1527-2.

Languages

In other projects