Minimax i Przycinanie Alfa-Beta: Przeszukiwanie Drzewa, Którego Nikt Nie Zdoła Skończyć

Załóżmy, że przeciwnik jest idealny

Minimax to podstawowy algorytm przeszukiwania dla dwu-graczowych gier zerową sumę z pełną informacją – w tym szachy, warcia i kropkę. Buduje drzewo możliwych przyszłych pozycji, przechodząc na zmianę między graczem maksymalizującym wynik (chcący najwyższego wyniku) a graczem minimalizującym (chcącym najniższego), oraz ocenia każdą pozycję, zakładając, że każdy z graczy zawsze wybierze najlepszy możliwy ruch z tego punktu widzenia. Nazwa dokładnie opisuje to: każdy gracz minimalizuje maksymalne uszkodzenie, które może wyrządzić drugi gracz, lub maksymalizuje swój gwarantowany minimalny wynik, w zależności od kolejności ruchów.

minimax(node, depth, maximizingPlayer):
  if depth == 0 or node is terminal:
    return evaluate(node)
  if maximizingPlayer:
    value = −infinity
    for each child of node:
      value = max(value, minimax(child, depth−1, false))
    return value
  else:
    value = +infinity
    for each child of node:
      value = min(value, minimax(child, depth−1, true))
    return value

Ekspozycyjny mur

Prosta minimalna gra bada kazdy wierzch drzewa, a rozmiar drzewa rosnie wykładniczo do O(b^d), gdzie b jest rozgałęzieniem (około 35 legalnych ruchów na pozycji w szachach) a d to liczba ruchów w przód, które oglądasz. Nawet umiarkowana głębokość 10 półruchów w szachach implikuje badanie rzędu 35^10 pozycji - znacznie więcej niż może odwiedzić żaden komputer, dlatego też silniki szachowe nigdy nie przeszukują do końca gry. Zamiast tego przeszukują do ustalonej głębokości i zastępują prawdziwy wynik funkcją heurystyczną oceniającą pozycję na podstawie materiału, bezpieczeństwa króla, aktywności figur itp.

Alfa-beta: przycinanie tego, czego nie da się uwzględnić

Przycinanie alfa-beta przyspiesza algorytm minimax bez zmiany jego odpowiedzi, śledząc dwa ograniczenia w trakcie poszukiwań: alfę, czyli najlepszy wynik, który maksymalizator jest tam gdzieś gwarantowany w drzewie, i bety, czyli najlepszy wynik, który minimalizator jest tam gdzieś gwarantowany. W momencie, gdy wartość węzła wypadłaby poza aktualne (alfa, beta) okno – co oznacza, że racjonalny przeciwnik nigdy nie pozwoliłby grze osiągnąć tego stanu – wszystkie pozostałe rodzeństwa danego węzła są całkowicie pominięte, ponieważ niezależnie od tego, do jakich wartości je ocenią, nie mogą one zmienić decyzji na jednym poziomie wyżej.

alphabeta(node, depth, α, β, maximizingPlayer):
  if depth == 0 or node is terminal:
    return evaluate(node)
  if maximizingPlayer:
    value = −infinity
    for each child of node:
      value = max(value, alphabeta(child, depth−1, α, β, false))
      α = max(α, value)
      if α >= β: break        // β cutoff — rest of the siblings pruned
    return value
  else:
    value = +infinity
    for each child of node:
      value = min(value, alphabeta(child, depth−1, α, β, true))
      β = min(β, value)
      if β <= α: break        // α cutoff — rest of the siblings pruned
    return value

To samo rozwiązanie, radykalnie mniej pracy

Jest to właściść, która sprawia, że prewencyjne przycinanie alfa-beta jest bezpieczne do użycia wszędzie tam, gdzie stosuje się minimax: nie jest to skrót heurystyczny, a dokładna optymalizacja. Przy identycznej głębokości wyszukiwania i funkcji oceny, alpha-beta zawsze zwraca dokładnie ruch, który znalazłby w zasadzie minimax, ponieważ każdy pominięty gałąź została udowodniona jako nieistotny dla wyniku, a nie tylko przypuszczono, że jest obiecująca. W najlepszym przypadku, gdy ruchy są przeszukiwane w idealnej kolejności, alpha-beta redukuje efektywny współczynnik rozgałęzania z b do około √b, co przycinając drzewo zmniejsza go z O(b^d) na około O(b^(d/2)) - co w praktyce oznacza przeszukanie dwukrotnie głębiej za tę samą ilość obliczeń.

Kolejność ruchów to cała gra

Rozmiar przyspieszenia zależy w pełni od kolejności, w jakiej są sprawdzane ruchy. Pruning działa tylko wtedy, gdy raz znaleziono wystarczająco dobry ruch na węźle, więc jeśli najsilniejszy ruch jest badany pierwszy, okno (alpha, beta) natychmiast się zamyka i większość pozostałych braci nie zostaje nigdy oceniona. Zamiast tego, sprawdź najsłabszy ruch jako pierwszy, a okno pozostanie szerokie, pruning działa słabo, a wydajność pogarsza się w kierunku prostej, niezamkniętej przeszukiwania minimax. Dlatego też silne konstrukcje inwestują duże środki w heurystyki sortowania ruchów – próbując pierwszych uderzeń zanim sprawdzasz spokojne ruchy, wcześniej odkryte najlepsze ruchy, ruchy zabójcze, które spowodowały wyłączenia na węzłach braci - ponieważ dobre sortowanie jest często warte więcej niż jakakolwiek inna pojedyncza optymalizacja ogólnej szybkości przeszukiwania.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Minimax and Alpha-Beta Pruning i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.