Przycinanie alfa-beta - Alpha–beta pruning

Przycinanie alfa–beta

Klasa	Algorytm wyszukiwania
Wydajność w najgorszym przypadku	${\ Displaystyle O (b ^ {d})}$
Wydajność w najlepszym przypadku	${\ Displaystyle O \ lewo ({\ sqrt {b ^ {d}}} \ po prawej)}$

Przycinanie alfa-beta to algorytm wyszukiwania, którego celem jest zmniejszenie liczby węzłów ocenianych przez algorytm minimax w drzewie wyszukiwania . Jest to algorytm wyszukiwania kontradyktoryjności używany powszechnie do maszynowego grania w gry dwuosobowe ( Kółko i krzyżyk , Szachy , Go , itp.). Przestaje oceniać ruch, gdy zostanie znaleziona przynajmniej jedna możliwość, która dowodzi, że ruch jest gorszy niż ruch wcześniej zbadany. Takie ruchy nie muszą być dalej oceniane. Po zastosowaniu do standardowego drzewa minimax, zwraca ten sam ruch, co minimax, ale przycina gałęzie, które nie mogą mieć wpływu na ostateczną decyzję.

Historia

Allen Newell i Herbert A. Simon, którzy w 1958 r. użyli tego, co John McCarthy nazywa „przybliżeniem”, napisali, że alfa-beta „wydaje się być wielokrotnie odkrywana na nowo”. Arthur Samuel miał wczesną wersję symulacji warcabów. Richards, Timothy Hart, Michael Levin i/lub Daniel Edwards również niezależnie wynaleźli alfa-betę w Stanach Zjednoczonych . McCarthy zaproponował podobne pomysły podczas warsztatów w Dartmouth w 1956 i zasugerował je grupie swoich studentów, w tym Alanowi Kotokowi z MIT w 1961. Alexander Brudno niezależnie opracował algorytm alfa-beta, publikując swoje wyniki w 1963. Donald Knuth i Ronald W. Moore udoskonalił algorytm w 1975 roku. Judea Pearl w dwóch pracach dowiodła swojej optymalności pod względem oczekiwanego czasu pracy dla drzew o losowo przyporządkowanych wartościach liści. Optymalność randomizowanej wersji alfa-beta wykazali Michael Saks i Avi Wigderson w 1986 roku.

Podstawowy pomysł

Drzewo gra może reprezentować wiele dwóch graczy gry o sumie zerowej , takich jak szachy, warcaby i Reversi. Każdy węzeł w drzewie reprezentuje możliwą sytuację w grze. Każdemu węzłowi końcowemu (wynikowi) gałęzi przypisywany jest wynik liczbowy, który określa wartość wyniku dla gracza wykonującego następny ruch.

Algorytm utrzymuje dwie wartości, alfa i beta, które odpowiednio reprezentują minimalny wynik, który jest zapewniony graczowi maksymalizującemu i maksymalny wynik, który jest zapewniony graczowi minimalizującemu. Początkowo alfa jest nieskończonością ujemną, a beta jest nieskończonością dodatnią, co oznacza, że ​​obaj gracze zaczynają z najgorszym możliwym wynikiem. Ilekroć maksymalny wynik, co do którego zapewniony jest gracz minimalizujący (tj. gracz „beta”), jest niższy niż minimalny wynik, który jest zapewniony graczowi maksymalizującemu (tj. graczowi „alfa”) (tj. beta < alfa), maksymalizujący gracz nie musi brać pod uwagę dalszych potomków tego węzła, ponieważ nigdy nie zostaną one osiągnięte w rzeczywistej grze.

Aby zilustrować to przykładem z życia, załóżmy, że ktoś gra w szachy i nadeszła jego kolej. Ruch „A” poprawi pozycję gracza. Gracz nadal szuka ruchów, aby upewnić się, że nie został pominięty lepszy. Ruch „B” jest również dobrym posunięciem, ale gracz zdaje sobie wtedy sprawę, że pozwoli przeciwnikowi wymusić mata w dwóch ruchach. Tak więc inne wyniki zagrania ruchu B nie muszą już być brane pod uwagę, ponieważ przeciwnik może wymusić wygraną. Maksymalny wynik, jaki przeciwnik może wymusić po ruchu „B”, to ujemna nieskończoność: strata dla gracza. Jest to mniej niż minimalna pozycja, która została wcześniej znaleziona; ruch „A” nie skutkuje wymuszoną stratą w dwóch ruchach.

Ulepszenia nad naiwnym minimax

Ilustracja przycinania alfa-beta. Wyszarzone poddrzewa nie muszą być eksplorowane (gdy ruchy są oceniane od lewej do prawej), ponieważ wiadomo, że grupa poddrzew jako całość daje wartość równoważnego poddrzewa lub gorzej i jako taka nie może wpływać Wynik końcowy. Poziomy maksymalny i minimalny reprezentują odpowiednio kolej gracza i przeciwnika.

Zaleta przycinania alfa-beta polega na tym, że można wyeliminować gałęzie drzewa wyszukiwania. W ten sposób czas wyszukiwania można ograniczyć do „bardziej obiecującego” poddrzewa, a jednocześnie można przeprowadzić głębsze wyszukiwanie. Podobnie jak jego poprzednik należy do gałęzi i powiązanej klasy algorytmów. Optymalizacja zmniejsza efektywną głębokość do nieco więcej niż połowy prostego minimaksu, jeśli węzły są oceniane w optymalnej lub bliskiej optymalnej kolejności (najlepszy wybór dla strony na ruch uporządkowany jako pierwszy w każdym węźle).

Z (średnia lub stałych) rozgałęzień czynnika z B i głębokości wyszukiwania z d warstw liczba maksymalna pozycji węzłów liściowych oceniano (gdy ruch jest zamawianie pessimal ) to O ( b x b x ... x b ) = O ( b ^d ) – to samo, co proste wyszukiwanie minimaksowe. Jeśli kolejność ruchów dla wyszukiwania jest optymalna (co oznacza, że ​​najlepsze ruchy są zawsze wyszukiwane jako pierwsze), liczba ocenianych pozycji węzłów liścia wynosi około O ( b ×1× b ×1×...× b ) dla nieparzystej głębokości i O ( b ×1× b ×1×...×1) dla równej głębokości, lub . W tym drugim przypadku, gdy warstwa wyszukiwania jest parzysta, efektywny współczynnik rozgałęzienia jest redukowany do pierwiastka kwadratowego lub, równoważnie, wyszukiwanie może zajść dwukrotnie głębiej przy tej samej ilości obliczeń. Wyjaśnienie b ×1× b ×1×... jest takie, że wszystkie ruchy pierwszego gracza muszą zostać przestudiowane, aby znaleźć najlepszy, ale dla każdego z nich potrzebny jest tylko najlepszy ruch drugiego gracza, aby obalić wszystkie oprócz pierwszego (i najlepszy) ruch pierwszego gracza — alfa-beta zapewnia, że ​​żadne inne ruchy drugiego gracza nie muszą być brane pod uwagę. Gdy węzły są rozpatrywane w kolejności losowej (tj. algorytm randomizuje), asymptotycznie, oczekiwana liczba węzłów ocenianych w jednolitych drzewach z binarnymi wartościami liści wynosi . Dla tych samych drzew, gdy wartości są przypisane do wartości liści niezależnie od siebie i powiedzmy zero i jeden są jednakowo prawdopodobne, oczekiwana liczba ocenianych węzłów wynosi , co jest znacznie mniejsze niż praca wykonana przez algorytm randomizowany, wspomniany powyżej i ponownie jest optymalny dla takich przypadkowych drzew. Gdy wartości liści są wybrane niezależnie od siebie, a z przedziału równomiernie w sposób losowy, oczekiwana liczba węzłów oceniano wzrasta do w granicach, które znów jest optymalne dla tego rodzaju losowych drzew. Zauważ, że rzeczywista praca dla "małych" wartości jest lepiej przybliżona za pomocą . ${\ Displaystyle O (b ^ {d/2}) = O ({\ sqrt {b ^ {d}}})}$${\ Displaystyle \ Theta (((b-1 + {\ sqrt {b ^ {2} + 14b + 1}}) / 4) ^ {d})}$${\ Displaystyle \ Theta ((b/2) ^ {d})}$${\displaystyle [0,1]}$${\ Displaystyle \ Theta (b ^ {d / log (d)})}$${\displaystyle d\do \infty}$${\displaystyle d}$${\ Displaystyle 0,925 d ^ {0,747}}$

Program szachowy, który przeszukuje cztery warstwy ze średnią 36 gałęzi na węzeł, ocenia ponad milion węzłów końcowych. Optymalna śliwka alfa-beta wyeliminowałaby prawie 2000 węzłów końcowych, co oznacza redukcję o 99,8%.

Animowany przykład pedagogiczny, który stara się być przyjazny człowiekowi, zastępując pustkę początkowymi nieskończonymi (lub arbitralnie dużymi) wartościami i unikając stosowania uproszczeń kodowania negamax .

Zwykle podczas fazy alfa-beta poddrzewami tymczasowo dominuje albo przewaga pierwszego gracza (kiedy wiele ruchów pierwszego gracza jest dobrych, a na każdej głębokości wyszukiwania pierwszy ruch sprawdzany przez pierwszego gracza jest wystarczający, ale wszystkie odpowiedzi drugiego gracza są wymagane, aby spróbuj znaleźć obalenie) lub odwrotnie. Ta zaleta może wielokrotnie zmieniać strony podczas wyszukiwania, jeśli kolejność ruchu jest nieprawidłowa, za każdym razem prowadząc do nieefektywności. Ponieważ liczba przeszukiwanych pozycji zmniejsza się wykładniczo z każdym ruchem bliżej aktualnej pozycji, warto poświęcić sporo wysiłku na sortowanie wczesnych ruchów. Ulepszone sortowanie na dowolnej głębokości wykładniczo zmniejszy całkowitą liczbę przeszukiwanych pozycji, ale sortowanie wszystkich pozycji na głębokościach w pobliżu węzła głównego jest stosunkowo tanie, ponieważ jest ich tak mało. W praktyce o kolejności przeprowadzek często decydują wyniki wcześniejszych, mniejszych wyszukiwań, np. poprzez iteracyjne pogłębianie .

Dodatkowo, algorytm ten można w prosty sposób zmodyfikować tak, aby oprócz wyniku zwracał całą główną odmianę . Niektóre bardziej agresywne algorytmy, takie jak MTD(f) , nie pozwalają łatwo na taką modyfikację.

Pseudo kod

Pseudokod dla minimaksu o ograniczonej głębokości z przycinaniem alfa-beta wygląda następująco:

Wdrożenia przycinania alfa-beta często można określić na podstawie tego, czy są one „miękkie” lub „trudne w przypadku niepowodzenia”. W przypadku alfa-beta soft-fail, funkcja alfabetu może zwracać wartości (v), które przekraczają (v < α lub v > β) granice α i β ustawione przez argumenty wywołania funkcji. Dla porównania, alfa-beta typu fail-hard ogranicza wartość zwracaną przez funkcję do zakresu α i β włącznie. Główna różnica między implementacjami typu fail-soft i fail-hard polega na tym, czy α i β są aktualizowane przed czy po sprawdzeniu odcięcia. Jeśli zostaną zaktualizowane przed sprawdzeniem, mogą przekroczyć początkowe granice, a algorytm jest odporny na błędy.

Poniższy pseudokod ilustruje odmianę hard-fail-hard.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then
                break (* α cutoff *)
            β := min(β, value)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Poniższy pseudokod ilustruje alfa-beta oprogramowania fail-soft.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if value ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if value ≤ α then
                break (* α cutoff *)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Ulepszenia heurystyczne

Dalszą poprawę można osiągnąć bez poświęcania dokładności, stosując heurystykę porządkowania do przeszukiwania wcześniejszych części drzewa, które prawdopodobnie wymuszą odcięcia alfa-beta. Na przykład w szachach ruchy, które zbijają bierki, mogą być badane przed ruchami, które tego nie robią, a ruchy, które uzyskały wysokie punkty we wcześniejszych przejściach przez analizę drzewa gry, mogą być oceniane przed innymi. Inną powszechną i bardzo tanią heurystyką jest heurystyka zabójcy , w której ostatni ruch, który spowodował odcięcie beta na tym samym poziomie drzewa w wyszukiwaniu drzewa, jest zawsze sprawdzany jako pierwszy. Pomysł ten można również uogólnić na zestaw tabel refutacji .

Wyszukiwanie alfa-beta można przeprowadzić jeszcze szybciej, biorąc pod uwagę tylko wąskie okno wyszukiwania (zwykle określane na podstawie zgadywania opartego na doświadczeniu). Nazywa się to wyszukiwaniem aspiracji . W skrajnym przypadku wyszukiwanie odbywa się z równymi alfa i beta; technika znana jako zero-window search , null-window search lub scout search . Jest to szczególnie przydatne w przypadku wyszukiwania wygranych/przegranych pod koniec gry, gdzie dodatkowa głębia uzyskana z wąskiego okna i prosta funkcja oceny wygranych/przegranych mogą prowadzić do rozstrzygającego wyniku. Jeśli wyszukiwanie aspiracji nie powiedzie się, łatwo jest wykryć, czy nie powiodło się wysoko (górna krawędź okna była za niska) czy niska (dolna krawędź okna była za wysoka). Daje to informacje o tym, jakie wartości okien mogą być przydatne w ponownym przeszukaniu pozycji.

Z biegiem czasu zasugerowano inne ulepszenia i rzeczywiście idea Falphabeta (fail-soft alfa-beta) Johna Fishburna jest niemal uniwersalna i została już włączona powyżej w nieco zmodyfikowanej formie. Fishburn zasugerował również połączenie zabójczej heurystyki i wyszukiwania z zerowym oknem pod nazwą Lalphabeta („ostatni ruch z minimalnym wyszukiwaniem w oknie alfa-beta”).

Inne algorytmy

Ponieważ algorytm minimax i jego warianty są z natury ukierunkowane na głębokość , strategia taka jak pogłębianie iteracyjne jest zwykle używana w połączeniu z alfa-beta, dzięki czemu można zwrócić dość dobry ruch, nawet jeśli algorytm zostanie przerwany przed zakończeniem wykonywania. Kolejną zaletą korzystania z iteracyjnego pogłębiania jest to, że wyszukiwania na płytszych głębokościach dają wskazówki dotyczące kolejności ruchów, a także płytkie oszacowania alfa i beta, które mogą pomóc w tworzeniu odcięcia dla wyszukiwania na większej głębokości znacznie wcześniej, niż byłoby to możliwe w innym przypadku.

Z drugiej strony algorytmy takie jak SSS* wykorzystują strategię „ najlepszy-pierwszy” . Może to potencjalnie sprawić, że będą one bardziej efektywne czasowo, ale zwykle przy dużych kosztach w zakresie wydajności kosmicznej.

Zobacz też

Bibliografia

Bibliografia

• George T. Heineman; Gary Pollice; Stanleya Selkowa (2008). „Rozdział 7: Znajdowanie ścieżki w AI”. Algorytmy w pigułce . Oreilly Media . s. 217-223. Numer ISBN 978-0-596-51624-6.
• Judea Pearl , Heurystyka , Addison-Wesley, 1984
• John P. Fishburn (1984). „Dodatek A: Niektóre optymalizacje wyszukiwania α-β”. Analiza przyspieszenia w algorytmach rozproszonych (rewizja pracy doktorskiej z 1981 r . ) . Prasa naukowa UMI. s. 107-111. Numer ISBN 0-8357-1527-2.