SSS*

SSS* to algorytm wyszukiwania , wprowadzony przez George'a Stockmana w 1979 r., który przeprowadza przeszukiwanie przestrzeni stanów przechodząc przez drzewo gry w sposób „najpierw najlepszy” , podobny do algorytmu wyszukiwania A* .

SSS* opiera się na koncepcji drzew rozwiązań. Nieformalnie drzewo rozwiązań można utworzyć z dowolnego dowolnego drzewa gry, zmniejszając liczbę gałęzi w każdym MAX do jednego. Takie drzewo reprezentuje kompletną strategię dla MAX, ponieważ określa dokładnie jedną akcję MAX na każdą możliwą sekwencję ruchów przeciwnika. Biorąc pod uwagę drzewo gry, SSS* przeszukuje przestrzeń drzew częściowych rozwiązań, stopniowo analizując coraz większe poddrzewa, ostatecznie tworząc pojedyncze drzewo rozwiązań z tym samym korzeniem i wartością Minimax, co oryginalne drzewo gry. SSS* nigdy nie bada węzła, który jest przycinany alfa-beta przycinałby i może przycinać niektóre gałęzie, których alfa-beta by nie przycinała. Stockman spekulował, że SSS* może być zatem lepszym algorytmem ogólnym niż alfa-beta. Jednak Igor Roizen i Judea Pearl wykazali, że oszczędności liczby pozycji ocenianych przez SSS* w stosunku do wersji alfa/beta są ograniczone i generalnie niewystarczające, aby zrekompensować wzrost innych zasobów (np. przechowywanie i sortowanie listy węzłów, które są konieczne ze względu na zasadę najlepszego pierwszego algorytmu). Jednak Aske Plaat, Jonathan Schaeffer , Wim Pijls i Arie de Bruin wykazali, że sekwencja wywołań alfa-beta w pustym oknie jest równoważna SSS* (tj. rozszerza te same węzły w tej samej kolejności), gdy alfa-beta jest używana z tablicą transpozycji tak jest we wszystkich programach do gry w szachy, warcaby itp. Teraz przechowywanie i sortowanie listy OPEN nie było już konieczne. Umożliwiło to wdrożenie (algorytmu równoważnego) SSS* w programach do gier o jakości turniejowej. Eksperymenty wykazały, że w praktyce rzeczywiście działał lepiej niż Alpha-Beta , ale nie pokonał NegaScout .

Przeformułowanie algorytmu „najlepszy jako pierwszy” jako sekwencji wywołań „najpierw w głąb” skłoniło do sformułowania klasy algorytmów alfa-beta z pustym oknem, z których MTD (f) jest najbardziej znanym przykładem.

Algorytm

Istnieje $($ priorytetowa OTWARTA, która przechowuje stany $lub$ węzły, gdzie notacja kropkowo służy węzły, ${\ Displaystyle \ epsilon}$ jest pierwiastkiem), ${\ Displaystyle s \ w \ {L, S \}}$ - stan węzła jot $\ displaystyle J}$ (L - węzeł jest aktywny, co oznacza, że ​​jeszcze nie został rozwiązany, a S - węzeł został rozwiązany), ${\ Displaystyle h \ in (- \ infty, \ infty)}$ - wartość rozwiązany węzeł. Elementy w kolejce OPEN są sortowane malejąco według $wartości$ . Jeśli więcej niż $jeden węzeł ma tę$ wartość , wybierany jest węzeł znajdujący się najbardziej na lewo w drzewie.

     OPEN := { (e, L, inf) }  while  true  wykonaj  // powtarzaj aż do zatrzymania wyskakuj element  p  = (  J  ,  s  ,  h  ) z początku kolejki OPEN  jeśli  J  =  e  i  s  =  S  to  ZATRZYMAJ algorytm i w rezultacie zwróć h, w  przeciwnym razie  zastosuj operator Gamma dla  p 

${\ Displaystyle \ Gamma}$ Operator dla jest zdefiniowany w następujący sposób: ${\ Displaystyle p = (J, s, h)}$

  
       jeśli  s  =  L  , to  jeśli  J  jest węzłem końcowym,  to  (1.) dodaj (  J  ,  S  , min(  h  , wartość (  J  ))) do OPEN  inaczej, jeśli  J  jest węzłem MIN  , to  (2.) dodaj (J. 1,  L  ,  h  ) do OPEN  w przeciwnym razie  (3.) dla  j  =1..liczba_dzieci(  J  ) dodaj (Jj,  L  ,  h  ) do OPEN  w przeciwnym razie 
      jeśli  J  jest węzłem MIN,  to  (4.) dodaj (parent(  J  ),  S  ,  h  ) do OPEN usuń z OPEN wszystkie stany, które są powiązane z dziećmi rodzica(J)  else if  is_last_child(  J  )  then  // jeśli J jest ostatnim dzieckiem rodzica (J) (5.) dodaj (rodzic (  J  ),  S  ,  h  ) do OPEN  else  (6.) dodaj (rodzic (  J  ). (  k  +1),  L  ,  h  ) do OPEN // dodaj stan powiązany z kolejnym dzieckiem rodzica (J) do OPEN 

Linki zewnętrzne

• Programowanie w szachach Wiki
• Witryna internetowa George'a Stockmana