Algorytm alfa-beta

Algorytm Alfa-Beta – algorytm przeszukujący, redukujący liczbę węzłów, które muszą być rozwiązywane w drzewach przeszukujących przez algorytm min-max. Jest to przeszukiwanie wykorzystywane w grach dwuosobowych, takich jak kółko i krzyżyk, szachy, go. Warunkiem stopu jest znalezienie przynajmniej jednego rozwiązania czyniącego obecnie badaną opcję ruchu gorszą od poprzednio zbadanych opcji. Wybranie takiej opcji ruchu nie przyniosłoby korzyści graczowi ruszającemu się, dlatego też nie ma potrzeby przeszukiwać dalej gałęzi drzewa tej opcji. Ta technika pozwala zaoszczędzić czas poszukiwania bez zmiany wyniku działania algorytmu.

Poprawiony min-max

Korzyść płynąca z algorytmu alfa-beta leży w fakcie, że niektóre gałęzie drzewa przeszukiwania mogą zostać odcięte. Czas przeszukiwania ograniczony zostaje do przeszukania najbardziej obiecujących poddrzew, w związku z czym możemy zejść głębiej w tym samym czasie. Tak samo jak klasyczny min-max, algorytm należy do algorytmów wykorzystujących metody podziału i ograniczeń (branch and bound). Współczynnik rozgałęzienia jest dwukrotnie mniejszy niż w metodzie min-max. Algorytm staje się wydajniejszy, gdy węzły rozwiązywane są układane w porządku optymalnym lub jemu bliskim.

Ze średnim albo stałym współczynnikiem rozgałęzienia b i głębokością d maksymalna liczba rozwiązanych węzłów (kiedy porządkowanie ruchów jest przypadkiem pesymistycznym) wynosi O(b*b*...*b) = O(b^d) i jest taki sam jak w przypadku min-max. Jeśli porządek wykonywania ruchów jest optymalny, czyli najlepsze ruchy są przeszukiwane jako pierwsze, liczba przeszukiwanych pozycji wyniesie O(b*1*b*1*...*b) dla nieparzystej głębokości i odpowiednio O (b*1*b*1*...*1), gdy głębokość będzie parzysta lub $O(b^{d/2})=O({\sqrt {b^{d}}}).$ W późniejszych przypadkach efektywny współczynnik rozgałęzienia jest redukowany do pierwiastka lub przeszukiwanie może odbywać się dwukrotnie głębiej^[1]. b*1*b*1*... bierze się stąd, że wszystkie pierwsze ruchy gracza muszą zostać sprawdzone w celu znalezienia ruchu najlepszego, ale dla każdego kolejnego tylko najlepszy ruch gracza jest potrzebny, aby odrzucić wszystkie ruchy poza pierwszym, najlepszym ruchem – alfa-beta dba o to, że żaden inny ruch drugiego gracza nie musi być brany pod uwagę. Jeśli b=40 (szachy) i głębokość wynosi 12, współczynnik pomiędzy optymalnym i pesymistycznym przypadkiem współczynnika jest bliski 40⁶.

Normalnie w trakcie wykonywania algorytmu alfa-beta poddrzewa są tymczasowo zdominowane przez przewagę pierwszego gracza (kiedy ruchy gracza są dobre i w każdym wyszukiwaniu głębokość jest odpowiednia, ale każda odpowiedź drugiego gracza jest nastawiona na odparcie ataku) lub vice versa. Ta przewaga może się wiele razy powtórzyć w trakcie poszukiwań, jeśli porządek ruchów jest niewłaściwy – za każdym razem prowadząc do marnotrawstwa. Jako że liczba pozycji zmniejsza się wykładniczo dla każdego ruchu początkowego, warto zastanowić się nad sortowaniem pierwszych ruchów. Zastosowanie sortowania na każdej głębokości wykładniczo zredukuje liczbę przeszukiwanych pozycji, ale sortowanie wszystkich pozycji na głębokości bliższej korzeniowi jest relatywnie tańsze z powodu ich niewielkiej liczby. W praktyce porządkowanie ruchów jest określane przez wyniki wcześniejszych mniejszych poszukiwań, takich jak iteracyjne pogłębianie.

Algorytm utrzymuje dwie wartości alfa i beta, które reprezentują minimalny wynik gracza MAX i maksymalny wynik gracza MIN. Początkowo alfa jest -nieskończonością, a beta +nieskończonością. W miarę postępowania rekursji przedział (alfa; beta) staje się mniejszy i kiedy beta staje się mniejsze niż alfa, oznacza to, że obecna pozycja nie może być wynikiem najlepszej gry przez obu graczy i wskutek tego nie ma potrzeby przeszukiwania głębiej.

Usprawnienia heurystyczne

Dalsza poprawa może zostać osiągnięta bez utraty skuteczności poprzez użycie porządku heurystycznego do przeszukiwania drzew, które zostają odcięte wcześnie. Na przykład w szachach ruchy, które biją pionki, mogą być sprawdzone przed innymi albo ruchy punktowane wysoko w poprzednich analizach mogą być sprawdzane przed innymi. Inną często stosowaną i tanią metodą heurystyczną jest sprawdzenie na początku ruchów, które spowodowały beta-odcięcie na tej samej głębokości. Idea ta może zostać zgeneralizowana jako refutation tables.

Przeszukiwanie może stać się nawet szybsze poprzez rozważanie wąskiego okna przeszukiwania, bazowanego na doświadczeniu. Jest to znane jako aspiration search. W przypadku ekstremalnym przeszukiwanie jest wykonywane z alfa = beta techniką zwaną zero-window search, null-window search, lub scout search. Jest to użyteczne dla wygrywających/przegrywających przeszukiwań w pobliżu końca gry, gdzie najwęższe okno i proste rozwiązania przegrywające/wygrywające mogą prowadzić do zakończenia rozgrywki. Jeśli aspiration search się nie uda, powinno się wykryć, czy przyczyną była za duża alfa / za mała beta. Da to informację o tym, czy wartości okna mogą być użyteczne w poszukiwaniu rozwiązania na nowo.

Inne algorytmy

Bardziej zaawansowane algorytmy, nawet szybsze w obliczaniu dokładnej wartości min-max, są znane jako Negascout i MTD-f.

Ponieważ min-max i jego warianty są rozwinięciem przeszukiwania w głąb, zazwyczaj w parze z alfa-beta używa się iteracyjnego pogłębiania – po to, aby dobry ruch został zwrócony, nawet gdy algorytm został przerwany, zanim zakończył swoje działanie. Inną przewagą używania metod przeszukiwania iteracyjnego jest to, że na niskich głębokościach dają one wskazówki do porządkowania ruchów, które mogą być pomocne w odcinaniu gałęzi dla większych głębokości znacznie wcześniej, niż byłoby to możliwe w przypadku innych algorytmów.

Algorytmy takie jak SSS* z drugiej strony używają strategii best-first strategy.

Pseudokod

Pseudokod algorytmu alfa-beta:

funkcja minimax(węzeł, głębokość)
    zwróć alfabeta(węzeł, głębokość, -∞, +∞)

funkcja alfabeta(węzeł, głębokość, α, β)
    jeżeli węzeł jest końcowy lub głębokość = 0
        zwróć wartość heurystyczną węzła
    jeżeli przeciwnik ma zagrać w węźle
        dla każdego potomka węzła
            β := min(β, alfabeta(potomek, głębokość-1, α, β))
            jeżeli α≥β
                przerwij przeszukiwanie  {odcinamy gałąź Alfa}
        zwróć β
    w przeciwnym przypadku {my mamy zagrać w węźle}
        dla każdego potomka węzła
            α := max(α, alfabeta(potomek, głębokość-1, α, β))
            jeżeli α≥β
                przerwij przeszukiwanie  {odcinamy gałąź Beta}
        zwróć α

Przypisy

↑ S. J. Russell, P. Norvig (2003). Artificial Intelligence: A Modern Approach. Second Edition, Prentice Hall.

Linki zewnętrzne

Chess Tree Search. [dostęp 2017-07-13]. [zarchiwizowane z tego adresu (2008-07-05)]. (ang.).
Przykładowy program wykorzystujący ten algorytm. computerchess.us. [zarchiwizowane z tego adresu (2007-04-30)].
Beowulf Computer Chess Engine. [dostęp 2017-07-13]. (ang.).

[1] S. J. Russell, P. Norvig (2003). Artificial Intelligence: A Modern Approach. Second Edition, Prentice Hall.

[1]