SSS*

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 \alpha-\beta mogąc dodatkowo poczynić dalsze oszczędności[2].

Dana jest kolejka priorytetowa OPEN przechowująca stany (J, s, h), gdzie J – wierzchołek (używana jest notacja Deweya, \epsilon oznacza korzeń), s\in\{L,S\} – stan rozwiązania dla J (S oznacza wierzchołek zamknięty (rozwiązany), a L otwarty (nierozwiązany)) oraz h\in(-\infty, \infty) – wartość rozwiązania dla J. OPEN jest posortowana zgodnie z malejącą 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 \Gamma 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..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[edytuj | edytuj kod]

Dane jest drzewo gier:

SSS* example tree.svg

Poniższy wydruk przedstawia działanie algorytmu. Kolumny, w kolejności od lewej do prawej: numer iteracji, przypadek operatora \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

  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