Modelowanie Przeciwników do Trenowania Modeli Opartych na Przeszukiwaniu Drzewa Monte Carlo w Grze Planszowej Citadels

1. Wprowadzenie

Monte Carlo Tree Search (MCTS) umocnił się jako skuteczna technika podejmowania decyzji w grach planszowych, łącząc adaptacyjność i niskie wykorzystanie wiedzy dziedzinowej. Jej wydajność jest zauważalna w deterministycznych grach z pełną informacją, takich jak Go (SILVER et al., 2016).

Jednak jej zastosowanie napotyka znaczące ograniczenia w środowiskach z wieloma graczami, ukrytymi informacjami i ograniczeniami czasowymi, gdzie wysoki koszt obliczeniowy symulacji i trudność adaptacji wpływają na responsywność i jakość decyzji (POWLEY et al., 2014).

W tym kontekście hybrydowe podejścia integrujące MCTS i uczenie przez wzmacnianie (RL) okazują się obiecujące, umożliwiając oddzielenie fazy planowania od wykonania. Budowa trwałych struktur decyzyjnych, z wcześniejszym przechowywaniem przeszukiwania, pozwala na natychmiastowy wybór akcji podczas gry, redukując potrzebę symulacji online i zachowując głębię strategiczną (BROWNE, 2012; SWIECHOWSKI, 2023).

W tych badaniach przetestowano i opracowano hybrydowy model MCTS z technikami uczenia przez wzmacnianie offline. Model został wytrenowany i przetestowany przy użyciu różnych przeciwników w środowisku symulacyjnym gry planszowej Citadels (FAIDUTTI, 2016).

2. Cel ogólny

Ogólnym celem tych badań jest opracowanie hybrydowej struktury MCTS-RL zdolnej do efektywnego działania w wieloosobowych grach planszowych z ukrytymi informacjami, wykorzystując Citadels jako studium przypadku.

Propozycja ma na celu wyeliminowanie wąskich gardeł obliczeniowych tradycyjnego MCTS poprzez offline'ową konstrukcję trwałej struktury decyzyjnej, umożliwiającej szybkie i solidne działania w czasie rzeczywistym.

3. Metodologia

Badanie to jest klasyfikowane jako eksperymentalne studium stosowane z analizą jakościowo-ilościową.

Pierwszy etap obejmował opracowanie i adaptację cyfrowego środowiska symulacyjnego dla gry planszowej Citadels. Następnie opracowano pięciu agentów eksperckich z dostosowanymi strategiami, zbudowanymi tak, aby naśladować rzeczywiste strategie stosowane przez ludzkich graczy, oraz agenta bazowego, który wybiera działania losowo. Po walidacji środowiska i opracowanych agentów rozpoczęto prace nad hybrydowym frameworkiem MCTS-RL.

Model MCTS jest w swej istocie heurystycznym algorytmem wyszukiwania, który działa poprzez wykonanie wielu symulacji. Dla każdego odrębnego stanu gry odwiedzonego podczas tych symulacji tworzony jest odpowiedni węzeł w strukturze danych drzewa. Początkowy stan gry reprezentuje węzeł główny tego drzewa.

Jednak propozycja przechowywania całego drzewa i zachowania go na potrzeby przyszłych decyzji jest niewykonalna ze względu na ogromny współczynnik rozgałęzienia. Aby to umożliwić, konieczne jest abstrahowanie drzewa: stan gry dzieli się na podstawowe cechy (np. złoto gracza, liczba kart w ręce), a każda cecha jest mapowana na niezależną tabelę danych.

W tej strukturze wiersze tabeli reprezentują możliwe wartości cechy stanu, a kolumny reprezentują możliwe działania, które agent może podjąć (np. zdobycie złota, dobranie kart). W każdej komórce przechowywane są dwie wartości: liczba zwycięstw (n) osiągniętych po wykonaniu tego działania w tym stanie oraz całkowita liczba razy, gdy ta kombinacja była badana (m). Tabele te, wypełniane podczas symulacji meczów Citadels, konfigurują wyuczony model agenta.

Proces uczenia obejmuje komponent uczenia przez wzmacnianie: po każdej symulowanej rozgrywce wyniki aktualizują tabele decyzyjne, wpływając na przyszłe wybory. Zwycięstwa działają jako nagrody i wzmacniają skuteczne działania, zwiększając prawdopodobieństwo ich ponownego wyboru, podczas gdy porażki zmniejszają tę możliwość. W ten sposób, po wielu symulacjach, model dostosowuje się w sposób ciągły, równoważąc eksplorację nowych alternatyw i eksploatację sprawdzonych strategii, stopniowo zbiegając się do bardziej efektywnych zachowań.

4. Wyniki i dyskusja

Aby ocenić wydajność proponowanego modelu MCTS, kluczowe było zrozumienie dynamiki sił między strategiami bazowymi (agenci eksperci i agent losowy). W tym celu każda z nich została poddana rundzie 10 000 meczów przeciwko czterem identycznym przeciwnikom.

Mapa ciepła przedstawiona na Rysunku 1 ilustruje wydajność każdej strategii (oś Y) przeciwko różnym przeciwnikom (oś X). Strategie posiadają wyraźne mocne i słabe strony: Eksperci 1, 2 i 3 okazują się kompetentni w większości scenariuszy, podczas gdy Eksperci 4 i 5 są znacznie mniej skuteczni. Zgodnie z oczekiwaniami, całkowicie losowa strategia wykazuje bardzo niską wydajność przeciwko każdemu minimalnie zorganizowanemu przeciwnikowi.

Rysunek 1: Porównanie strategii.

Następnym krokiem była ocena modelu MCTS-RL. Przeprowadzono różne sesje treningowe, każda skupiająca się na jednym z przeciwników, łącznie 100 000 meczów treningowych dla każdej wersji modelu. Następnie zmierzono wydajność każdego wytrenowanego modelu przeciwko wszystkim typom przeciwników, stosując ten sam poprzedni model testowania, oraz przeciwko losowo wybranym zróżnicowanym przeciwnikom.

Mapa cieplna pokazana na Rysunku 2 przedstawia skonsolidowany wskaźnik wygranych każdego modelu. Najbardziej znaczącym wynikiem był ten modelu wytrenowanego w zróżnicowanym środowisku, który osiągnął spójną wydajność, przewyższając inne wersje modelu w prawie wszystkich scenariuszach testowych. Sugeruje to, że ekspozycja na różnorodność strategii podczas treningu była kluczowa dla rozwinięcia bardziej solidnej i ogólnej zdolności gry.

Rysunek 2: Porównanie wytrenowanych modeli.

Modele trenowane przeciwko Ekspertom 4 i 5, uważanym za najsłabszych przeciwników, stały się zaskakująco skutecznymi agentami. Z kolei trenowanie przeciwko Ekspertom 1 i 3, uważanym za silnych przeciwników, dało modele o bardzo słabej ogólnej wydajności.

Możliwym wyjaśnieniem tego kontrastu jest to, że zaawansowane strategie ekspertów są zwykle wysoce wyspecjalizowane, podczas gdy model MCTS-RL na początku treningu zachowuje się losowo. Przeciwko silnym przeciwnikom nawet potencjalnie korzystne działania mogą nie przynieść wystarczającej liczby zwycięstw, aby model rozpoznał wzorce sukcesu; natomiast przeciwko mniej wyspecjalizowanym przeciwnikom zwycięstwa zdarzają się częściej, co sprzyja uczeniu się. Mimo to pozostaje to hipotezą wymagającą potwierdzenia.

5. Wnioski

To badanie wykazało wykonalność proponowanego podejścia, które wykorzystuje abstrakcję drzewa MCTS do zachowania zdobytej wiedzy między ruchami. Wyniki potwierdziły, że model jest w stanie opracować solidne strategie dla środowiska.

Lepsze wyniki agenta wyszkolonego w zróżnicowanym środowisku pokazują, że ekspozycja na wiele taktyk jest kluczowa dla budowy modelu ogólnego. Ponadto badania wskazują, że jakość końcowego agenta zależy bardziej od różnorodności niż od pozornej siły przeciwników treningowych.

W przyszłych badaniach interesujące byłoby dokładniejsze zbadanie rzeczywistych powodów, dla których mniej wyspecjalizowane strategie prowadziły do bardziej wydajnych modeli niż silniejsze strategie. Ponadto porównanie proponowanego modelu z innymi modelami MCTS pomogłoby uzyskać dokładniejszą ocenę podejścia.