Algorytm Alfa-Beta
Algorytm Alfa-Beta to technika przeszukiwania, która zmniejsza liczbę węzłów, które muszą być analizowane w drzewach przeszukiwania przez algorytm min-max. Używa się go w grach dwuosobowych, takich jak kółko-krzyżyk, szachy czy go. Warunkiem zakończenia przeszukiwania jest znalezienie co najmniej jednego rozwiązania, które sprawia, że obecnie analizowana opcja ruchu jest gorsza od wcześniej zbadanych. Wybór takiego ruchu nie przynosiłby korzyści graczowi, co oznacza, że dalsze przeszukiwanie tej gałęzi drzewa nie jest konieczne. Ta strategia pozwala zaoszczędzić czas na poszukiwania, nie wpływając na wynik działania algorytmu.
Poprawiony min-max
Zaletą algorytmu Alfa-Beta jest to, że niektóre gałęzie drzewa przeszukiwania mogą zostać odcięte. Czas przeszukiwania ogranicza się do najbardziej obiecujących poddrzew, co pozwala na głębsze badanie w tym samym czasie. Podobnie jak klasyczny min-max, algorytm ten należy do grupy metod podziału i ograniczeń (branch and bound). Współczynnik rozgałęzienia jest o połowę mniejszy w porównaniu do metody min-max. Algorytm staje się bardziej efektywny, gdy węzły są rozwiązywane w optymalnym lub bliskim porządku.
Przy średnim lub stałym współczynniku rozgałęzienia b oraz głębokości d, maksymalna liczba rozwiązanych węzłów (w przypadku pesymistycznego porządku ruchów) wynosi O(b*b*…*b) = O(bd) i jest równa tej samej wartości, co w przypadku min-max. Gdy porządek ruchów jest optymalny, liczba przeszukiwanych pozycji wynosi O(b*1*b*1*…*b) dla nieparzystej głębokości, a O(b*1*b*1*…*1) dla parzystej głębokości, co można zapisać jako O(bd/2) = O(√(bd)).
W późniejszych przypadkach efektywny współczynnik rozgałęzienia może być zmniejszony do pierwiastka, co pozwala na przeszukiwanie dwukrotnie głębiej. Otrzymany wzór b*1*b*1*… wynika z faktu, że wszystkie pierwsze ruchy gracza muszą być sprawdzone w celu znalezienia najlepszego ruchu. Dla każdego kolejnego ruchu konieczne jest tylko ustalenie najlepszego ruchu, co sprawia, że alfa-beta eliminuje potrzebę rozważania innych ruchów drugiego gracza. Dla b=40 (szachy) i głębokości 12, stosunek pomiędzy przypadkiem optymalnym a pesymistycznym wynosi blisko 406.
Podczas działania algorytmu Alfa-Beta poddrzewa są czasowo zdominowane przez przewagę pierwszego gracza (gdy ruchy gracza są dobre i głębokość przeszukiwania jest odpowiednia, ale odpowiedzi drugiego gracza mają na celu obronę) lub odwrotnie. Taka przewaga może wielokrotnie występować w trakcie poszukiwań, jeśli porządek ruchów jest błędny, co prowadzi do niepotrzebnego marnotrawstwa. Ponieważ liczba pozycji zmniejsza się wykładniczo dla każdego początkowego ruchu, warto rozważyć sortowanie tych ruchów. Zastosowanie sortowania na każdej głębokości może wykładniczo zredukować liczbę przeszukiwanych pozycji, ale sortowanie wszystkich pozycji na głębokości bliższej korzeniowi jest relatywnie tańsze ze względu na ich niewielką liczbę. W praktyce porządkowanie ruchów ustala się na podstawie wyników wcześniejszych mniejszych poszukiwań, takich jak iteracyjne pogłębianie.
Algorytm przechowuje dwie wartości: alfa i beta, które reprezentują minimalny wynik gracza MAX i maksymalny wynik gracza MIN. Na początku alfa przyjmuje wartość -nieskończoność, a beta +nieskończoność. W miarę postępu rekursji przedział (alfa; beta) staje się coraz węższy. Kiedy beta staje się mniejsza niż alfa, oznacza to, że obecna pozycja nie może prowadzić do najlepszego wyniku dla obu graczy, co eliminuje potrzebę dalszego przeszukiwania.
Usprawnienia heurystyczne
Można osiągnąć dalsze ulepszenia bez utraty efektywności, stosując porządek heurystyczny do przeszukiwania drzew, które są odcinane na wczesnym etapie. Na przykład w szachach ruchy, które biją pionki, mogą być sprawdzane wcześniej, a ruchy oceniane wysoko w poprzednich analizach mogą być priorytetowo traktowane. Inną popularną i tanią metodą heurystyczną jest weryfikacja na początku ruchów, które spowodowały beta-odcięcie na tej samej głębokości. Ta koncepcja może być uogólniona jako refutation tables.
Przeszukiwanie może być jeszcze szybsze, gdy rozważa się wąskie okno przeszukiwania, oparte na doświadczeniu. Technika ta nazywa się aspiration search. W skrajnych przypadkach przeszukiwanie odbywa się z alfa = beta, co nazywa się zero-window search, null-window search lub scout search. Jest to przydatne w kontekście poszukiwań wygrywających/przegrywających w końcowych fazach gry, gdzie najwęższe okno i proste rozwiązania mogą prowadzić do szybkiego zakończenia rozgrywki. Jeśli aspiration search zawiedzie, warto sprawdzić, czy przyczyną była zbyt duża alfa lub zbyt mała beta, co dostarczy informacji, czy wartości okna mogą być użyteczne w nowym poszukiwaniu rozwiązania.
Inne algorytmy
Bardziej zaawansowane algorytmy, które potrafią jeszcze szybciej obliczyć dokładną wartość min-max, to Negascout i MTD-f.
Jako że min-max i jego warianty są rozwinięciem przeszukiwania w głąb, zazwyczaj w połączeniu z alfa-beta stosuje się iteracyjne pogłębianie, co pozwala na zwrócenie dobrego ruchu nawet wtedy, gdy algorytm został przerwany przed zakończeniem. Inną zaletą stosowania metod przeszukiwania iteracyjnego jest to, że na niskich głębokościach dostarczają one wskazówek do porządkowania ruchów, które mogą być pomocne w szybkim odcinaniu gałęzi na większych głębokościach.
Algorytmy takie jak SSS* z drugiej strony wykorzystują strategię best-first strategy.
Pseudokod
Pseudokod dla 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
== 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. [zarchiwizowane z tego adresu (2007-04-30)].
Beowulf Computer Chess Engine. [dostęp 2017-07-13]. (ang.).
