SSS*

Z Wikipedii

SSS* jest zoptymalizowanym algorytmem do gier dwuosobowych (algorytmem typu min-max) autorstwa G. Stockmanna ([2]). Wg [1] jest algorytmem co najmniej tak dobrym jak algorytm alfa-beta, tzn. nigdy nie przegląda wierzchołka ominiętego przez α − β mogąc dodatkowo poczynić dalsze oszczędności.

Dana jest lista OPEN przechowująca stany (J,s,h), gdzie J - wierzchołek (używana jest notacja Deweya, ε oznacza korzeń), - stan rozwiązania dla J (S oznacza wierzchołek zamknięty (rozwiązany), a L otwarty (nierozwiązany)) oraz - wartość rozwiązania dla J. OPEN jest kolejką priorytetową, elementy ułożone są w kolejności malejącej wartości h. W przypadku wielu węzłów o tej samej mierze 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 Γ dla 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..ilość_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=ilość_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

[edytuj] 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 Γ, zawartość listy 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.

[edytuj] Literatura

• [1] J. Pearl: Heuristics. Intelligent search strategies for computer problem solving, Addison-Wesley, 1984
• [2] G. Stockmann: A minimax algorithm better than alpha-beta?, Artificial Intelligence 12(2), 1979, s. 179-196