Из Википедии, бесплатной энциклопедии
  (Перенаправлено из альфа-бета-обрезки )
Перейти к навигации Перейти к поиску
Для использования в других целях, см Алфавит (значения) .
Альфа – бета обрезка
Учебный классАлгоритм поиска
Наихудшая производительность
Лучшая производительность
Алгоритмы поиска по графам и деревьям
Списки
похожие темы

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

История [ править ]

Аллен Ньюэлл и Герберт А. Саймон, которые использовали то, что Джон Маккарти называет «приближением» [2] в 1958 году, писали, что альфа-бета «по-видимому, повторно изобреталась несколько раз». [3] У Артура Сэмюэля была ранняя версия симуляции шашек. Ричардс, Тимоти Харт, Майкл Левин и / или Дэниел Эдвардс также независимо изобрели альфа-бета в Соединенных Штатах . [4] Маккарти предложил аналогичные идеи во время семинара в Дартмуте в 1956 году и предложил их группе своих студентов, включая Алана Котока из Массачусетского технологического института в 1961 году. [5] Александр Бруднонезависимо разработал альфа-бета алгоритм, опубликовав свои результаты в 1963 году. [6] Дональд Кнут и Рональд В. Мур усовершенствовали алгоритм в 1975 году. [7] [8] Джудея Перл доказала его оптимальность с точки зрения ожидаемого времени работы для деревьев со случайно назначенными листовыми значениями в двух статьях. [9] [10] Оптимальность рандомизированной версии альфа-бета была показана Майклом Саксом и Ави Вигдерсон в 1986 году. [11]

Основная идея [ править ]

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

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

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

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

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

С (среднего или постоянная) ветвящимся фактором из Ь , и глубиной поиска из д слоев , максимальное количество узловых положений листа оценивало (когда упорядочение шага pessimal ) является O ( б × б × ... × б ) = O ( b d ) - то же, что и простой минимаксный поиск. Если порядок ходов для поиска оптимален (то есть лучшие ходы всегда ищутся первыми), количество оцененных позиций конечных узлов составляет около O ( b × 1 × b × 1 × ... × b ) для нечетной глубины и O (b × 1 × b × 1 × ... × 1) для четной глубины, или . В последнем случае, когда уровень поиска является четным, эффективный коэффициент ветвления уменьшается до его квадратного корня , или, что то же самое, поиск может идти вдвое глубже с тем же объемом вычислений. [12] Объяснение b × 1 × b× 1 × ... состоит в том, что все ходы первого игрока должны быть изучены, чтобы найти лучший, но для каждого необходим только лучший ход второго игрока, чтобы опровергнуть все, кроме первого (и лучшего) хода первого игрока - альфа - beta гарантирует, что никакие другие ходы второго игрока не нужно рассматривать. Когда узлы рассматриваются в случайном порядке (т. Е. Алгоритм рандомизирует), асимптотически ожидаемое количество узлов, оцениваемых в однородных деревьях с двоичными значениями листьев, равно . [11] Для одних и тех же деревьев, когда значения присваиваются значениям листьев независимо друг от друга и говорят, что ноль и один равновероятны, ожидаемое количество оцениваемых узлов равно , что намного меньше, чем работа, выполненная рандомизированным Алгоритм, упомянутый выше, и снова является оптимальным для таких случайных деревьев. [9]Когда значение листа выбраны независимо друг от друга , но из интервала равномерно случайным образом , ожидаемое число узлов оценивается возрастает до в пределе, [10] , который является оптимальным для вновь этих рода случайных дерев. Обратите внимание, что фактическая работа для "малых" значений лучше приблизительно определяется с помощью . [10] [9]

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

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

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

Псевдокод [ править ]

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

функция алфавитa (узел, глубина, α, β, maximizingPlayer) -  если depth = 0 или node является конечным узлом, то  возвращает эвристическое значение узла, если maximizingPlayer, то значение: = −∞ для каждого дочернего элемента узла сделать значение: = макс (значение, алфавит (дочерний элемент, глубина - 1, α, β, ЛОЖЬ)) α: = max (α, значение) если α ≥ β, то  break  (* β cutoff *)  вернуть значение иначе значение: = + ∞ для каждого дочернего элемента узла сделать значение: = min (значение, алфавитa (дочерний элемент, глубина - 1, α, β, ИСТИНА)) β: = min (β, значение) если β ≤ α, то  break  (* α cutoff *)  возвращает значение
(* Первоначальный вызов *)
алфавитa (происхождение, глубина, - ∞ , + ∞ , ИСТИНА)

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

Эвристические улучшения [ править ]

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

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

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

Другие алгоритмы [ править ]

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

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

См. Также [ править ]

  • Минимакс
  • Expectiminimax
  • Негамакс
  • Обрезка (алгоритм)
  • Ветвь и переплет
  • Комбинаторная оптимизация
  • Поиск основного варианта
  • Таблица транспонирования

Ссылки [ править ]

  1. ^ Рассел, Стюарт Дж .; Норвиг, Питер (2010). Искусственный интеллект: современный подход (3-е изд.). Река Аппер Сэдл, Нью-Джерси: Pearson Education, Inc. стр. 167. ISBN. 978-0-13-604259-4.
  2. ↑ Маккарти, Джон (27 ноября 2006 г.). «ИИ человеческого уровня сложнее, чем казалось в 1955 году» . Проверено 20 декабря 2006 .
  3. ^ Ньюэлл, Аллен; Саймон, Герберт А. (1 марта 1976 г.). «Информатика как эмпирическое исследование: символы и поиск» . Коммуникации ACM . 19 (3): 113–126. DOI : 10.1145 / 360018.360022 .
  4. ^ Эдвардс, диджей; Харт, Т.П. (4 декабря 1961 г.). «Альфа-бета-эвристика (AIM-030)». Массачусетский технологический институт . ЛВП : 1721,1 / 6098 . Цитировать журнал требует |journal=( помощь )
  5. ^ Коток, Алан (3 декабря 2004). «Памятка 41 Массачусетского технологического института по искусственному интеллекту» . Проверено 1 июля 2006 .
  6. ^ Marsland, TA (май 1987). "Компьютерные шахматные методы (PDF) из Энциклопедии искусственного интеллекта. С. Шапиро (редактор)" (PDF) . J. Wiley & Sons. С. 159–171. Архивировано из оригинального (PDF) 30 октября 2008 года . Проверено 21 декабря 2006 .
  7. ^ Кнут, Дональд Э .; Мур, Рональд В. (1975). «Анализ альфа-бета обрезки». Искусственный интеллект . 6 (4): 293–326. DOI : 10.1016 / 0004-3702 (75) 90019-3 . S2CID 7894372 . 
  8. ↑ Абрамсон, Брюс (1 июня 1989 г.). «Стратегии управления для игр двух игроков». ACM Computing Surveys . 21 (2): 137–161. DOI : 10.1145 / 66443.66444 . S2CID 11526154 . 
  9. ^ a b c Жемчуг, Иудея (1980). «Асимптотические свойства минимаксных деревьев и процедуры поиска игры». Искусственный интеллект . 14 (2): 113–138. DOI : 10.1016 / 0004-3702 (80) 90037-5 .
  10. ^ a b c Жемчуг, Иудея (1982). «Решение для фактора ветвления алгоритма альфа-бета-отсечения и его оптимальность». Коммуникации ACM . 25 (8): 559–64. DOI : 10.1145 / 358589.358616 . S2CID 8296219 . 
  11. ^ а б Сакс, М .; Вигдерсон, А. (1986). «Вероятностные булевы деревья решений и сложность оценки игровых деревьев». 27-й ежегодный симпозиум по основам информатики . С. 29–38. DOI : 10.1109 / SFCS.1986.44 . ISBN 0-8186-0740-8. S2CID  6130392 .
  12. ^ a b Рассел, Стюарт Дж .; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Prentice Hall, ISBN 0-13-790395-2
  13. ↑ Перл, Иудея ; Корф, Ричард (1987), «Методы поиска», Annual Review of Computer Science , 2 : 451–467, doi : 10.1146 / annurev.cs.02.060187.002315 , Как и его аналог A * для однопользовательских игр, 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.