SSS* Algoritam

SSS* je algoritam pretrage koji je izumeo Džordž Stokman 1979. Ovaj algoritam pronalazi stablo igre pretragom po najboljim osobinama slično A* algoritmu.

SSS* se zasniva na ideji rešavanja stabala. Informativno, rešeno stablo može biti formirano od bilo koje proizvoljne igre stabala odrezivanjem grana svakom MAX ćvoru do poslednjeg. Takvo drvo reprezentuje kompletnu strategiju za MAX, pošto specifikuje tačno jednu MAX akciju za svaku moguću sekvencu poteza napravljenu od strane protivnika. Za dato drvo igre, SSS* pretražuje kroz prostor parcijalnih rešenja stabala, postepeno analizirajući sve veća i veća postabla, i na kraju eventualno stvara jedinstveno rešenje stabla sa istim korenom i Minimax vrednošnosću originalnog stabla igre. SSS* nikada ne ispituje čvor koji bi Alfa-beta pretraga otkresala, i može otkresati neke grane koje alfa-beta ne bi. Stockman je spekulisao da je SSS* zbog toga bolji algoritam od alfa-beta algoritma. Ipak, Igor Roizen i Judea Pearl su pokazali da ušteda u broju pozicija koje SSS* procenjuje u odnosu na afla-beta je ograničena i generalno nedovoljna da kompenzuje potrebu za povećanjem drugih resursa (skladištenje i sortiranje liste čvorova je neophodno u algoritmu). Ipak, Aske Plaat, Jonathan Schaeffer, Wim Pijls i Arie de Bruin su pokazali da je sekvenca null-window alfa-beta poziva ekvivalentna SSS*-u (to proširuje iste čvorove u istom redosledu) kada je alfa-beta iskorišcen u transposition table, kao što je slučaj u svim kompjuterskim igrama za šah. Sada skladištenje i sortiranje otvorene liste nije više neophodno. Ovo je dozvolilo implementaciju SSS* algoritma u turnirima programa za igrice. Eksperiment je pokazao da se on uistinu ima bolje performanse od alfa-beta algoritma u praksi, ali nije bolji od NegaScout algoritma.

Algoritam

Ovde imamo red sa prioritetom OPEN koji skladišti $(J,s,h)$ ili čvorove, gde je$J$ -ćvor identifikator (Devejeva notacija je korišćena za identifikaciju čvorova, $\epsilon$je koren), $s\in \{L,S\}$ - stanje čvora $J$ (L - čvor je 'živ', što znači da nije još iskorišćen i S - čvor je iskorišćen), $h\in (-\infty ,\infty )$ - vrednost iskorišćenog čvora. Podaci u redu su sortirani opadajuće po njihovoj $h$ vrednosti. Ako više od jednog čvora ima istu vrednost $h$, biće izabran onaj čvor koji je najviše ulevo.

   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$ operator za $p=(J,s,h)$ je definisan na sledeći način:

   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

Spoljašnje veze

• Chess Programming Wiki Архивирано на сајту Wayback Machine (28. септембар 2008)
• George Stockman's website