Tegenstander Modellering voor het Trainen van Monte Carlo Tree Search-Gebaseerde Modellen in het Bordspel Citadels

1. Inleiding

Monte Carlo Tree Search (MCTS) heeft zich gevestigd als een effectieve techniek voor besluitvorming in bordspellen, waarbij aanpassingsvermogen en laag gebruik van domeinspecifieke kennis worden gecombineerd. De prestaties zijn opmerkelijk in deterministische spellen met perfecte informatie, zoals Go (SILVER et al., 2016).

De toepassing ervan ondervindt echter aanzienlijke beperkingen in omgevingen met meerdere spelers, verborgen informatie en tijdsbeperkingen, waar de hoge rekenkosten van simulaties en de moeilijkheid van aanpassing de responsiviteit en kwaliteit van beslissingen in gevaar brengen (POWLEY et al., 2014).

In deze context hebben hybride benaderingen die MCTS en Reinforcement Learning (RL) integreren veelbelovend getoond door de planningsfase los te koppelen van de uitvoering. De constructie van persistente beslissingsstructuren, met voorafgaande opslag van de zoekopdracht, maakt de onmiddellijke selectie van acties tijdens het spel mogelijk, waardoor de behoefte aan online simulaties wordt verminderd en de strategische diepgang behouden blijft (BROWNE, 2012; SWIECHOWSKI, 2023).

In dit onderzoek werd een hybride MCTS-model met offline reinforcement learning-technieken getest en ontwikkeld. Het model werd getraind en getest met verschillende tegenstanders in een simulatieomgeving van het bordspel Citadels (FAIDUTTI, 2016).

2. Algemene doelstelling

Het algemene doel van dit onderzoek is het ontwikkelen van een hybride MCTS-RL-framework dat efficiënt kan werken in multiplayer bordspellen met verborgen informatie, met Citadels als casestudy.

Het voorstel streeft ernaar computationele knelpunten van traditionele MCTS te elimineren door de offline constructie van een persistente beslissingsstructuur, waardoor snelle en robuuste acties tijdens runtime mogelijk zijn.

3. Methodologie

Dit onderzoek wordt gekarakteriseerd als een toegepaste experimentele studie met kwalitatief-kwantitatieve analyse.

De eerste fase omvatte de ontwikkeling en aanpassing van een digitale simulatieomgeving voor het bordspel Citadels. Dit werd gevolgd door de ontwikkeling van vijf expertagenten met op maat gemaakte strategieën, gebouwd om echte strategieën van menselijke spelers na te bootsen, en de ontwikkeling van een basisagent die willekeurig acties kiest. Na de validatie van de omgeving en de ontwikkelde agenten begon de ontwikkeling van het hybride MCTS-RL-framework.

Het MCTS-model is in essentie een heuristisch zoekalgoritme dat werkt door het uitvoeren van meerdere simulaties. Voor elke afzonderlijke speltoestand die tijdens deze simulaties wordt bezocht, wordt een overeenkomstig knooppunt gemaakt in een boomdatastructuur. De initiële speltoestand vertegenwoordigt het wortelknooppunt van deze boom.

Het voorstel om de volledige boom op te slaan en te bewaren voor toekomstige beslissingen is echter onhaalbaar vanwege de enorme vertakkingsfactor. Om dit mogelijk te maken, is het noodzakelijk om de boom te abstraheren: de speltoestand wordt verdeeld in zijn fundamentele kenmerken (bijv. goud van de speler, aantal kaarten in de hand) en elk kenmerk wordt toegewezen aan een onafhankelijke gegevenstabel.

In deze structuur vertegenwoordigen de rijen van een tabel de mogelijke waarden van een toestandskenmerk, en de kolommen vertegenwoordigen de mogelijke acties die de agent kan ondernemen (bijv. goud verdienen, kaarten trekken). In elke cel worden twee waarden opgeslagen: het aantal behaalde overwinningen (n) na het uitvoeren van die actie in die toestand, en het totale aantal keren dat deze combinatie is verkend (m). Deze tabellen, gevuld door simulaties van Citadels-wedstrijden, vormen het geleerde model van de agent.

Het trainingsproces omvat een component van reinforcement learning: na elke gesimuleerde wedstrijd werken de resultaten de beslissingstabellen bij, wat toekomstige keuzes beïnvloedt. Overwinningen fungeren als beloningen en versterken effectieve acties, waardoor de kans dat ze opnieuw worden gekozen toeneemt, terwijl nederlagen deze mogelijkheid verminderen. Zo past het model zich na vele simulaties continu aan, waarbij het de verkenning van nieuwe alternatieven en de exploitatie van bewezen strategieën in evenwicht houdt, en geleidelijk convergeert naar effectiever gedrag.

4. Resultaten en Discussie

Om de prestaties van het voorgestelde MCTS-model te evalueren, was het cruciaal om de machtsdynamiek tussen de basisstrategieën (expertagenten en willekeurige agent) te begrijpen. Om dit te bereiken, werd elk onderworpen aan een ronde van 10.000 wedstrijden tegen vier identieke tegenstanders.

De heatmap in Figuur 1 illustreert de prestaties van elke strategie (Y-as) tegen de verschillende tegenstanders (X-as). De strategieën hebben duidelijke sterke en zwakke punten: Experts 1, 2 en 3 blijken competent in de meeste scenario's, terwijl Experts 4 en 5 aanzienlijk minder effectief zijn. Zoals verwacht vertoont de volledig willekeurige strategie zeer lage prestaties tegen elke minimaal gestructureerde tegenstander.

Figuur 1: Vergelijking tussen strategieën.

De volgende stap was het evalueren van het MCTS-RL-model. Er werden verschillende trainingssessies uitgevoerd, elk gericht op een van de tegenstanders, met in totaal 100.000 trainingswedstrijden voor elke versie van het model. Vervolgens werd de prestatie van elk getraind model gemeten tegen alle typen tegenstanders volgens hetzelfde eerdere testmodel, en tegen willekeurig getrokken gevarieerde tegenstanders.

De heatmap in Figuur 2 toont het geconsolideerde winstpercentage van elk model. Het meest significante resultaat was dat van het model dat in de gevarieerde omgeving was getraind, dat consistente prestaties leverde en de andere versies van het model in bijna alle testscenario's overtrof. Dit suggereert dat blootstelling aan een diversiteit aan strategieën tijdens de training fundamenteel was voor het ontwikkelen van een robuustere en meer generalistische speelcapaciteit.

Figuur 2: Vergelijking tussen getrainde modellen.

De modellen die getraind zijn tegen Experts 4 en 5, beschouwd als de zwakste tegenstanders, werden verrassend effectieve agenten. Omgekeerd leverde training tegen Experts 1 en 3, beschouwd als sterke tegenstanders, modellen op met zeer slechte algehele prestaties.

Een mogelijke verklaring voor dit contrast is dat geavanceerde expertstrategieën de neiging hebben zeer gespecialiseerd te zijn, terwijl het MCTS-RL-model aan het begin van de training willekeurig gedrag vertoont. Tegen sterke tegenstanders kunnen zelfs potentieel voordelige acties niet leiden tot voldoende overwinningen voor het model om succespatronen te herkennen; terwijl tegen minder gespecialiseerde tegenstanders overwinningen vaker voorkomen, wat leren bevordert. Dit blijft echter een hypothese die bevestiging behoeft.

5. Conclusie

Deze studie toonde de levensvatbaarheid aan van de voorgestelde aanpak, die een abstractie van de MCTS-boom gebruikt om de verworven kennis tussen zetten te behouden. De resultaten bevestigden dat het model in staat is robuuste strategieën voor de omgeving te ontwikkelen.

De superieure prestaties van de agent die is getraind in de gevarieerde omgeving tonen aan dat blootstelling aan meerdere tactieken fundamenteel is voor het bouwen van een generalistisch model. Bovendien geeft het onderzoek aan dat de kwaliteit van de uiteindelijke agent meer afhangt van de diversiteit dan van de schijnbare sterkte van de trainings-tegenstanders.

Als toekomstige studies zou het interessant zijn om preciezer te onderzoeken wat de werkelijke redenen zijn waarom minder gespecialiseerde strategieën resulteerden in efficiëntere modellen dan sterkere strategieën. Verder zou een vergelijking van het voorgestelde model met andere MCTS-modellen ook helpen om een nauwkeurigere beoordeling van de aanpak te verkrijgen.