Поиск по номеру подтверждения

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

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

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

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

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

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

Ссылки

^ Эллис, Л. Виктор. Поиск решений в играх и искусственном интеллекте. Кандидатская диссертация . Понсен и Лойен. ISBN 90-9007488-0 . Архивировано из оригинала 4 декабря 2004 г. Проверено 24 октября 2014 г. {{cite book}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
^ Марк Х. М. Винандс, Йос УХМ Уитервейк и Х. Яап ван ден Херик (2003). PDS-PN: новый алгоритм поиска числа подтверждений (PDF) . Конспекты лекций по информатике. {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

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

А. Кишимото, МХМ Винандс, М. Мюллер и Дж.Т. Сайто (2012) Поиск в дереве игр с использованием чисел доказательств: первые двадцать лет , ICGA, 35(3):131–156, pdf

[1] Эллис, Л. Виктор. Поиск решений в играх и искусственном интеллекте. Кандидатская диссертация . Понсен и Лойен. ISBN 90-9007488-0 . Архивировано из оригинала 4 декабря 2004 г. Проверено 24 октября 2014 г. {{cite book}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )

[NS-2] Марк Х. М. Винандс, Йос УХМ Уитервейк и Х. Яап ван ден Херик (2003). PDS-PN: новый алгоритм поиска числа подтверждений (PDF) . Конспекты лекций по информатике. {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[ 1 ]

[ 2 ]