Альфа – бета сокращение

редактировать

Алгоритм поиска, который стремится уменьшить количество узлов в дереве поиска минимаксного алгоритма

Отсечение альфа-бета
Класс	Алгоритм поиска
Худший случай производительность	$O ( bd) {\ displaystyle O (b ^ {d})}$ $О (b ^ d)$
в лучшем случае производительность	$O (bd) {\ displaystyle O \ left ({\ sqrt {b ^ {d} }} \ right)}$ ${\ displaystyle O \ left ({\ sqrt {b ^ {d}}} \ right)}$

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

Содержание

1 История
2 Основная идея
3 Улучшения за наивный минимакс
4 Псевдокод
5 Эвристические улучшения
6 Другие алгоритмы
7 См. также
8 Ссылки
9 Библиография

История

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

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

Алгоритм поддерживает два значения, альфа и бета, которые соответственно представляют минимальное оценка, в которой гарантирован максимизирующий игрок, и максимальная оценка, в которой гарантирован минимизирующий игрок. Первоначально альфа - это отрицательная бесконечность, а бета - положительная бесконечность, то есть оба игрока начинают с худшим из возможных результатов. Каждый раз, когда максимальное количество очков, которое гарантировано минимизирующему игроку (т. Е. «Бета-игроку») становится меньше минимального количества очков, гарантированного максимизирующему игроку (т. Е. «Альфа-игроку») (т. Е. Бета < alpha), the maximizing player need not consider further descendants of this node, as they will never be reached in the actual play.

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

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

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

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

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

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

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

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

Псевдокод

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

function alpha (node, depth, α, β, maximizingPlayer) isifdepth = 0 или узел является конечным узлом, затемвозвращает эвристическое значение узла, если maximizingPlayer, то value: = −∞ для каждого дочернего узла do value: = max (value, alpha (child, depth - 1, α, β, FALSE)) α: = max (α, значение) если α ≥ β тогдаbreak (* β cutoff *) вернуть значение else value: = + ∞ для каждого дочернего узла do value: = min (value, alpha (child, depth - 1, α, β, TRUE)) β: = min ( β, значение) если β ≤ α, тогдаbreak (* α cutoff *) вернуть value

(* Первоначальный вызов *) alpha (origin, depth, - ∞, + ∞, TRUE)

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

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

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

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

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

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

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

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

См. Также

Ссылки

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

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