SSS * - SSS* - Wikipedia

SSS * это алгоритм поиска, представленный Джорджем Стокманом в 1979 году, который проводит поиск в пространстве состояний пересекая игровое дерево в лучший первый мода похожа на Алгоритм поиска A *.

SSS * основан на понятии деревья решений. Неформально дерево решений может быть сформировано из любого произвольного игрового дерева путем сокращения количества ветвей на каждом МАКСИМУМ узел к одному. Такое дерево представляет собой полную стратегию для MAX, поскольку оно определяет ровно одно действие MAX для каждой возможной последовательности ходов, сделанных противником. Учитывая дерево игры, SSS * просматривает пространство частичных деревьев решений, постепенно анализируя все большие и большие поддеревья, в конечном итоге создавая одно дерево решений с тем же корнем и значением Minimax, что и исходное дерево игры. SSS * никогда не проверяет узел, который альфа-бета обрезка будет обрезать, и может обрезать некоторые ветви, которые не сделала бы альфа-бета. Стокман предположил, что поэтому SSS * может быть лучшим общим алгоритмом, чем альфа-бета. Тем не мение, Игорь Ройзен и Жемчужина Иудеи показали[1] что экономия в количестве позиций, которые SSS * оценивает относительно альфа / бета, ограничена и, как правило, недостаточна, чтобы компенсировать увеличение других ресурсов (например, хранение и сортировка списка узлов, необходимых для наилучшего первого характер алгоритма). Тем не мение, Aske Plaat, Джонатан Шеффер, Wim Pijls и Arie de Bruin показали, что последовательность вызовов альфа-бета нулевого окна эквивалентна SSS * (т. Е. Расширяет те же узлы в том же порядке), когда альфа-бета используется с таблица транспонирования, как и во всех игровых программах для шахмат, шашек и т. д. Теперь в хранении и сортировке ОТКРЫТОГО списка больше не было необходимости. Это позволило реализовать (алгоритм, эквивалентный) SSS * в игровых программах турнирного качества. Эксперименты показали, что он действительно работал лучше, чем Альфа-Бета на практике, но чтобы он не побил NegaScout.[2]

Переформулировка алгоритма лучшего первого как последовательности вызовов в глубину побудила сформулировать класс альфа-бета алгоритмов нулевого окна, из которых МПД-ф это самый известный пример.

Алгоритм

Существует приоритетная очередь ОТКРЫТЬ, в котором хранятся состояния или узлы, где - идентификатор узла (Обозначение Дьюи используется для идентификации узлов, является корнем), - состояние узла (L - узел активен, что означает, что он еще не решен и S - узел решен), - значение решаемого узла. Элементы в очереди OPEN сортируются по убыванию ценить. Если более одного узла имеют одинаковое значение , выбирается крайний левый узел в дереве.

ОТКРЫТЬ: = {(e, L, inf)}пока истинный делать   // повторяем, пока не остановимся, выталкиваем элемент п=(J, s, час) из головы ОТКРЫТОЙ очереди если J = е и s = S тогда        ОСТАНОВИТЬ алгоритм и в результате вернуть h еще        применить гамма-оператор для п

оператор для определяется следующим образом:

если s = L тогда    если J конечный узел тогда        (1.) добавить (J, S, мин (час, ценить(J))) открыть иначе если J является узлом MIN тогда        (2.) добавить (J.1, L, час) открыть еще        (3.) для j= 1..количество_детей (J) add (J.j, L, час) открытьеще    если J узел MIN тогда        (4.) добавить (родительский (J), S, час), чтобы ОТКРЫТЬ, удалите из ОТКРЫТО все состояния, связанные с дочерними элементами родительского элемента (J) иначе если is_last_child (J) тогда   // если J последний дочерний элемент parent (J) (5.) add (parent (J), S, час) открыть еще        (6.) добавить (родительский (J).(k+1), L, час) в OPEN // добавляем состояние, связанное со следующим дочерним элементом родительского (J), в OPEN

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

  1. ^ Ройзен, Игорь; Жемчужина Иудеи (март 1983 г.). «Минимаксный алгоритм лучше, чем альфа-бета ?: Да и Нет». Искусственный интеллект. 21 (1–2): 199–220. Дои:10.1016 / с0004-3702 (83) 80010-1.
  2. ^ Plaat, Aske; Джонатан Шеффер; Вим Пейлс; Арье де Брюэн (ноябрь 1996 г.). «Лучшие первые минимаксные алгоритмы фиксированной глубины». Искусственный интеллект. 87 (1–2): 255–293. Дои:10.1016/0004-3702(95)00126-3.

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