Поиск по контрольному номеру - Proof-number search

Поиск по контрольному номеру (кратко: поиск PN) - это игровое дерево алгоритм поиска изобретен Виктор Аллис,^[1] с приложениями в основном в решатели эндшпиля, но также и для дополнительных целей во время игр.

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

Каждому узлу частично расширенного игрового дерева соответствует номер доказательства и номер доказательства. Номер доказательства представляет собой минимальное количество листовых узлов, которые необходимо доказать, чтобы подтвердить узел. Аналогично, номер опровержения представляет собой минимальное количество листьев, которые должны быть опровергнуты, чтобы опровергнуть узел. Поскольку цель дерева - доказать принудительный выигрыш, выигрышные узлы считаются доказанными. Следовательно, они имеют номер доказательства 0 и номер опровержения ∞. Потерянные или нарисованные узлы считаются опровергнутыми. У них номер доказательства ∞ и номер опровержения 0. Неизвестные листовые узлы имеют доказательство и опровержение, равное единице. Число доказательств внутреннего узла И равно сумме номеров доказательств его дочерних элементов, поскольку для доказательства узла И должны быть доказаны все дочерние элементы. Номер опровержения узла И равен минимуму его детских номеров опровержения. Номер опровержения внутреннего узла ИЛИ равен сумме номеров опровержения его дочерних узлов, поскольку для опровержения узла ИЛИ должны быть опровергнуты все дочерние элементы. Его количество доказательств равно минимуму из его детских доказательств.

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

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

Некоторые варианты поиска номера доказательства, такие как dfPN, PN², ПДС-ПН^[2] были разработаны для удовлетворения довольно больших требований алгоритма к памяти.

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

1. Аллис, Л. Виктор. Поиск решений в играх и искусственном интеллекте. Кандидатская диссертация. ISBN  90-9007488-0. Архивировано 4 декабря 2004 года.. Получено 24 октября 2014.
2. Марк Х. Winands, Jos W.H.M. Uiterwijk и Х. Яап ван ден Херик (2003). «PDS-PN: новый алгоритм поиска числа» (PDF). Конспект лекций по информатике.

дальнейшее чтение

А. Кишимото, M.H.M. Winands, M. Müller и J-T. Сайто (2012) Поиск в дереве игр с использованием чисел доказательства: первые двадцать лет, ICGA, 35 (3): 131–156, pdf