🎯 Monte Carlo Tree Search
Sztuczna inteligencja w grach: selekcja UCB1, symulacja, propagacja wsteczna
Nim: zabierz 1, 2 lub 3 kamienie ze stosu 15 — wygrywa ten, kto weźmie ostatni
Sterowanie
Statystyki
Łączna liczba symulacji
0
Odwiedziny korzenia
0
Najlepszy ruch
—
Wielkość stosu
15
Informacje i teoria

Monte Carlo Tree Search (MCTS) buduje drzewo przeszukiwań przyrostowo, powtarzając cztery fazy i wykorzystując losowe symulacje zamiast ręcznie zaprojektowanej funkcji oceny.

Cztery fazy

  • Selekcja — zaczynając od korzenia, schodzimy w dół drzewa, wybierając za każdym razem dziecko maksymalizujące wartość UCB1, aż dotrzemy do węzła z niewypróbowanymi ruchami lub bez dzieci.
  • Ekspansja — dodajemy jeden nowy węzeł-dziecko dla niewypróbowanego ruchu.
  • Symulacja (rollout) — rozgrywamy losowe, ale legalne ruchy od nowego węzła aż do zakończenia gry.
  • Propagacja wsteczna (backpropagation) — wracamy do korzenia, aktualizując liczbę odwiedzin i wygranych na każdym węźle wzdłuż ścieżki.

UCB1: równowaga między eksploracją a eksploatacją

Upper Confidence Bound zastosowany do drzew (UCB1) wybiera dziecko maksymalizujące wyrażenie winRate + C·√(ln(parentVisits) / childVisits). Pierwszy człon faworyzuje ruchy, które często wygrywały (eksploatacja); drugi człon rośnie dla rzadko odwiedzanych dzieci (eksploracja), dzięki czemu przeszukiwanie wciąż próbkuje obiecujące, lecz słabo zbadane gałęzie zamiast skupiać się wyłącznie na wczesnych wynikach. C = √2 ≈ 1,41 to teoretycznie uzasadniona stała dla nagród z przedziału [0,1].

Bez potrzeby heurystycznej oceny

W przeciwieństwie do minimax, który wymaga ręcznie zaprojektowanej funkcji oceny do punktowania pozycji nieterminalnych, MCTS szacuje wartość pozycji wyłącznie na podstawie wyników losowych symulacji. Dzięki temu nadaje się do gier, w których trudno jest zaprojektować dobre heurystyki.

Zbieżność i zastosowania praktyczne

Wraz ze wzrostem liczby symulacji liczba odwiedzin koncentruje się na najsilniejszych ruchach, a oszacowania współczynnika wygranych zbiegają do rzeczywistych wartości gry. MCTS dobrze skaluje się przy dużych współczynnikach rozgałęzienia, dlatego napędzał systemy AlphaGo i AlphaZero, w których połączono go z głębokimi sieciami neuronowymi zastępującymi losowe symulacje wyuczonymi oszacowaniami wartości i polityki.

O Monte Carlo Tree Search

Autor: MySimulator Team · Recenzja: MySimulator Editorial Review

Ostatnia aktualizacja: 11 lipca 2026

Monte Carlo Tree Search (MCTS) to algorytm służący do znajdowania silnych ruchów w sekwencyjnych problemach decyzyjnych, takich jak gry planszowe, poprzez przyrostowe budowanie drzewa przeszukiwań za pomocą wielokrotnego losowego próbkowania. Każda iteracja składa się z czterech faz: selekcji, która schodzi w dół drzewa od korzenia, wykorzystując wzór UCB1 — winRate + C·√(ln(parentVisits)/childVisits) — aby zrównoważyć eksploatację znanych dobrych ruchów z eksploracją rzadziej odwiedzanych; ekspansji, która dodaje jeden nowy węzeł dla niewypróbowanego ruchu; symulacji (rollout), która rozgrywa losowe ruchy aż do stanu końcowego; oraz propagacji wstecznej, która aktualizuje statystyki odwiedzin i wygranych wzdłuż ścieżki powrotnej do korzenia. Ponieważ MCTS szacuje wartość pozycji na podstawie wyników symulacji, a nie ręcznie zaprojektowanej heurystyki, dobrze skaluje się do gier o ogromnym współczynniku rozgałęzienia, takich jak go, gdzie wyczerpujące przeszukiwanie minimax jest obliczeniowo niewykonalne. Ta właściwość sprawiła, że MCTS stał się fundamentem systemu AlphaGo firmy DeepMind, a w połączeniu z głębokimi sieciami neuronowymi zastępującymi losowe symulacje — także systemu AlphaZero, który przewyższył ludzką biegłość w grze w go, szachy i shogi.

Najczęściej zadawane pytania

Jakie są cztery fazy Monte Carlo Tree Search?

MCTS powtarza w każdej iteracji cztery fazy: selekcję, która schodzi w dół drzewa, wykorzystując UCB1 do wyboru obiecujących dzieci; ekspansję, która dodaje nowy węzeł-dziecko dla niewypróbowanego ruchu; symulację (rollout), która rozgrywa losowe ruchy aż do wyniku końcowego; oraz propagację wsteczną, która aktualizuje liczbę odwiedzin i wygranych dla każdego węzła na ścieżce powrotnej do korzenia. Powtórzenie tego tysiące razy tworzy asymetryczne drzewo skupione na silnych liniach gry.

Czym jest UCB1 i jak równoważy eksplorację z eksploatacją?

UCB1 (Upper Confidence Bound 1) ocenia każdy węzeł-dziecko jako winRate + C·√(ln(parentVisits)/childVisits). Człon współczynnika wygranych faworyzuje ruchy, które sprawdziły się dobrze (eksploatacja), natomiast człon pierwiastka kwadratowego rośnie dla dzieci z niewieloma odwiedzinami (eksploracja), przyciągając przeszukiwanie z powrotem do słabo zbadanych gałęzi. Stała C = √2 równoważy oba człony dla nagród w skali od 0 do 1.

Dlaczego losowa symulacja wystarcza bez ręcznie zaprojektowanej funkcji oceny?

Pojedyncza losowa symulacja jest szumowa, ale uśredniona po wielu symulacjach daje nieobciążone statystyczne oszacowanie rzeczywistego prawdopodobieństwa wygranej danej pozycji. Dzięki temu MCTS może oceniać pozycje w grach, w których zaprojektowanie dokładnej heurystycznej funkcji oceny — wymaganej przez minimax — byłoby trudne lub niemożliwe, tak jak w przypadku ogromnej i silnie zależnej od wzorców przestrzeni stanów gry go.

Gdzie MCTS jest wykorzystywany w praktycznych systemach sztucznej inteligencji do gier?

MCTS jest podstawowym algorytmem przeszukiwania stojącym za systemem AlphaGo firmy DeepMind, który w 2016 roku pokonał czołowych ludzkich graczy w go, oraz jego następcą AlphaZero, który opanował go, szachy i shogi dzięki grze z samym sobą. W tych systemach losowe symulacje MCTS zastąpiono oszacowaniami wartości i polityki wytrenowanej sieci neuronowej, jednak struktura selekcja–ekspansja–propagacja wsteczna przeszukiwania drzewa pozostała niezmieniona.