Przeszukiwanie drzewa Monte Carlo: Przegląd wad, zalet i ograniczeń w złożonych grach wieloosobowych

1. Wprowadzenie

Monte Carlo Tree Search (MCTS) to rodzina algorytmów przeszukiwania, która buduje drzewo decyzyjne w czterech etapach: selekcji, ekspansji, symulacji i propagacji wstecznej. Zamiast wymagać kompletnej funkcji oceny dla każdego stanu, metoda szacuje jakość akcji na podstawie licznych symulacji, równoważąc eksplorację rzadko odwiedzanych alternatyw z eksploatacją znanych akcji. Ta cecha przyczyniła się do znaczących wyników w grach takich jak Go, szachy i shogi, szczególnie w środowiskach dwuosobowych z doskonałą informacją (BROWNE i in., 2012).

Jednak współczesne gry cyfrowe i planszowe przedstawiają bardziej złożone warunki: wielu przeciwników, ukrytą informację, losowość, duże przestrzenie akcji i decyzje w czasie rzeczywistym. W takich sytuacjach jedna dodatkowa symulacja nie zawsze prowadzi do lepszej decyzji. Większa liczba graczy powiększa drzewo przeszukiwania i utrudnia modelowanie odpowiedzi przeciwników. Niedoskonała informacja może powodować fuzję strategii, gdy ukryte stany są obsługiwane nieodpowiednio, a presja czasu zmniejsza dostępny budżet obliczeniowy. Pomimo rosnącego zastosowania MCTS w tych scenariuszach, literatura pozostaje rozdrobniona i skoncentrowana na grach klasycznych.

2. Cele

Ogólnym celem tej pracy było zidentyfikowanie i uporządkowanie powtarzających się ograniczeń MCTS w wieloosobowych grach cyfrowych i planszowych, szczególnie w środowiskach z niedoskonałą informacją, stochastycznością i ograniczeniami czasowymi.

Jako cele szczegółowe praca dążyła do zebrania strategii łagodzących te ograniczenia oraz do zidentyfikowania luk badawczych, które mogą ukierunkować przyszłe badania i sprzyjać bardziej porównywalnym i powtarzalnym ocenom.

3. Metodologia

Przeprowadzono przegląd literatury obejmujący badania opublikowane w latach 2013–2025, z wyszukiwaniami w bazach IEEE Xplore, HAL Science Ouverte i Google Scholar. Strategie wyszukiwania łączyły terminy „Monte Carlo Tree Search” i „MCTS” z wyrażeniami związanymi z grami cyfrowymi, grami planszowymi i grami wieloosobowymi. Przy selekcji uwzględniano prace, których tytuł lub streszczenie dotyczyło MCTS, bezpośredniego wariantu lub metody hybrydowej zastosowanej do gier konkurencyjnych lub kooperacyjnych. Wykluczono badania poza zakresem, dokumenty bez dostępu do pełnego tekstu oraz prace, których zakres nie był zgodny z celami przeglądu.

Wyszukiwania zwróciły 24 rekordy, z których dwa były zduplikowane między zapytaniami, co dało 22 unikalne potencjalnie istotne prace (17 w języku angielskim i pięć w języku francuskim). Po selekcji wybrano 18 badań do pełnej analizy, a cztery wykluczono. Ostateczny korpus zgromadził 13 badań z IEEE Xplore, trzy z HAL i dwa znalezione przez Google Scholar, a wśród wybranych 15 tekstów było w języku angielskim, a trzy w języku francuskim. Prace sklasyfikowano według typu gry, zastosowanego algorytmu, ograniczeń środowiska, raportowanych wyników i strategii łagodzenia. Analizę tematyczną zorganizowano w trzy strukturalne kategorie ograniczeń — limity wydajności, taktyczne martwe punkty i kompromisy w modelowaniu przeciwników — oraz dwa wzmacniacze zależne od domeny: niedoskonałą informację i decyzje w czasie rzeczywistym.

4. Wyniki i dyskusja

Analizowane badania wskazują, że MCTS działa najstabilniej w grach o dobrze zdefiniowanych stanach, umiarkowanym współczynniku rozgałęzienia i budżecie obliczeniowym wystarczająco dużym na dużą liczbę symulacji. Wśród 18 wybranych prac osiem dotyczyło gier cyfrowych, sześć badało gry planszowe lub stołowe, a pozostałe analizowały gry karciane, ogólne środowiska gry lub powiązane zastosowania. Algorytmy oparte na MCTS zastosowano w 14 badaniach, często w połączeniu z sieciami neuronowymi, abstrakcjami przestrzeni akcji, politykami symulacji i technikami dostrajania parametrów.

Pierwsze zidentyfikowane ograniczenie dotyczy wydajności przeszukiwania. Chociaż zwiększenie liczby symulacji zwykle poprawia jakość decyzji, marginalne zyski mają tendencję do zmniejszania się, gdy nowe symulacje zaczynają ponownie odwiedzać trajektorie już wystarczająco zbadane. Wyniki uzyskane w Go, grach strategicznych czasu rzeczywistego i grach stołowych pokazują, że podwojenie budżetu obliczeniowego może przynieść zmniejszone korzyści lub ich brak po pewnym punkcie. Ponadto badania nad głębią umiejętności pokazują, że ten limit zależy zarówno od złożoności gry, jak i konfiguracji agenta. Strategie łagodzenia obejmują abstrakcję przestrzeni akcji, uproszczenie symulacji oraz automatyczne dostrajanie polityk, stałych eksploracji i strategii rolloutów za pomocą algorytmu N-Tuple Bandit Evolutionary Algorithm (NTBEA) (GOODMAN; PEREZ-LIEBANA; LUCAS, 2024).

Drugie ograniczenie odpowiada martwym punktom rozumowania taktycznego. Ponieważ MCTS szacuje średnią wartość próbkowanych kontynuacji, algorytm może zawodzić w pozycjach wymagających rozpoznania konkretnych sekwencji taktycznych, długoterminowych zagrożeń lub rzadkich konfiguracji. W Go sytuacje takie jak drabiny i semeai ilustrują scenariusze, w których struktura taktyczna oczywista dla doświadczonych graczy może nie zostać zidentyfikowana przez przeszukiwanie.

Trzecie ograniczenie dotyczy modelowania przeciwników. W grach z trzema lub więcej uczestnikami proces przeszukiwania musi reprezentować nie tylko decyzje gracza w korzeniu drzewa, ale także możliwe odpowiedzi każdego przeciwnika. Modele utrzymujące niezależne struktury dla każdego przeciwnika mają tendencję do lepszego reprezentowania zachowań strategicznych, choć znacząco zwiększają koszt obliczeniowy. Z kolei uproszczone podejścia, takie jak Paranoid Search i polityki uogólnione, zmniejszają ten koszt, ale mogą nie reprezentować istotnych zachowań. Literatura sugeruje, że podejścia oparte na selektywnym skupieniu, uogólnieniu odpowiedzi przeciwników i dekompozycji drzewa są obiecującymi alternatywami, choć są jeszcze słabo oceniane w grach z dużą liczbą uczestników (BAIER; KAISERS, 2020).

Niedoskonała informacja wzmacnia te ograniczenia. W grach karcianych, Pokémon i innych środowiskach z ukrytymi stanami, determinizacja, polegająca na założeniu jednej możliwej konfiguracji nieznanej informacji i przeszukiwaniu tak, jakby była prawdziwa, może powodować fuzję niekompatybilnych strategii. Information Set MCTS, wariant przeszukiwania drzewa Monte Carlo zaprojektowany do obsługi niepewności, redukuje ten problem, grupując stany, których gracz nie może rozróżnić, zachowując jedynie informacje faktycznie dostępne w momencie decyzji (COWLING; POWLEY; WHITEHOUSE, 2012). Mimo to losowość inherentna w środowisku i potrzeba wnioskowania o zachowaniu przeciwników nadal ograniczają wiarygodność generowanych szacunków.

W środowiskach czasu rzeczywistego, takich jak gry strategiczne, MOBA i strzelanki pierwszoosobowe, ograniczenia czasowe stają się krytycznym czynnikiem. MCTS musi wybierać akcje w bardzo krótkich odstępach czasu, zarządzając kombinatorycznymi przestrzeniami akcji, wieloma jednostkami i częściowymi obserwacjami. W tym kontekście hierarchiczne abstrakcje, makroakcje, przycinanie akcji oraz polityki uzyskane poprzez uczenie nadzorowane lub uczenie ze wzmocnieniem pojawiają się jako powtarzające się strategie (ONTAÑÓN, 2013). W niektórych sytuacjach metody alternatywne mogą działać lepiej. Rolling Horizon Evolutionary Algorithm (RHEA), na przykład, ewoluuje krótkie sekwencje akcji i wykonuje ciągłe replanowanie, okazując się szczególnie odpowiedni dla gier kooperacyjnych i wysoce stochastycznych środowisk, w których drzewo przeszukiwania zmienia się szybko (SFIKAS; LIAPIS, 2022).

Zidentyfikowano również zastosowania MCTS, które w mniejszym stopniu zależą od decyzji w czasie rzeczywistym, takie jak automatyczne balansowanie, testowanie rozgrywki i wsparcie projektowania gier. W tych scenariuszach czas przetwarzania przestaje być krytycznym ograniczeniem, pozwalając na szerokie badanie różnych konfiguracji, identyfikację braku równowagi i ocenę alternatyw projektowych. Chociaż większość badań raportuje wyniki korzystne dla proponowanych podejść, niektóre prace zaobserwowały niższą wydajność MCTS w porównaniu z konkurencyjnymi technikami, jak w grach Kingdomino i Pandemic.

5. Wnioski

Przegląd zidentyfikował również pięć istotnych możliwości przyszłych badań: (i) przyjęcie i standaryzacja wspólnych benchmarków dla gier wieloosobowych z niedoskonałą informacją; (ii) systematyczna ocena technik modelowania przeciwników w grach z większą liczbą uczestników; (iii) zbadanie związku między złożonością postrzeganą przez ludzkich graczy a efektywną głębią przeszukiwania; (iv) badanie serii konkurencyjnych best-of-three i best-of-five, z uwzględnieniem historii wyborów i banów; oraz (v) rozszerzenie zastosowań MCTS w automatycznym balansowaniu, testowaniu rozgrywki i proceduralnym generowaniu treści.