ССС* Алгоритам

SSS* је алгоритам претраге који је изумео Џорџ Стокман 1979. Овај алгоритам проналази стабло игре претрагом по најбољим особинама слично А* алгоритму.

SSS* се заснива на идеји решавања стабала. Информативно, решено стабло може бити формирано од било које произвољне игре стабала одрезивањем грана сваком МАX ћвору до последњег. Такво дрво репрезентује комплетну стратегију за МАX, пошто спецификује тачно једну МАX акцију за сваку могућу секвенцу потеза направљену од стране противника. За дато дрво игре, ССС* претражује кроз простор парцијалних решења стабала, постепено анализирајући све већа и већа постабла, и на крају евентуално ствара јединствено решење стабла са истим кореном и Минимаx вредношносћу оригиналног стабла игре. ССС* никада не испитује чвор који би Алфа-бета претрага откресала, и може откресати неке гране које алфа-бета не би. Стоцкман је спекулисао да је ССС* због тога бољи алгоритам од алфа-бета алгоритма. Ипак, Игор Роизен и Јудеа Пеарл су показали да уштеда у броју позиција које ССС* процењује у односу на афла-бета је ограничена и генерално недовољна да компензује потребу за повећањем других ресурса (складиштење и сортирање листе чворова је неопходно у алгоритму). Ипак, Аске Плаат, Јонатхан Сцхаеффер, Wим Пијлс и Арие де Бруин су показали да је секвенца нулл-wиндоw алфа-бета позива еквивалентна ССС*-у (то проширује исте чворове у истом редоследу) када је алфа-бета искоришцен у транспоситион табле, као што је случај у свим компјутерским играма за шах. Сада складиштење и сортирање отворене листе није више неопходно. Ово је дозволило имплементацију ССС* алгоритма у турнирима програма за игрице. Експеримент је показао да се он уистину има боље перформансе од алфа-бета алгоритма у пракси, али није бољи од НегаСцоут алгоритма.

Алгоритам

Овде имамо ред са приоритетом OPEN који складишти $(J,s,h)$ или чворове, где је$J$ -ћвор идентификатор (Девејева нотација је коришћена за идентификацију чворова, $\epsilon$је корен), $s\in \{L,S\}$ - стање чвора $J$ (L - чвор је 'жив', што значи да није још искоришћен и С - чвор је искоришћен), $h\in (-\infty ,\infty )$ - вредност искоришћеног чвора. Подаци у реду су сортирани опадајуће по њиховој $h$ вредности. Ако више од једног чвора има исту вредност $h$, биће изабран онај чвор који је највише улево.

   OPEN := { (e,L,inf) }
   while (true)   // beskonačna petlja koja se prekida ulaskom u if
       pop an element p=(J,s,h) 
       if J == e and s == S
           return h//Zaustavi algoritam i vrati h kao rezultat
       else
           primeni gama operator za p

$\Gamma$ оператор за $p=(J,s,h)$ је дефинисан на следећи начин:

   if s == L
       if J je terminalni čvor
           (1.) dodaj (J,S,min(h,value(J))) u OPEN
       else if J je MIN cvor
           (2.) dodaj (J.1,L,h) u OPEN
       else
           (3.) for j=1..broj_sinova(J) dodaj (J.j,L,h) u OPEN
   else
       if J je MIN čvor
           (4.) dodaj (otac(J),S,h) u OPEN
                izbriši iz reda  OPEN sve povezane sa decom od otac(J)
       else if poslednji_sin(J)   // ako je J poslednji sin od otac(J)
           (5.) dodaj (otac(J),S,h) u OPEN
       else
           (6.) dodaj(otac(J).(k+1),L,h) u OPEN   //dodaj čvor povezan sa sledećim detetom  otac(J) u OPEN

Спољашње везе

• Цхесс Программинг Wики Архивирано на сајту Wayback Machine (28. септембар 2008)
• Георге Стоцкман'с wебсите