SSS*

SSS* jest zoptymalizowanym algorytmem do gier dwuosobowych (algorytmem typu min-max) autorstwa G. Stockmanna^[1]. Algorytm ten jest co najmniej tak dobry jak algorytm alfa-beta, tzn. nigdy nie przegląda wierzchołka ominiętego przez ${\displaystyle \alpha -\beta }$ mogąc dodatkowo poczynić dalsze oszczędności^[2].

Dana jest kolejka priorytetowa OPEN przechowująca stany ${\displaystyle (J,s,h),}$ gdzie ${\displaystyle J}$ – wierzchołek (używana jest notacja Deweya, ${\displaystyle \epsilon }$ oznacza korzeń), ${\displaystyle s\in \{L,S\}}$ – stan rozwiązania dla ${\displaystyle J}$ (${\displaystyle S}$ oznacza wierzchołek zamknięty (rozwiązany), a ${\displaystyle L}$ otwarty (nierozwiązany)) oraz ${\displaystyle h\in (-\infty ,\infty )}$ – wartość rozwiązania dla ${\displaystyle J.}$ OPEN jest posortowana zgodnie z malejącą wartością ${\displaystyle h.}$ W przypadku wielu węzłów o tej samej mierze ${\displaystyle h,}$ preferowane są wierzchołki położone po lewej stronie drzewa.

   OPEN := { (e,L,inf) }
   powtarzaj
       zdejmij element p=(J,s,h) z wierzchołka OPEN
       jeśli J=e i s=S, zakończ działanie algorytmu, zwracając h
       w przeciwnym przypadku
           zastosuj operator Gamma dla p

Operator ${\displaystyle \Gamma }$ dla ${\displaystyle p=(J,s,h)}$ zdefiniowany jest następująco:

   jeżeli s=L
       jeżeli J jest wierzchołkiem terminalnym
           (1.) dodaj (J,S,min(h,wartość(J))) do OPEN
       w p.p. jeżeli J jest wierzchołkiem typu MIN
           (2.) dodaj (J.1,L,h) do OPEN
       w p.p.
           (3.) dla j=1..liczba_potomków(J) dodaj (J.j,L,h) do OPEN
   w p.p.
       jeżeli J jest wierzchołkiem typu MIN
           (4.) dodaj (rodzic(J),S,h) do OPEN
                usuń z OPEN wszystkie stany zawierające następników
                    wierzchołka rodzic(J)
       w p.p. jeżeli J=rodzic(J).k i k=liczba_potomków(rodzic(J))
           (5.) dodaj (rodzic(J),S,h) do OPEN
       w p.p.
           (6.) dodaj (rodzic(J).(k+1),L,h) do OPEN

Przykład

Dane jest drzewo gier:

Poniższy wydruk przedstawia działanie algorytmu. Kolumny, w kolejności od lewej do prawej: numer iteracji, przypadek operatora ${\displaystyle \Gamma ,}$ zawartość kolejki OPEN.

   1: –  e,L,inf
   2: 2  1,L,inf       2,L,inf       3,L,inf       4,L,inf
   3: 3  1.1,L,inf     2,L,inf       3,L,inf       4,L,inf
   4: 2  1.1.1,L,inf   1.1.2,L,inf   2,L,inf       3,L,inf       4,L,inf
   5: 1  1.1.2,L,inf   2,L,inf       3,L,inf       4,L,inf       1.1.1,S,2
   6: 1  2,L,inf       3,L,inf       4,L,inf       1.1.1,S,2     1.1.2,S,2
   7: 3  2.1,L,inf     3,L,inf       4,L,inf       1.1.1,S,2     1.1.2,S,2
   8: 2  2.1.1,L,inf   3,L,inf       4,L,inf       1.1.1,S,2     1.1.2,S,2
   9: 1  3,L,inf       4,L,inf       2.1.1,S,7     1.1.1,S,2     1.1.2,S,2
  10: 3  3.1,L,inf     4,L,inf       2.1.1,S,7     1.1.1,S,2     1.1.2,S,2
  11: 2  3.1.1,L,inf   4,L,inf       2.1.1,S,7     1.1.1,S,2     1.1.2,S,2
  12: 1  4,L,inf       2.1.1,S,7     1.1.1,S,2     1.1.2,S,2     3.1.1,S,1
  13: 3  4.1,L,inf     2.1.1,S,7     1.1.1,S,2     1.1.2,S,2     3.1.1,S,1
  14: 2  4.1.1,L,inf   2.1.1,S,7     1.1.1,S,2     1.1.2,S,2     3.1.1,S,1
  15: 1  2.1.1,S,7     1.1.1,S,2     1.1.2,S,2     4.1.1,S,2     3.1.1,S,1
  16: 4  2.1,S,7       1.1.1,S,2     1.1.2,S,2     4.1.1,S,2     3.1.1,S,1
  17: 6  2.2,L,7       1.1.1,S,2     1.1.2,S,2     4.1.1,S,2     3.1.1,S,1
  18: 2  2.2.1,L,7     2.2.2,L,7     1.1.1,S,2     1.1.2,S,2     4.1.1,S,2     3.1.1,S,1
  19: 1  2.2.2,L,7     2.2.1,S,6     1.1.1,S,2     1.1.2,S,2     4.1.1,S,2     3.1.1,S,1
  20: 1  2.2.1,S,6     1.1.1,S,2     1.1.2,S,2     4.1.1,S,2     3.1.1,S,1     2.2.2,S,0
  21: 4  2.2,S,6       1.1.1,S,2     1.1.2,S,2     4.1.1,S,2     3.1.1,S,1
  22: 5  2,S,6         1.1.1,S,2     1.1.2,S,2     4.1.1,S,2     3.1.1,S,1
  23: 4  e,S,6

Algorytm zakończył działanie po 23 krokach. Nie zostały odwiedzone dwa wierzchołki --- 4.2 i 4.2.1, które to zostały oznaczone kolorem białym na powyższej rycinie.

Przypisy