Monte Carlo Tree Search: Przeszukiwanie Drzewa Gry, Którego Nigdy Nie Można Pełne Zbudować

Wyszukiwanie bez pełnego drzewa

Szachy mają około 10^120 możliwych gier i Go więcej pozycji legalnych niż atomy w obserwowalnym wszechświecie, więc żaden komputer nie może nigdy rozwinąć pełnego drzewa gry dla żadnej z nich. Monte Carlo Tree Search (MCTS) omija ten problem: zamiast wyczerpująco rozszerzać każdy gałąź, buduje się małe, skośne drzewo, które rośnie najszybciej tam, gdzie gra wydaje się mieć znaczenie, kierowane przez losowe symulacje zamiast ręcznie dostrojonej funkcji oceny.

Algorytm powtarza cztery fazy, raz za razem, tak długo, jak możesz sobie pozwolić na myślenie: selekcję, rozbudowę, symulację (zwany również rozegraniem) i propagację wsteczną. Każde powtórzenie to jedno odwiedzenie; po tysiącach wizyt kształt drzewa sam w sobie jest odpowiedzią – dziecko korzenia z największą liczbą wizyt jest zalecanym ruchem, ponieważ liczba wizyt koreluję z ruchem przetrwałym weryfikację, a nie z pojedynczym szczęśliwym rozegraniem.

Selekcja: formuła UCB1

Zaczynając od korzenia, algorytm przechodzi w dół istniejącego drzewa zawsze wybierając dziecko, które maksymalizuje wynik UCB1 (Górny Wąs Konfidencyjny), aż do momentu, gdy osiągnie węzeł nie jeszcze w pełni rozbudowany:

UCB1(węzel) = stopień_zwycięgzenia(węzel) + C * pierwiastek(ln(wizyty_rodzica)/wizyty_węzła) \_____ wykorzystanie ____/ \______ eksploracja ______/ Pierwszy termin nagradza ruchy, które często wygrywały – wykorzystanie. Drugi termin rośnie dla dowolnego dziecka, które zostało odwiedzone rzadko w porównaniu z rodzicem – eksploracja – i rośnie bez ograniczeń, gdy węzeł jest zaniedbywany, gwarantując, że każde dziecko ostatecznie zostanie ponownie odwiedzona nawet po serii nieudanych symulacji. Stała C (pierwiastek dwóch w oryginalnej formule) ustawia równowagę; większa wartość C przeszukuje szerszy obszar, a mniejsza wartość szybcieWIE pogłębia się w obiecujących liniach szybciej.

UCB1(node) = winRate(node) + C * sqrt( ln(parentVisits) / nodeVisits )
             \_____ exploitation ____/   \______ exploration ______/

Rozbudowa, symulacja, propagacja wsteczna

Gdy wybór osiąga węzeł z niezbadanymi ruchami, jeden z nich jest dodawany do drzewa jako nowy podwęzel – rozbudowa. Od tego nowego podwęzła algorytm wykonuje symulację: ruchy wybierane losowo (lub według taniej polityki heurystycznej) aż do stanu terminalnego, zwycięstwa, przegranej lub remisu. Wynik tej jednej losowej gry stanowi jedyną nową informację, jaką w tym kroku wnosi się.

Ten wynik jest następnie propagowany wstecz przez wszystkie węzły odwiedzone podczas opadania – propagacja wsteczna – zwiększając liczbę wizyt i sumę zwycięstw każdego węzła. Pojedyncza symulacja jest prawie bezużytecznym szumem, ale celem UCB1 jest to, że tysiące szumów, ważonych przez ilość uwagi, jaką otrzymał każdy ruch, zbiega się w dystrybucję wizyt, która śledzi prawdziwą wartość każdego ruchu znacznie lepiej niż jakkolwiek pojedyncza symulacja.

function mctsIteration(root):
  node = root
  while node.fullyExpanded and node.children.length > 0:
    node = argmax(node.children, ucb1)          // selection
  if not node.isTerminal:
    node = expand(node)                          // expansion: add one child
  result = randomRollout(node.state)              // simulation
  while node !== null:
    node.visits += 1
    node.wins += result belongs to node's player ? 1 : 0
    node = node.parent                            // backpropagation

Dlaczego losowe rozważania działają

Wygląda na torebkę oceniać pozycję poprzez rozegranie jej z losowymi ruchami, ale losowe rozważania są obiektywnym, choć szumowym, oszacowaniem wartości pozycji, a MCTS potrzebuje jedynie względnego uporządkowania między ruchami braci, a nie dokładnej wartości bezwzględnej. Średnio wystarczającą liczbę niezależnych, szumowych próbek i prawo dużego liczby robi resztę. To właśnie dlatego MCTS uczynił komputer Go konkurencyjnym lata przed pojawieniem się głębokiego uczenia się – rozgałęzienie gry pokonało klasyczny algorytm alfa-beta z ręcznie zbudowaną funkcją oceny, ale drzewo, które adaptacyjnie wydala swoje rozważania tam, gdzie to ma największe znaczenie, nie potrzebowało jednej.

Nowoczesne silniki poprawiają rozważanie poprzez wyuczoną politykę i sieć wartości zamiast losowości – to jest rdzeń idei stojącej za AlphaGo i AlphaZero: sieć neuronowa proponuje, które ruchy warto rozszerzać i szacuje wartość pozycji bezpośrednio, dzięki czemu potrzebnych jest znacznie mniej losowych rozgrywek, a MCTS staje się konstrukcją poszukiwań wokół wyuczonego poczucia zamiast jego substytutu.

Gdzie MCTS błyszczy, a gdzie nie

MCTS potrzebuje w zasadzie niczego poza domeną – jedynie legalne ruchy i sygnał wygranej/przegranej – bez ręcznie tworzonej funkcji oceny, bez heurystyk specyficznych dla danej domeny, aby uzyskać rozsądnego gracza. To właśnie ta ogólność sprawiła, że rozprzestrzenił się on z Go na ogólną rozgrywkę, sztuczną inteligencję w czasie rzeczywistym, rozwiązywanie łamigłówek i nawet problemy nie związane z planowaniem. Ma jednak trudności w grach z bardzo długimi, głęboko taktycznymi sekwencjami, gdzie pojedyncze przypadkowe błędy w rozwijaniu (rollout) źle oceniają całą linię, oraz potrzebuje sposobu na zapobieganie nieograniczonemu wzrostowi drzewa bez ograniczeń pamięciowych, zwykle poprzez ograniczenie liczby węzłów lub wygasanie najmniej odwiedzanych gałęzi.

Frequently asked questions

Wypróbuj na żywo

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