Поиск основного варианта - Principal variation search - Wikipedia

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

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

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

Другой алгоритм поиска называется SSS * теоретически может привести к поиску меньшего количества узлов. Однако его первоначальная формулировка имеет практические проблемы (в частности, она в значительной степени полагается на ОТКРЫТЫЙ список для хранения), и в настоящее время большинство шахматных движков все еще используют форму NegaScout в своем поиске. Большинство шахматных движков используют таблицу транспонирования, в которой хранится соответствующая часть дерева поиска. Эта часть дерева имеет тот же размер, что и список OPEN в SSS *.[2] Переформулировка, названная MT-SSS *, позволила реализовать ее как серию вызовов нулевого окна к Alpha-Beta (или NegaScout), которые используют таблицу транспонирования, и могут быть выполнены прямые сравнения с использованием игровых программ. На практике он не превзошел NegaScout. Еще один алгоритм поиска, который, как правило, работает лучше, чем NegaScout на практике, - это алгоритм лучшего первого, который называется МПД-ф, хотя ни один алгоритм не доминирует над другим. Существуют деревья, в которых NegaScout ищет меньше узлов, чем SSS * или MTD-f, и наоборот.

NegaScout берет свое начало в SCOUT, изобретенном Жемчужина Иудеи в 1980 году, это был первый алгоритм, превзошедший альфа-бета и доказавший свою асимптотическую оптимальность.[3][4] Нулевые окна с β = α + 1 в негамаксном режиме были изобретены независимо Дж. П. Фишберном и использовались в алгоритме, аналогичном SCOUT в приложении к его докторской диссертации. Тезис,[5] в параллельном альфа-бета алгоритме,[6] и на последнем поддереве корневого узла дерева поиска.[7]

Идея

Большинство ходов неприемлемы для обоих игроков, поэтому нам не нужно полностью перебирать каждый узел, чтобы получить точный счет. Точный счет необходим только в основном варианте (последовательность ходов, приемлемая для обоих игроков), который, как ожидается, будет распространяться до корня. При итеративном поиске с углублением предыдущая итерация уже установила такую ​​последовательность. В узле, который имеет счет, который оказывается внутри окна, который называется PV-узлом, мы ищем первый ход, который считается лучшим, в полном окне, чтобы установить границу. Это нужно для того, чтобы доказать неприемлемость других ходов. Мы провели поиск в нулевом окне, чтобы проверить, может ли ход быть лучше. Поскольку поиск с нулевым окном намного дешевле, он может сэкономить много усилий. Если мы обнаруживаем, что ход может повысить альфу, мы проводим повторный поиск во всем окне, чтобы получить точный счет. [8][9]

Псевдокод

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

Рекомендации

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

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

внешняя ссылка