Поиск основных вариантов
Поиск основных вариантов (иногда приравниваемый к практически идентичному NegaScout ) — это алгоритм negamax , который может быть быстрее, чем альфа-бета-отсечение . Как и альфа-бета-отсечение, NegaScout представляет собой алгоритм направленного поиска для вычисления минимаксного значения узла в дереве . Он доминирует над альфа-бета-отсечением в том смысле, что никогда не исследует узел, который можно отсечь с помощью альфа-бета; однако, чтобы воспользоваться этим преимуществом, он полагается на точный порядок узлов.
NegaScout работает лучше всего при правильном порядке ходов. На практике порядок ходов часто определяется предыдущими более мелкими поисками. Он дает больше отсечений, чем альфа-бета, если предположить, что первый исследованный узел является лучшим. Другими словами, предполагается, что первый узел находится в основном варианте . Затем он может проверить, так ли это, выполнив поиск в оставшихся узлах с помощью нулевого окна (также известного как окно поиска; когда альфа и бета равны), что быстрее, чем поиск с использованием обычного окна альфа-бета. Если доказательство не удалось, то первый узел не принадлежал к основному варианту, и поиск продолжается как обычный альфа-бета. Следовательно, NegaScout работает лучше всего, когда порядок ходов правильный. При случайном порядке ходов NegaScout займет больше времени, чем обычная альфа-бета; хотя он не будет исследовать ни один узел, которого не исследовали альфа-бета, ему придется повторно исследовать множество узлов.
Александр Рейнефельд изобрел NegaScout через несколько десятилетий после изобретения альфа-бета-обрезки. В своей книге он приводит доказательство правильности NegaScout. [1]
Другой алгоритм поиска, называемый SSS*, теоретически может привести к меньшему количеству обыскиваемых узлов. Однако его первоначальная формулировка имеет практические проблемы (в частности, она в значительной степени опирается на ОТКРЫТЫЙ список для хранения), и в настоящее время большинство шахматных движков все еще используют форму NegaScout в своем поиске. Большинство шахматных движков используют таблицу транспонирования, в которой хранится соответствующая часть дерева поиска. Эта часть дерева имеет тот же размер, что и список OPEN в SSS*. [2] Переформулировка под названием MT-SSS* позволила реализовать ее как серию нулевых оконных вызовов Alpha-Beta (или NegaScout), которые используют таблицу транспонирования, и можно было проводить прямые сравнения с использованием игровых программ. На практике он не превзошел NegaScout. Еще один алгоритм поиска, который на практике работает лучше, чем NegaScout, — это алгоритм «сначала лучший», называемый MTD(f) , хотя ни один из алгоритмов не доминирует над другим. Существуют деревья, в которых NegaScout ищет меньше узлов, чем SSS* или MTD(f), и наоборот.
NegaScout создан по образцу SCOUT, изобретенного Джудеей Перл в 1980 году и ставшего первым алгоритмом, превзошедшим по производительности альфа-бета и доказавшим свою асимптотически оптимальную эффективность. [3] [4] Нулевые окна с β=α+1 в негамаксной настройке были независимо изобретены Дж. П. Фишберном и использованы в алгоритме, аналогичном SCOUT, в приложении к его докторской диссертации. диссертация, [5] в параллельном альфа-бета-алгоритме, [6] и в последнем поддереве корневого узла дерева поиска. [7]
Идея
[ редактировать ]Большинство ходов неприемлемы для обоих игроков, поэтому нам не нужно полностью перебирать каждый узел, чтобы получить точный результат. Точный результат необходим только для узлов основного варианта (оптимальной последовательности ходов для обоих игроков), где он будет распространяться до корня. При итеративном поиске с углублением предыдущая итерация уже установила кандидата на такую последовательность, которую также обычно называют основной вариацией. Для любого нелистового узла в этом основном варианте его дочерние элементы переупорядочиваются таким образом, что следующий узел из этого основного варианта является первым дочерним элементом. Предполагается, что все остальные дочерние элементы приведут к худшему или равному результату для текущего игрока (это предположение следует из предположения, что текущий кандидат PV является реальным PV). Чтобы проверить это, мы ищем первый ход с полным окном, чтобы установить верхнюю границу счета других детей, для чего мы проводим поиск с нулевым окном, чтобы проверить, может ли ход быть лучше. Поскольку поиск с нулевым окном обходится намного дешевле из-за более высокой частоты обрезания бета-версии, это может сэкономить много усилий. Если мы обнаружим, что ход может повысить альфу, наше предположение для этого хода опровергается, и мы проводим повторное исследование с полным окном, чтобы получить точный результат. [8] [9]
Псевдокод
[ редактировать ]function pvs(node, depth, α, β, color) is
if depth = 0 or node is a terminal node then
return color × the heuristic value of node
for each child of node do
if child is first child then
score := −pvs(child, depth − 1, −β, −α, −color)
else
score := −pvs(child, depth − 1, −α − 1, −α, −color) (* search with a null window *)
if α < score < β then
score := −pvs(child, depth − 1, −β, −α, −color) (* if it failed high, do a full re-search *)
α := max(α, score)
if α ≥ β then
break (* beta cut-off *)
return α
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ А. Райнефельд. Метод поиска в дереве игр. Отчет по компьютерным наукам 200, Springer-Verlag, Берлин (1989), ISBN 3-540-50742-6
- ^ Плаат, Аске; Джонатан Шеффер; Вим Пейлс; Арье де Брюэн (ноябрь 1996 г.). «Минимаксные алгоритмы с фиксированной глубиной и лучшими первыми» . Искусственный интеллект . 87 (1–2): 255–293. дои : 10.1016/0004-3702(95)00126-3 .
- ^ Перл, Дж., «SCOUT: простой алгоритм поиска игр с доказанными оптимальными свойствами», Материалы первой ежегодной национальной конференции по искусственному интеллекту, Стэнфордский университет, 18–21 августа 1980 г., стр. 143–145.
- ^ Перл, Дж., «Асимптотические свойства минимаксных деревьев и процедур поиска игр», Искусственный интеллект, том. 14, нет. 2, стр. 113–138, сентябрь 1980 г.
- ^ Фишберн, JP, «Анализ ускорения распределенных алгоритмов», UMI Research Press ISBN 0-8357-1527-2 , 1981, 1984.
- ^ Фишберн, Дж.П., Финкель, Р.А., и Лоулесс, С.А., «Параллельный альфа-бета-поиск на Арахне», Труды 1980 Int. Конф. Параллельная обработка, IEEE, 26–29 августа 1980 г., стр. 235–243.
- ^ Фишберн, Дж. П., «Оптимизация альфа-бета-поиска» , бюллетень ACM SIGART , выпуск 72, июль 1980 г., стр. 29–31.
- ^ Иудея Перл (1980). Асимптотические свойства минимаксных деревьев и процедуры поиска игр. Искусственный интеллект, том. 14, нет. 2
- ^ Мюррей Кэмпбелл, Тони Марсленд (1983). Сравнение алгоритмов поиска по минимаксному дереву. Искусственный интеллект, том. 20, нет. 4, стр. 347–367. ISSN 0004-3702.