Algorytm alpha-beta

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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, kółko i krzyżyk, szachy, Go. Warunkiem stopu jest znalezienie przynajmniej jednego rozwiązania poprawiajacego 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 wpływania na wynik końcowy.

[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 przeszukiwanie 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 "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 maxymalna 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 ruch początkowego, warto zastanowić się nad sortowaniem pierwszych ruchów. Zastsowanie sortowania na każdej głębokości wykładniczo zredukuje ilość przeszukiwanych pozycji, ale sortowanie wszystkich pozycji na głębokości bliższej korzeniwi jest relatywnie tańsza z powodu ich małej ilości. W praktyce porządkwanie 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. Pczątkowo alfa jest -nieskończonością a beta +nieskończonścią. W miarę postępowania rekursji okno(alfa-beta) staje się mniejsze i kiedy beta staje się miejsze niż alfa ozbacza to, że obecna pozycja nie może być wynikiem najlepszej gry przez obu graczy i w skutek tego nie ma potrzeby przeszukiwania głębiej.

[edytuj] Usprawnienia Heurystyczne

Dalsza pprawa może zostać osiągnięta bez utraty skuteczności poprzez użycie porządku herystyki 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 punkktowane wysoko w poprzednich analizach mogą być sprawdzane przed innymi. Inną, częstą, tanią metodą jest heurystyką jest sprawdzenie na początku ruchów, które spowodowały beta-odccięcie na tej samej głębokości. Ida 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 and 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 jak algorym zstał 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ło by to możliwe w innym przypadku.

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

Algorithms like , on the other hand, use the best-first strategy. This can potentially make them more time-efficient, but typically at a heavy cost in space-efficiency.

[edytuj] Pseudocode

Pseudocode metoda alfa-beta

function minimax(node, depth)
    return alphabeta(node, depth, -∞, +∞)

function alphabeta(node, depth, α, β)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    if the adversary is to play at node
        foreach child of node
            β := min(β, alphabeta(child, depth-1, α, β))
            if α≥β
                return α
        return β
    else {we are to play at node}
        foreach child of node
            α := max(α, alphabeta(child, depth-1, α, β))
            if α≥β
                return β
        return α

[edytuj] Zobacz też

Pruning (Algorithm)
Branch and bound
Minimax
Combinatorial optimization
Negamax
Transposition table
MTD(f)
Killer heuristic

[edytuj] Przypisy

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

[edytuj] Linki zewnętrzne

Źródło: "http://pl.wikipedia.org../../../a/l/g/Algorytm_alpha-beta.html"

Kategoria: Algorytmy

We provide Linux to the World

Algorytm alpha-beta

Z Wikipedii

Spis treści

[edytuj] Poprawiony minimax

[edytuj] Usprawnienia Heurystyczne

[edytuj] Inne algorytmy

[edytuj] Pseudocode

[edytuj] Zobacz też

[edytuj] Przypisy

[edytuj] Linki zewnętrzne

Views

nawigacja

techniczne

zmiany

Szukaj

W innych językach