ССС*

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$, выбирается самый левый узел дерева.

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

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

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

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

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