Tekst źródłowy strony SSS*

'''SSS*''' jest zoptymalizowanym algorytmem do gier dwuosobowych ([[algorytm min-max|algorytmem typu min-max]])
autorstwa G. Stockmanna<ref>J. Pearl: ''Heuristics. Intelligent search strategies for computer problem solving'', Addison-Wesley, 1984.</ref>. Algorytm ten jest co najmniej tak dobry jak [[algorytm alfa-beta]], tzn. nigdy nie przegląda wierzchołka ominiętego przez <math>\alpha-\beta</math> mogąc dodatkowo poczynić dalsze oszczędności<ref>G. Stockmann: ''A minimax algorithm better than alpha-beta?'', Artificial Intelligence 12(2), 1979, s. 179–196.</ref>.

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

[[Plik:SSS* example tree.svg|400px]]

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

[[Kategoria:Algorytmy wyszukiwania]]