PL 
EnglishDomyślny
Українська♟️ Minimax i alfa-beta
Przeszukiwanie drzewa gry w głąb przy założeniu optymalnej gry przeciwnika; obcinanie alfa-beta pomija gałęzie bez znaczenia. Patrz, jak okno (α, β) się zawęża, odcięcia wyszarzają poddrzewa, i porównuj liczbę odwiedzonych liści.
O algorytmie minimax z przycinaniem alfa-beta
Minimax to rekurencyjny algorytm przeszukiwania przeciwstawnego, używany w grach dwuosobowych o sumie zerowej. Gracz MAX (np. sztuczna inteligencja) stara się zmaksymalizować heurystyczną wartość stanu gry, podczas gdy gracz MIN (przeciwnik) stara się ją zminimalizować; minimax wykonuje przeszukiwanie w głąb do węzłów liści, a następnie propaguje wartości w górę, na przemian biorąc maksimum i minimum na każdym poziomie. Dla drzewa gry o współczynniku rozgałęzienia b i głębokości d naiwny minimax ocenia O(b^d) węzłów — dla szachów jest to astronomicznie duża liczba.
Przycinanie alfa-beta to ulepszenie utrzymujące dwie granice — alfa (najlepsza wartość, jaką może zagwarantować MAX) i beta (najlepsza wartość, jaką może zagwarantować MIN) — i porzucające (przycinające) każde poddrzewo, w którym wiadomo już, że istnieje lepsza opcja. W najlepszym przypadku alfa-beta redukuje liczbę ocenianych węzłów do O(b^(d/2)), efektywnie podwajając głębokość przeszukiwania przy tym samym koszcie. Wizualizator pozwala włączać i wyłączać przycinanie oraz zliczać ocenione węzły w każdym trybie.
Najczęściej zadawane pytania
Czym jest algorytm minimax i gdzie jest wykorzystywany?
Minimax to algorytm decyzyjny dla dwuosobowych gier o sumie zerowej z pełną informacją, takich jak szachy, go, warcaby, czwórka w rzędzie i kółko i krzyżyk. Zakłada, że obaj gracze grają optymalnie: MAX zawsze wybiera ruch o najwyższej wartości minimax; MIN zawsze wybiera ruch o najniższej. Algorytm został sformalizowany przez Johna von Neumanna w jego dowodzie twierdzenia minimax z 1928 roku.
O ile przycinanie alfa-beta redukuje przeszukiwanie?
W najlepszym przypadku (optymalna kolejność ruchów, gdy najlepszy ruch jest zawsze przeszukiwany jako pierwszy) alfa-beta przycina wystarczająco dużo, by ocenić tylko O(b^(d/2)) węzłów liści zamiast O(b^d). Dla szachów (b ≈ 35) oznacza to przeszukiwanie do głębokości 10 zamiast 5 przy tym samym budżecie obliczeniowym. W praktyce, przy dobrych heurystykach kolejności ruchów, prawdziwe silniki szachowe osiągają 60–80% przycinania najlepszego przypadku, mniej więcej podwajając efektywną głębokość.
Co reprezentują granice alfa i beta?
Alfa to najlepszy wynik zagwarantowany graczowi MAX z dowolnej pozycji wzdłuż bieżącej ścieżki — tylko rośnie. Beta to najlepszy wynik zagwarantowany graczowi MIN — tylko maleje. Gdy alfa ≥ beta w węźle MIN (lub beta ≤ alfa w węźle MAX), pozostałe węzły siostrzane nie mogą wpłynąć na wynik i są przycinane. Warunek alfa ≥ beta nazywany jest odcięciem (cutoff).
Czym jest kolejność ruchów i dlaczego ma znaczenie dla alfa-beta?
Efektywność przycinania alfa-beta silnie zależy od kolejności, w jakiej przeszukiwane są ruchy. Jeśli najlepszy ruch jest badany jako pierwszy, odcięcia następują wcześnie i osiągane jest maksymalne przycinanie. Popularne heurystyki kolejności obejmują heurystykę ruchu zabójczego (próbuj ruchów, które spowodowały odcięcia w węzłach siostrzanych), heurystykę historii oraz przeszukiwanie bić przed ruchami spokojnymi. Nowoczesne silniki, takie jak Stockfish, poświęcają znaczny wysiłek na kolejność ruchów, by zbliżyć się do wydajności alfa-beta z najlepszego przypadku.
Czym jest negamax i jak upraszcza implementację?
Negamax to przeformułowanie minimax wykorzystujące własność sumy zerowej: wartość dla bieżącego gracza jest zawsze przeciwieństwem wartości dla przeciwnika. Pozwala to na użycie jednej funkcji rekurencyjnej zamiast dwóch naprzemiennych: zwróć maksimum po dzieciach z (−negamax(dziecko)). Przycinanie alfa-beta integruje się z tym elegancko: alfa = −beta_rodzica, beta = −alfa_rodzica przy każdym wywołaniu rekurencyjnym.
Czym jest tablica transpozycji i jak uzupełnia alfa-beta?
Tablica transpozycji to mapa haszująca pozycje planszy na wcześniej obliczone wartości minimax i najlepsze ruchy. Ponieważ wiele różnych sekwencji ruchów prowadzi do tej samej pozycji, buforowanie wyników unika ponownej oceny identycznych poddrzew. Nowoczesne silniki szachowe używają 64-bitowego haszowania Zobrista i tablic transpozycji o rozmiarze 512 MB–2 GB, często osiągając ponad 90% trafień pamięci podręcznej w środkowej fazie gry, znacznie wzmacniając skuteczność alfa-beta.
Czym jest efekt horyzontu w przeszukiwaniu drzewa gry?
Efekt horyzontu występuje, gdy przeszukiwanie zatrzymuje się na stałej głębokości, powodując pominięcie konsekwencji ważnych zdarzeń tuż za tą głębokością. Na przykład silnik szachowy mógłby poświęcić figurę, by odsunąć nieuniknioną utratę hetmana poza horyzont przeszukiwania, sprawiając, że przegrana pozycja wygląda na neutralną. Przeszukiwanie quiescence — rozszerzające przeszukiwanie w węzłach liści aż do osiągnięcia „spokojnej” pozycji (bez bić) — łagodzi to niewielkim dodatkowym kosztem.
Czym różni się przeszukiwanie drzewa Monte Carlo (MCTS) od minimax?
MCTS nie używa heurystycznej funkcji oceny. Zamiast tego uruchamia losowe symulacje (rollouts) z węzłów do stanów końcowych i wykorzystuje wyniki statystyczne do oszacowania wartości węzłów. Czyni to dobrze dopasowanym do gier takich jak go, gdzie trudno zaprojektować dobre heurystyki. AlphaGo połączyło MCTS z głębokimi sieciami neuronowymi polityki/wartości, osiągając ponadludzki poziom gry w go w 2016 roku. Minimax z alfa-beta pozostaje dominujący w grach klasycznych, takich jak szachy, gdzie istnieją silne funkcje oceny.
Czym jest pogłębianie iteracyjne w połączeniu z minimax?
Przeszukiwanie w głąb z pogłębianiem iteracyjnym (IDDFS) wielokrotnie uruchamia alfa-beta do rosnących głębokości (1, 2, 3, …), aż zostanie osiągnięty limit czasu. Wydaje się to marnotrawne, ale jest efektywne, ponieważ liczba węzłów na głębokości d dominuje nad sumą wszystkich płytszych głębokości dla typowych współczynników rozgałęzienia. Kluczową korzyścią jest to, że wyniki z płytszych przeszukiwań dają doskonałe informacje o kolejności ruchów dla głębszego przeszukiwania, poprawiając efektywność przycinania.
O tej symulacji
Ta symulacja wizualizuje przeszukiwanie minimax na drzewie gry, które kształtujesz samodzielnie, pokazując, jak czerwony gracz MAX i niebieski gracz MIN na przemian wykonują ruchy, podczas gdy wartości wędrują w górę od liści. Włącz przycinanie alfa-beta, by zobaczyć, jak gałęzie są skreślane w momencie, gdy nie mogą już wpłynąć na wynik.
🔬 Co pokazuje
Drzewo gry o wybranym współczynniku rozgałęzienia i głębokości. Czerwone węzły MAX przyjmują największą wartość dziecka, niebieskie węzły MIN najmniejszą. W trybie alfa-beta każdy węzeł śledzi okno α/β, a przerywane szare gałęzie oznaczają poddrzewa przycięte, gdy β spadnie do lub poniżej α.
🎮 Jak korzystać
Wybierz kształt drzewa, a następnie ustaw współczynnik rozgałęzienia b i głębokość d suwakami. Wybierz Czysty minimax lub Alfa-beta, plus losową lub najlepszą-najpierw kolejność ruchów, a następnie naciśnij Krok, by przejść o jeden węzeł, albo Auto, by animować z wybraną prędkością.
💡 Czy wiesz, że?
Przy kolejności najlepszy-najpierw przycinanie alfa-beta może zredukować liczbę badanych węzłów z w przybliżeniu b^d do b^(d/2) — efektywnie podwajając przeszukiwalną głębokość przy tym samym wysiłku, dlatego silniki szachowe na nim polegają.
Najczęściej zadawane pytania
Jaka jest różnica między czystym minimax a przycinaniem alfa-beta?
Czysty minimax odwiedza każdy węzeł, by obliczyć poprawną wartość. Alfa-beta osiąga ten sam wynik, pomijając gałęzie, które dowiedlnie nie mogą zmienić wyniku — licznik „Odcięcia” pokazuje, ile z nich pominięto.
Dlaczego kolejność ruchów wpływa na ilość przycinania?
Przycinanie uruchamia się dopiero, gdy znana jest dobra wartość. Kolejność najlepszy-najpierw przeszukuje najpierw obiecujące dzieci, wcześnie zawężając okno i wyzwalając więcej odcięć; kolejność losowa przycina średnio mniej.
Co reprezentują czerwone i niebieskie węzły?
Czerwone węzły to MAX, próbujący zmaksymalizować wynik; niebieskie węzły to MIN, próbujący go zminimalizować. Obie role zmieniają się na każdym poziomie głębokości.
Co dzieje się ze skreślonymi gałęziami?
Gdy okno α/β węzła się zamyka (β ≤ α), jego pozostałe nieprzeszukane dzieci są pomijane i rysowane jako skreślone przerywaną linią, ponieważ żadna wartość, jaką mogłyby mieć, nie mogłaby zmienić decyzji rodzica.
Czy współczynnik rozgałęzienia i głębokość razem zmieniają czas przeszukiwania?
Tak — łączna liczba liści to w przybliżeniu b do potęgi d, więc zwiększenie głębokości o jeden ma podobny efekt do pomnożenia współczynnika rozgałęzienia. Obserwuj „Węzły łącznie” w panelu statystyk.