Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search

Gra jako problem przeszukiwania, drzewo gry, minimax, przycinanie alfa-beta, funkcja oceny i MCTS — na kółku i krzyżyku, gdzie da się policzyć wszystko, oraz droga od Deep Blue do AlphaZero.

14 minut Matěj Žalmánek 2026-10-15

Seria Podstawy AI Część 22 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

W labiryncie z poprzedniej części ludzik stał sam. Świat się nie poruszał, a każdy ruch prowadził tam, dokąd miał. W grze naprzeciw ciebie siedzi jednak ktoś, kto chce dokładnie odwrotnie — i na każdy twój ruch odpowie tym, który zaboli cię najbardziej. Szukanie drogi do celu już nie wystarcza: musisz szukać strategii, która wytrzyma każdą odpowiedź. Szachy, warcaby i go przez dziesięciolecia były miarą sztucznej inteligencji, a algorytmy z tej części stoją za Deep Blue i za AlphaGo.

Nawiązuje do części Przeszukiwanie przestrzeni stanów i Grafy i drzewa.

1. Gra jako problem przeszukiwania

Definicja — gra dwóch graczy

Gra to siódemka Γ = (S, s₀, gracz, A, T, K, U), gdzie

• S, s₀, A(s) i T to stany, stan początkowy, akcje i funkcja przejścia jak w problemie przeszukiwania,
• gracz : S → {MAX, MIN} mówi, kto w danym stanie ma ruch,
• K ⊆ S to zbiór stanów końcowych — tam gra się kończy,
• U : K → ℝ to użyteczność stanu końcowego z punktu widzenia gracza MAX.

Gra ma sumę zerową: co MAX zyska, MIN straci, więc użyteczność MIN wynosi −U. Gracze wykonują ruchy na przemian, ruchy są deterministyczne i obaj widzą cały stan (pełna informacja).

Różnica w porównaniu z przeszukiwaniem jest zasadnicza. Rozwiązaniem nie jest już ścieżka — tej nie wybierzesz, bo co drugi ruch wykonuje przeciwnik. Rozwiązaniem jest strategia: przepis, jak odpowiedzieć na każdy ruch, który przeciwnik może wykonać.

2. Drzewo gry

Definicja — drzewo gry

Drzewo gry to drzewo ukorzenione, którego korzeniem jest s₀, a dziećmi węzła s są następniki {T(s, a) : a ∈ A(s)}. Liście to stany końcowe. Węzły, w których ruch ma MAX, rysujemy jako trójkąt wierzchołkiem w górę, węzły MIN wierzchołkiem w dół.

Jeśli gra ma współczynnik rozgałęzienia b i trwa najwyżej m ruchów, drzewo ma do b^m liści.

Kółko i krzyżyk na planszy 3 × 3 to mała gra, a mimo to jej drzewo ma 549 946 węzłów i 255 168 liści — tyle różnych partii da się rozegrać. Różnych pozycji jest przy tym tylko 5 478: do tej samej pozycji dojdziesz wieloma kolejnościami ruchów. Szachy mają współczynnik rozgałęzienia około 35, a partia trwa dziesiątki ruchów; Claude Shannon w 1950 roku oszacował ich drzewo na 10¹²⁰ partii. Go ze współczynnikiem rozgałęzienia około 250 jest jeszcze o wiele rzędów wielkości dalej. Całe drzewo przejdziemy więc tylko w małych grach — w dużych musimy się nauczyć, które gałęzie pominąć.

3. Minimax

Definicja — wartość minimaksowa

Wartość minimaksowa stanu s to

• MM(s) = U(s), gdy s ∈ K,
• MM(s) = max_{a ∈ A(s)} MM(T(s, a)), gdy gracz(s) = MAX,
• MM(s) = min_{a ∈ A(s)} MM(T(s, a)), gdy gracz(s) = MIN.

Optymalny ruch gracza MAX w stanie s to argmax_a MM(T(s, a)).

Lewy węzeł MIN z liści 4, 6 i 9 wybiera 4, środkowy z 2, 7 i 8 wybiera 2, prawy z 5, 3 i 9 wybiera 3. MAX w korzeniu wybiera potem między 4, 2 i 3 i wykonuje lewy ruch o wartości 4. Zauważ, że prawa gałąź skrywa dziewiątkę — tyle że MAX nigdy do niej nie dotrze, bo MIN zagrałby zamiast niej trójkę.

Twierdzenie — co gwarantuje minimax

Jeśli MAX gra optymalnie, uzyska co najmniej MM(s₀) przeciw dowolnej strategii MIN. Jeśli optymalnie gra także MIN, MAX uzyska dokładnie MM(s₀).

Minimax przechodzi drzewo w głąb: czas O(b^m), pamięć O(b · m).

4. Minimax w kółko i krzyżyk

Kółko i krzyżyk 3 × 3 jest na tyle małe, że minimax przejdzie całe drzewo. Wynik zna każdy, kto grał w nie dłużej niż kilka minut: wartość minimaksowa pustej planszy wynosi 0 — gdy obaj grają bezbłędnie, zawsze jest remis. Ciekawsze jest to, co minimax powie o konkretnej pozycji. Ruch ma X (MAX), a w każdym wolnym polu jest wartość ruchu na nie:

Wygrywa jedyny ruch — środek. X buduje nim widełki: grozi dokończeniem środkowego wiersza i przekątnej, a O nie może zablokować obu. Ruch na dół pośrodku utrzymuje remis. Pozostałe trzy ruchy wyglądają niewinnie, ale przegrywają: O odpowie na nie własnymi widełkami. Człowiek musiałby to przemyśleć; minimax po prostu to oblicza.

def minimax(board):
    end = winner(board)                 # "X", "O", "draw" lub None
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    values = [minimax(play(board, move)) for move in empty_squares(board)]
    return max(values) if to_move(board) == "X" else min(values)

5. Przycinanie alfa-beta

Minimax przechodzi całe drzewo, choć w połowie jest ono zbędne. Spójrz jeszcze raz na środkową gałąź: pierwszy liść pokazał 2. MIN osiągnie więc w tej gałęzi 2 lub mniej — a MAX ma już pewną lewą gałąź o wartości 4. Jakiekolwiek byłyby pozostałe dwa liście, MAX do środkowej gałęzi nie pójdzie. Nie musi na nie nawet patrzeć.

Definicja — alfa-beta

Przeszukiwanie w głąb niesie ze sobą dwie granice:

• α — najwyższa wartość, jaką MAX już zapewnił sobie gdzieś na ścieżce od korzenia (na początku −∞),
• β — najniższa wartość, jaką zapewnił sobie MIN (na początku +∞).

W węźle MAX po każdym dziecku ustawia się v ← max(v, wartość dziecka) i α ← max(α, v); w węźle MIN analogicznie v ← min(…) i β ← min(β, v). Gdy tylko α ≥ β, pozostałe dzieci węzła zostają przycięte — nie są przeszukiwane.

Twierdzenie. Alfa-beta zwraca w korzeniu tę samą wartość co minimax. Przy najlepszej możliwej kolejności ruchów bada tylko O(b^m/2) węzłów.

Alfa-beta doszła do tego samego wyniku — MAX gra w lewo i uzyskuje 4 — ale oceniła tylko 6 liści z 9. W środkowej gałęzi przycięła dwa liście zaraz po dwójce, w prawej jeden po trójce. Przy przyciętym węźle MIN jest więc tylko granica „≤ 2” i „≤ 3”: dokładnej wartości nie znamy i nie potrzebujemy jej.

W kółku i krzyżyku różnica jest bardziej dramatyczna. Pełny minimax z pustej planszy odwiedza 549 946 pozycji, alfa-beta przy tej samej kolejności ruchów tylko 18 297 — mniej więcej trzydzieści razy mniej — i zwraca to samo zero. Wykładnik m/2 w twierdzeniu oznacza, że w tym samym czasie sięgniesz wzrokiem dwa razy głębiej. Dlatego kolejność ruchów ma tak duże znaczenie: programy szachowe sprawdzają najpierw bicia i ruchy, które okazały się dobre poprzednio.

def alphabeta(board, alpha=-inf, beta=inf):
    end = winner(board)
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    maximizing = to_move(board) == "X"
    v = -inf if maximizing else inf
    for move in empty_squares(board):
        h = alphabeta(play(board, move), alpha, beta)
        if maximizing:
            v = max(v, h); alpha = max(alpha, v)
        else:
            v = min(v, h); beta = min(beta, v)
        if alpha >= beta:
            break                          # cięcie: reszta gałęzi niczego nie zmieni
    return v

6. Ograniczona głębokość i funkcja oceny

Nawet alfa-beta nie przejdzie drzewa szachów do końca partii. Prawdziwe programy szukają więc tylko do ustalonej głębokości, a pozycję, w której skończą, szacują.

Definicja — minimax z ograniczoną głębokością

Funkcja oceny E : S → ℝ szacuje MM(s) i dla stanów końcowych pokrywa się z U. Zwykle jest to ważona suma cech pozycji: E(s) = w₁f₁(s) + … + w_nf_n(s).

Minimax do głębokości d: MM_d(s) = E(s), gdy s ∈ K lub d = 0; w przeciwnym razie max, odpowiednio min z MM_d−1 następników.

Ograniczona głębokość ma swoją pułapkę: efekt horyzontu. Gdy przeszukiwanie skończy się w środku wymiany figur — właśnie zbiłeś hetmana, przeciwnik za ruch zbije go z powrotem —, funkcja oceny widzi tylko pierwszą połowę i przecenia pozycję. Programy bronią się przed tym, przeszukując „niespokojne” pozycje dalej, dopóki się nie uspokoją. A ponieważ nigdy nie wiedzą, ile mają czasu, szukają iteracyjnym pogłębianiem z poprzedniej części: głębokość 1, 2, 3, … dopóki nie skończy się czas. Wyniki płytkich przejść służą przy tym jako kolejność ruchów dla głębszych — a alfa-beta przycina wtedy znacznie więcej.

7. Monte Carlo tree search

Funkcję oceny dla szachów ludzie dopracowywali przez dziesięciolecia. Dla go nie udawało się jej napisać — pozycja, która wygląda spokojnie, może o dwadzieścia ruchów później okazać się przegrana. Monte Carlo tree search (MCTS) całkowicie rezygnuje z funkcji oceny. Zamiast szacować pozycję, rozgrywa ją do końca: losowo, wiele razy, i sprawdza, jak często skończyło się to dobrze.

Definicja — jedna iteracja MCTS

Drzewo rośnie od korzenia s₀. Każdy węzeł i pamięta liczbę odwiedzin n_i i sumę wyników w_i z punktu widzenia gracza, który wykonał ruch do tego węzła (wygrana 1, remis ½, przegrana 0). Iteracja ma cztery kroki:

1. Wybór — od korzenia wielokrotnie idź do dziecka o najwyższej wartości UCT, dopóki nie trafisz na węzeł, który nie ma jeszcze wszystkich dzieci.
2. Rozszerzenie — dodaj mu jedno dziecko za dotąd niewypróbowany ruch.
3. Symulacja — z nowego węzła rozegraj partię losowymi ruchami aż do stanu końcowego.
4. Propagacja wsteczna — wszystkim węzłom na ścieżce z powrotem do korzenia dodaj n ← n + 1, a do w wynik partii.

Po wyczerpaniu czasu wykonuje się ruch z korzenia o największym n.

Definicja — UCT

W kroku wyboru spośród dzieci węzła o N odwiedzinach wybiera się dziecko i o największej wartości

UCT(i) = w_i / n_i + c · √(ln N / n_i),

gdzie c > 0 to stała eksploracji, zwykle √2. Przy rosnącej liczbie iteracji zalecany ruch zbliża się do minimaksowego.

Puśćmy MCTS na pozycję, którą minimax rozszyfrował wyżej. Liczby w polach to odwiedziny po 100, 300 i 1000 iteracjach, pod nimi średni wynik dla X:

Po 100 iteracjach środek ma 47 odwiedzin, a pozostałe ruchy razem więcej. Po tysiącu ma ich 856 i średni wynik 0,94; remisowy ruch na dole pośrodku dostał 52 odwiedziny, przegrywające ruchy jeszcze mniej. MCTS przy tym nie zna ani pojęcia widełek, ani żadnej funkcji oceny — tylko zasady i przypadek. A mimo to znalazł ten sam ruch co minimax, który musiał przejść całą resztę drzewa.

8. Od Deep Blue do AlphaZero

• Deep Blue (1997) pokonał mistrza świata Garriego Kasparowa. W środku była alfa-beta z ręcznie napisaną funkcją oceny i wyspecjalizowany sprzęt, który przetwarzał około 200 milionów pozycji na sekundę.
• Chinook grał w warcaby z mistrzami świata już w latach 90., a w 2007 roku jego autorzy grę rozwiązali: przeszli tyle pozycji, że udowodnili, iż bezbłędna partia kończy się remisem — tak samo jak kółko i krzyżyk 3 × 3.
• AlphaGo (2016) pokonał Lee Se-dola 4 : 1. Połączył MCTS z sieciami neuronowymi: jedna sieć proponowała obiecujące ruchy (zamiast losowego wyboru), druga szacowała wartość pozycji (zamiast całej losowej rozgrywki).
• AlphaZero (2017) porzucił nawet ludzkie partie. Nauczył się szachów, shogi i go wyłącznie przez grę sam ze sobą — uczeniem ze wzmocnieniem — i w każdej z tych gier pokonał najlepszy dotychczasowy program.
• Gry z losowością i ukrytą informacją wymagają więcej. W backgammonie decyduje kostka, więc do drzewa dodaje się węzły losowe z wartością oczekiwaną (expectiminimax). W pokerze nie widzisz kart przeciwnika; program Libratus (2017) mimo to pokonał profesjonalistów w pokerze dwóch graczy.

Idea „spójrz naprzód, zanim coś zrobisz” nie zniknęła z szachownic. Planujący agenci językowi próbują kilku wariantów postępowania, oceniają je i kontynuują tym najbardziej obiecującym — tylko zamiast ruchów figur wybierają kroki rozwiązania.

9. Podsumowanie

• Gra dwóch graczy o sumie zerowej to problem przeszukiwania, w którym dzielisz się ruchami z przeciwnikiem; rozwiązaniem jest strategia, a nie ścieżka.
• Minimax oblicza wartość od końca: MAX bierze maksimum, MIN minimum. Wynik jest gwarantowany przeciw dowolnemu przeciwnikowi.
• Alfa-beta zwraca tę samą wartość, ale przycina gałęzie, które nie mogą zmienić wyniku; przy dobrej kolejności ruchów sięga wzrokiem dwa razy głębiej.
• Duże gry przeszukuje się do ograniczonej głębokości z funkcją oceny — i uwaga na efekt horyzontu.
• MCTS zamiast oceniać pozycję wiele razy losowo rozgrywa ją do końca i rozwija drzewo tam, gdzie jest to obiecujące; w połączeniu z sieciami neuronowymi powstał z niego AlphaGo.

Chcesz to wypróbować? Poproś agenta AI o napisanie kółka i krzyżyka z minimaksem, a potem policz, ile pozycji oszczędzi alfa-beta, gdy uporządkujesz ruchy od środka do brzegów.

Masz inne zdanie? Napisz na support@coden-app.com.