ССС*

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

SSS* основан на понятии деревьев решений . Неформально дерево решений можно сформировать из любого произвольного игрового дерева, сократив количество ветвей в каждом узле MAX до одной. Такое дерево представляет собой полную стратегию MAX, поскольку оно определяет ровно одно MAX-действие для каждой возможной последовательности ходов, сделанных противником. Учитывая дерево игры, SSS* просматривает пространство частичных деревьев решений, постепенно анализируя все большие и большие поддеревья, в конечном итоге создавая единственное дерево решений с тем же корнем и минимаксным значением, что и исходное дерево игры. SSS* никогда не проверяет узел, который будет удален при альфа-бета-обрезке , и может обрезать некоторые ветви, которые не будут удалены при альфа-бета-обрезке. Стокман предположил, что SSS* может быть лучшим общим алгоритмом, чем альфа-бета. Однако Игорь Ройзен и Джудея Перл показали что экономия количества позиций, которые SSS* оценивает по сравнению с альфа/бета, ограничена и, как правило, недостаточна, чтобы компенсировать увеличение других ресурсов (например, хранение и сортировка списка узлов, необходимые в соответствии с принципом «лучший — первый») суть алгоритма). Однако Аске Плаат , Джонатан Шеффер , Вим Пейлс и Ари де Брюин показали, что последовательность альфа-бета-вызовов с нулевым окном эквивалентна SSS* (т. е. она расширяет одни и те же узлы в том же порядке), когда альфа-бета использовался с таблицей транспонирования , как и во всех игровых программах для шахмат, шашек и т.п. Теперь хранение и сортировка ОТКРЫТОГО списка отпала необходимость. Это позволило реализовать (алгоритм, эквивалентный) SSS* в игровых программах турнирного качества. Эксперименты показали, что на практике он действительно работал лучше, чем Alpha-Beta , но не превосходил NegaScout .

Переформулировка алгоритма «сначала лучшее» как последовательности вызовов «сначала в глубину» привела к формулировке класса альфа-бета-алгоритмов с нулевым окном, MTD(f) наиболее известным примером которых является .

Алгоритм

Существует очередь приоритетов OPEN, в которой хранятся состояния. $(J,s,h)$ или узлы, где $J$ - идентификатор узла ( десятичная запись , для идентификации узлов используется $\epsilon$ является корнем), $s\in \{L,S\}$ - состояние узла $J$ (L – узел активен, что означает, что он еще не решен и S – узел решен), $h\in (-\infty ,\infty )$ - значение решенного узла. Элементы в очереди OPEN сортируются по убыванию их $h$ ценить. Если более одного узла имеют одинаковое значение $h$, выбирается самый левый узел дерева.

OPEN := { (e, L, inf) }
while true do   // repeat until stopped
    pop an element p=(J, s, h) from the head of the OPEN queue
    if J = e and s = S then
        STOP the algorithm and return h as a result
    else
        apply Gamma operator for p

$\Gamma$ оператор для $p=(J,s,h)$ определяется следующим образом:

if s = L then
    if J is a terminal node then
        (1.) add (J, S, min(h, value(J))) to OPEN
    else if J is a MIN node then
        (2.) add (J.1, L, h) to OPEN
    else
        (3.) for j=1..number_of_children(J) add (J.j, L, h) to OPEN
else
    if J is a MIN node then
        (4.) add (parent(J), S, h) to OPEN
             remove from OPEN all the states that are associated with the children of parent(J)
    else if is_last_child(J) then   // if J is the last child of parent(J)
        (5.) add (parent(J), S, h) to OPEN
    else
        (6.) add (parent(J).(k+1), L, h) to OPEN   // add state associated with the next child of parent(J) to OPEN

Внешние ссылки

• Вики по шахматному программированию
• сайт Джорджа Стокмана