stringtranslate.com

Поиск основных вариаций

Поиск основных вариаций (иногда приравниваемый к практически идентичному NegaScout ) — это алгоритм negamax , который может быть быстрее, чем alpha–beta pruning . Как и alpha–beta pruning, NegaScout — это алгоритм направленного поиска для вычисления минимаксного значения узла в дереве . Он доминирует над alpha–beta pruning в том смысле, что он никогда не будет исследовать узел, который может быть отсечен alpha–beta; однако он полагается на точное упорядочение узлов, чтобы извлечь выгоду из этого преимущества.

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

Александр Рейнефельд изобрел NegaScout спустя несколько десятилетий после изобретения альфа-бета-обрезки. Он приводит доказательство корректности NegaScout в своей книге. [1]

Другой алгоритм поиска, называемый SSS*, теоретически может привести к меньшему количеству просматриваемых узлов. Однако его первоначальная формулировка имеет практические проблемы (в частности, она в значительной степени опирается на открытый список для хранения), и в настоящее время большинство шахматных движков по-прежнему используют форму NegaScout в своем поиске. Большинство шахматных движков используют таблицу транспозиции, в которой хранится соответствующая часть дерева поиска. Эта часть дерева имеет тот же размер, что и открытый список 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]

Псевдокод

Функция pvs(узел, глубина, α, β, цвет) —  если глубина = 0 или узел является конечным узлом , то  возвращает цвет × эвристическое значение узла для каждого дочернего узла ,  если дочерний узел является первым дочерним узлом , то оценка := −pvs(ребенок, глубина − 1, −β, −α, −цвет) else score := −pvs(child, depth − 1, −α − 1, −α, −color) (* поиск с нулевым окном *)  if α < score < β then score := −pvs(child, depth − 1, −β, −α, −color) (* если не удалось выполнить high, выполнить полный повторный поиск *) α := max(α, оценка) если α ≥ β , то  перерыв  (* бета-отсечка *)  вернуть α

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

Ссылки

  1. ^ А. Райнефельд. Шпильбаум-Зухверфарен. Informatik-Fachbericht 200, Springer-Verlag, Берлин (1989), ISBN  3-540-50742-6
  2. ^ Плаат, Аске; Джонатан Шеффер; Вим Пейлс; Арье де Брюин (ноябрь 1996 г.). «Наилучшие минимаксные алгоритмы фиксированной глубины». Искусственный интеллект . 87 (1–2): 255–293. дои : 10.1016/0004-3702(95)00126-3 .
  3. ^ Перл, Дж., «SCOUT: простой алгоритм поиска игр с доказанными оптимальными свойствами», Труды Первой ежегодной национальной конференции по искусственному интеллекту, Стэнфордский университет, 18–21 августа 1980 г., стр. 143–145.
  4. ^ Перл, Дж., «Асимптотические свойства минимаксных деревьев и процедуры поиска в играх», Искусственный интеллект, т. 14, № 2, стр. 113–138, сентябрь 1980 г.
  5. ^ Фишберн, Дж. П., «Анализ ускорения в распределенных алгоритмах», UMI Research Press ISBN 0-8357-1527-2 , 1981, 1984. 
  6. ^ Фишберн, Дж. П., Финкель, Р. А. и Лоулесс, С. А., «Параллельный альфа-бета-поиск на Arachne», Труды Международной конференции 1980 г. по параллельной обработке, IEEE, 26–29 августа 1980 г., стр. 235–243.
  7. ↑ Фишберн, Дж. П., «Оптимизация поиска альфа–бета» Бюллетень ACM SIGART , выпуск 72, июль 1980 г., стр. 29–31.
  8. ^ Judea Pearl (1980). Асимптотические свойства минимаксных деревьев и процедуры поиска в играх. Искусственный интеллект, т. 14, № 2
  9. ^ Мюррей Кэмпбелл, Тони Марсленд (1983). Сравнение алгоритмов поиска в минимаксном дереве. Искусственный интеллект, т. 20, № 4, стр. 347–367. ISSN 0004-3702.

Внешние ссылки