Gegnermodellierung für das Training Monte-Carlo-Baumsuche-basierter Modelle im Brettspiel Citadels

1. Einleitung

Monte-Carlo-Baumsuche (MCTS) hat sich als effektive Technik für die Entscheidungsfindung in Brettspielen etabliert, die Anpassungsfähigkeit mit geringem Einsatz von domänenspezifischem Wissen kombiniert. Ihre Leistung ist bemerkenswert in deterministischen Spielen mit perfekter Information, wie Go (SILVER et al., 2016).

Allerdings stößt ihre Anwendung in Umgebungen mit mehreren Spielern, versteckten Informationen und Zeitbeschränkungen auf erhebliche Einschränkungen, wo die hohen Rechenkosten von Simulationen und die Schwierigkeit der Anpassung die Reaktionsfähigkeit und Qualität der Entscheidungen beeinträchtigen (POWLEY et al., 2014).

In diesem Kontext haben sich hybride Ansätze, die MCTS und Reinforcement Learning (RL) integrieren, als vielversprechend erwiesen, indem sie die Planungsphase von der Ausführung entkoppeln. Die Konstruktion persistenter Entscheidungsstrukturen mit vorheriger Speicherung der Suche ermöglicht die sofortige Auswahl von Aktionen während des Spiels, reduziert den Bedarf an Online-Simulationen und bewahrt die strategische Tiefe (BROWNE, 2012; SWIECHOWSKI, 2023).

In dieser Forschung wurde ein hybrides MCTS-Modell mit Offline-Verstärkungslernverfahren getestet und entwickelt. Das Modell wurde mit verschiedenen Gegnern in einer Simulationsumgebung des Brettspiels Citadels (FAIDUTTI, 2016) trainiert und getestet.

2. Allgemeines Ziel

Das allgemeine Ziel dieser Forschung ist die Entwicklung eines hybriden MCTS-RL-Frameworks, das in der Lage ist, effizient in Multiplayer-Brettspielen mit versteckten Informationen zu arbeiten, wobei Citadels als Fallstudie dient.

Der Vorschlag zielt darauf ab, rechnerische Engpässe des traditionellen MCTS durch den Offline-Aufbau einer persistenten Entscheidungsstruktur zu beseitigen, die schnelle und robuste Aktionen zur Laufzeit ermöglicht.

3. Methodik

Diese Forschung wird als angewandte experimentelle Studie mit qualitativ-quantitativer Analyse charakterisiert.

Die erste Phase umfasste die Entwicklung und Anpassung einer digitalen Simulationsumgebung für das Brettspiel Citadels. Darauf folgte die Entwicklung von fünf Expert-Agenten mit maßgeschneiderten Strategien, die reale Strategien menschlicher Spieler nachahmen, sowie die Entwicklung eines Basis-Agenten, der Aktionen zufällig auswählt. Nach der Validierung der Umgebung und der entwickelten Agenten begann die Entwicklung des hybriden MCTS-RL-Frameworks.

Das MCTS-Modell ist im Wesentlichen ein heuristischer Suchalgorithmus, der durch die Ausführung mehrerer Simulationen arbeitet. Für jeden unterschiedlichen Spielzustand, der während dieser Simulationen besucht wird, wird ein entsprechender Knoten in einer Baumdatenstruktur erstellt. Der anfängliche Spielzustand repräsentiert den Wurzelknoten dieses Baums.

Allerdings ist der Vorschlag, den gesamten Baum zu speichern und für zukünftige Entscheidungen zu erhalten, aufgrund des massiven Verzweigungsfaktors undurchführbar. Um dies zu ermöglichen, ist es notwendig, den Baum zu abstrahieren: Der Spielzustand wird in seine grundlegenden Merkmale unterteilt (z. B. Gold des Spielers, Anzahl der Karten auf der Hand) und jedes Merkmal wird einer unabhängigen Datentabelle zugeordnet.

In dieser Struktur repräsentieren die Zeilen einer Tabelle die möglichen Werte eines Zustandsmerkmals, und die Spalten repräsentieren die möglichen Aktionen, die der Agent ausführen kann (z. B. Gold erhalten, Karten ziehen). In jeder Zelle werden zwei Werte gespeichert: die Anzahl der errungenen Siege (n) nach Ausführung dieser Aktion in diesem Zustand und die Gesamtzahl der Male, die diese Kombination erkundet wurde (m). Diese Tabellen, die durch Simulationen von Citadels-Spielen befüllt werden, konfigurieren das gelernte Modell des Agenten.

Der Trainingsprozess umfasst eine Komponente des bestärkenden Lernens: Nach jedem simulierten Spiel aktualisieren die Ergebnisse die Entscheidungstabellen und beeinflussen zukünftige Entscheidungen. Siege wirken als Belohnungen und verstärken effektive Aktionen, wodurch deren Wahrscheinlichkeit, erneut gewählt zu werden, steigt, während Niederlagen diese Möglichkeit verringern. So passt sich das Modell über viele Simulationen hinweg kontinuierlich an, balanciert die Erkundung neuer Alternativen und die Nutzung bewährter Strategien aus und konvergiert allmählich zu effektiveren Verhaltensweisen.

4. Ergebnisse und Diskussion

Um die Leistung des vorgeschlagenen MCTS-Modells zu bewerten, war es entscheidend, die Machtdynamik zwischen den Basisstrategien (Expertenagenten und Zufallsagent) zu verstehen. Um dies zu erreichen, wurde jede Strategie einer Runde von 10.000 Spielen gegen vier identische Gegner ausgesetzt.

Die in Abbildung 1 dargestellte Heatmap veranschaulicht die Leistung jeder Strategie (Y-Achse) gegen die verschiedenen Gegner (X-Achse). Die Strategien haben unterschiedliche Stärken und Schwächen: Experten 1, 2 und 3 erweisen sich in den meisten Szenarien als kompetent, während Experten 4 und 5 deutlich weniger effektiv sind. Wie erwartet zeigt die völlig zufällige Strategie eine sehr geringe Leistung gegen jeden minimal strukturierten Gegner.

Abbildung 1: Vergleich zwischen Strategien.

Der nächste Schritt bestand darin, das MCTS-RL-Modell zu evaluieren. Es wurden verschiedene Trainingssitzungen durchgeführt, die sich jeweils auf einen der Gegner konzentrierten, insgesamt 100.000 Trainingsspiele für jede Version des Modells. Anschließend wurde die Leistung jedes trainierten Modells gegen alle Arten von Gegnern gemessen, wobei das gleiche vorherige Testmodell verwendet wurde, sowie gegen zufällig ausgewählte verschiedene Gegner.

Die in Abbildung 2 gezeigte Heatmap zeigt die konsolidierte Gewinnrate jedes Modells. Das bedeutendste Ergebnis war das des in der variierten Umgebung trainierten Modells, das eine konstante Leistung erzielte und die anderen Versionen des Modells in fast allen Testszenarien übertraf. Dies deutet darauf hin, dass die Exposition gegenüber einer Vielfalt von Strategien während des Trainings grundlegend für die Entwicklung einer robusteren und generalistischeren Spielfähigkeit war.

Abbildung 2: Vergleich zwischen trainierten Modellen.

Die Modelle, die gegen die Experten 4 und 5 trainiert wurden, die als die schwächsten Gegner galten, wurden überraschend effektive Agenten. Umgekehrt führte das Training gegen die Experten 1 und 3, die als starke Gegner galten, zu Modellen mit sehr schlechter Gesamtleistung.

Eine mögliche Erklärung für diesen Kontrast ist, dass fortgeschrittene Expertenstrategien tendenziell hochspezialisiert sind, während sich das MCTS-RL-Modell zu Beginn des Trainings zufälligem Verhalten annähert. Gegen starke Gegner können selbst potenziell vorteilhafte Aktionen möglicherweise nicht zu genügend Siegen führen, damit das Model Erfolgsmuster erkennt; während gegen weniger spezialisierte Gegner Siege häufiger auftreten, was das Lernen begünstigt. Dennoch bleibt dies eine Hypothese, die bestätigt werden muss.

5. Fazit

Diese Studie zeigte die Machbarkeit des vorgeschlagenen Ansatzes, der eine Abstraktion des MCTS-Baums verwendet, um das erworbene Wissen zwischen den Zügen zu bewahren. Die Ergebnisse bestätigten, dass das Model in der Lage ist, robuste Strategien für die Umgebung zu entwickeln.

Die überlegene Leistung des in der abwechslungsreichen Umgebung trainierten Agenten zeigt, dass die Exposition gegenüber mehreren Taktiken grundlegend für den Aufbau eines Generalistenmodells ist. Zusätzlich deutet die Forschung darauf hin, dass die Qualität des endgültigen Agenten mehr von der Vielfalt als von der scheinbaren Stärke der Trainingsgegner abhängt.

Für zukünftige Studien wäre es interessant, die tatsächlichen Gründe genauer zu untersuchen, warum weniger spezialisierte Strategien zu effizienteren Modellen führten als stärkere Strategien. Darüber hinaus würde ein Vergleich des vorgeschlagenen Modells mit anderen MCTS-Modellen auch helfen, eine genauere Bewertung des Ansatzes zu erhalten.