Поиск основных вариантов (иногда приравниваемый к практически идентичному NegaScout ) - это алгоритм негамакса , который может быть быстрее, чем обрезка альфа-бета . Подобно альфа-бета-обрезке, 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 в негамаксном режиме были изобретены независимо JP Fishburn и использовались в алгоритме, аналогичном SCOUT в приложении к его докторской диссертации. thesis, [5] в параллельном альфа-бета-алгоритме, [6] и на последнем поддереве корневого узла дерева поиска. [7]
Идея
Большинство ходов неприемлемы для обоих игроков, поэтому нам не нужно полностью перебирать каждый узел, чтобы получить точный счет. Точный счет нужен только в основном варианте (последовательность ходов, приемлемая для обоих игроков), который, как ожидается, будет распространяться до корня. При итеративном поиске с углублением предыдущая итерация уже установила такую последовательность. В узле, который имеет счет, который оказывается внутри окна, который называется PV-узлом, мы ищем первый ход, который считается лучшим, в полном окне, чтобы установить границу. Это нужно, чтобы доказать неприемлемость других ходов. Мы провели поиск в нулевом окне, чтобы проверить, может ли ход быть лучше. Поскольку поиск с нулевым окном намного дешевле, он может сэкономить много усилий. Если мы обнаруживаем, что ход может повысить альфу, мы проводим повторный поиск во всем окне, чтобы получить точный счет. [8] [9]
Псевдокод
функция pvs (узел, глубина, α, β, цвет) - если глубина = 0 или узел является конечным узлом, тогда возвращает цвет × эвристическое значение узла для каждого дочернего элемента узла do, если дочерний элемент является первым дочерним узлом , то оценка: = −pvs (ребенок, глубина - 1, −β, −α, −цвет) иначе оценка: = −pvs (ребенок, глубина - 1, −α - 1, −α, −color) (* поиск с пустым окном *), если α <оценка <β, то оценка: = −pvs (ребенок, глубина - 1, −β, −score, −color) (* если не получилось, выполните полный повторный поиск *) α: = max (α, оценка) если α ≥ β, то break (* бета-отсечка *) вернуть α
Смотрите также
Рекомендации
- ^ А. Райнефельд. Spielbaum-Susverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin (1989), ISBN 3-540-50742-6
- ^ Plaat, Aske; Джонатан Шеффер; Вим Пейлс; Арье де Брюэн (ноябрь 1996 г.). «Лучшие первые минимаксные алгоритмы с фиксированной глубиной». Искусственный интеллект . 87 (1–2): 255–293. DOI : 10.1016 / 0004-3702 (95) 00126-3 .
- ^ Перл, Дж., «SCOUT: простой алгоритм поиска игр с доказанными оптимальными свойствами», Труды Первой ежегодной национальной конференции по искусственному интеллекту, Стэнфордский университет, 18–21 августа 1980 г., стр. 143–145.
- ^ Перл, Дж., «Асимптотические свойства минимаксных деревьев и процедур поиска игр», « Искусственный интеллект», Vol. 14, No. 2, pp. 113-138, сентябрь 1980 г.
- ^ Fishburn, JP, "Анализ ускорения в распределенных алгоритмах", UMI Research Press ISBN 0-8357-1527-2 , 1981, 1984.
- Перейти ↑ Fishburn, JP, Finkel, RA, and Lawless, SA, "Parallel Alpha-Beta Search on Arachne" Proceedings 1980 Int. Конф. Параллельная обработка, IEEE, 26–29 августа 1980 г., стр. 235–243.
- ↑ Fishburn, JP, «Оптимизация альфа-бета-поиска» Бюллетень ACM SIGART , выпуск 72, июль 1980 г., стр. 29–31.
- Перейти ↑ Judea Pearl (1980). Асимптотические свойства минимаксных деревьев и процедуры поиска игр. Искусственный интеллект, Vol. 14, №2
- ^ Мюррей Кэмпбелл, Тони Марсленд (1983). Сравнение алгоритмов поиска по минимаксному дереву. Искусственный интеллект, Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702.