Algorytm alfa-beta

Z Wikipedii

Algorytm alpha-beta

Algorytm Alfa-Beta jest algorytmem przeszukiwawczym, redukującym liczbę węzłów, które muszą być rozwiązywane w drzewa przeszukiwawczych przez algorytm Minimax. Jest to przeszukiwanie wykorzystywane w grach dwuosobowych, takich jak kółko i krzyżyk, szachy, Go. Warunkiem stopu jest znalezienie przynajmniej jednego rozwiązania poprawiającego ruch gorszy niż poprzedni. Nie przyniesie korzyści graczowi, który wykonałby taki ruch, dlatego też nie ma potrzeby przeszukiwać tej gałęzi drzewa dalej. Ta technika pozwala zaoszczędzić czas poszukiwania bez zmiany wyniku działania algorytmu.

[edytuj] Poprawiony minimax

Korzyść płynąca z algorytmu alfa-beta leży w fakcie, że niektóre gałęzie drzewa przeszukiwawczego 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 swój poprzednik 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 minimax. 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 ilość 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 minimax. Jeśli porządek wykonywania ruchów jest optymalny, czyli najlepsze ruchy są przeszukiwane jako pierwsze, ilość 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 czasie alfa-beta poddrzewa są tymczasowo zdominowane przez przewagę pierwszego gracza (kiedy ruch 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 zmieniać strony wiele razy w trakcie poszukiwań jeśli porządek ruchów jest niewłaściwy za każdym razem prowadząc do marnotrawstwa. Jako że ilość 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 ilość przeszukiwanych pozycji, ale sortowanie wszystkich pozycji na głębokości bliższej korzeniowi jest relatywnie tańsza z powodu ich małej ilości. W praktyce porządkowanie ruchów jest określane przez wyniki wcześniejszych mniejszych poszukiwań, takich jak iterative deepening.

Algorytm utrzymuje dwie wartości alfa i beta, które reprezentują minimalny wynik MAX gracza i maksymalny wynik gracza MIN. Początkowo alfa jest -nieskończonością a beta +nieskończonością. W miarę postępowania rekursji okno (alfa-beta) staje się mniejsze 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.

[edytuj] 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 przeszukiwawczego bazowanego na doświadczeniu. To jest znane jako aspiration search. W przypadku ekstremalnym przeszukiwanie jest wykonywane z alfa równym 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 nie udało się z powodu, że alfa była za duża/beta za mała. To da informację o tym, czy wartości okna mogą być użyteczne w poszukiwaniu rozwiązania na nowo.

[edytuj] Inne algorytmy

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

Od kiedy minimax i jego warianty dziedziczą z depth-first, strategia taka jak iterative deepening jest zazwyczaj używana w parze z alfa-beta 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ą 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.

[edytuj] 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ść heurystyczna 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 α≥β
                zwróć α
        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 α≥β
                zwróć β
        zwróć α

[edytuj] Zobacz też

Pruning
Metoda podziału i ograniczeń
Minimax
Optymalizacja kombinatoryczna
Negamax
Tabela transpozycji
MTD(f)

[edytuj] Przypisy

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

[edytuj] Linki zewnętrzne

Kategoria: Algorytmy

We provide Linux to the World

Algorytm alfa-beta

Z Wikipedii

Spis treści

[edytuj] Poprawiony minimax

[edytuj] Usprawnienia Heurystyczne

[edytuj] Inne algorytmy

[edytuj] Pseudokod

[edytuj] Zobacz też

[edytuj] Przypisy

[edytuj] Linki zewnętrzne

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach