Monte-Carlo-Baumsuche: Eine Übersicht über Nachteile, Vorteile und Einschränkungen in komplexen Mehrspieler-Spielen

1. Einleitung

Monte-Carlo-Baumsuche (MCTS) ist eine Familie von Suchalgorithmen, die in vier Phasen einen Entscheidungsbaum aufbaut: Selektion, Expansion, Simulation und Backpropagation. Anstatt eine vollständige Bewertungsfunktion für jeden Zustand zu erfordern, schätzt die Methode die Qualität von Aktionen aus zahlreichen Simulationen und balanciert die Exploration selten besuchter Alternativen mit der Ausbeutung bekannter Aktionen. Diese Eigenschaft trug zu ausdrucksstarken Ergebnissen in Spielen wie Go, Schach und Shogi bei, insbesondere in Zwei-Spieler-Umgebungen mit perfekter Information (BROWNE et al., 2012).

Allerdings weisen zeitgenössische digitale und Brettspiele komplexere Bedingungen auf: mehrere Gegner, verborgene Informationen, Zufälligkeit, große Aktionsräume und Echtzeitentscheidungen. In diesen Situationen führt eine zusätzliche Simulation nicht immer zu einer besseren Entscheidung. Eine größere Anzahl von Spielern vergrößert den Suchbaum und erschwert die Modellierung der Antworten der Gegner. Unvollkommene Information kann zu Strategieverschmelzung führen, wenn verborgene Zustände unzureichend behandelt werden, während Zeitdruck das verfügbare Rechenbudget reduziert. Trotz der wachsenden Anwendung von MCTS in diesen Szenarien bleibt die Literatur fragmentiert und auf klassische Spiele konzentriert.

2. Ziele

Das allgemeine Ziel dieser Arbeit war es, wiederkehrende Einschränkungen von MCTS in digitalen Mehrspieler- und Brettspielen zu identifizieren und zu ordnen, insbesondere in Umgebungen mit unvollkommener Information, Stochastizität und Zeitbeschränkungen.

Als spezifische Ziele versuchte die Arbeit, die Strategien zu sammeln, die diese Einschränkungen mildern, und Forschungslücken zu identifizieren, die zukünftige Studien anleiten und vergleichbarere und reproduzierbarere Bewertungen begünstigen können.

3. Methodik

Es wurde eine Literaturübersicht über Studien durchgeführt, die zwischen 2013 und 2025 veröffentlicht wurden, mit Suchen in den Datenbanken IEEE Xplore, HAL Science Ouverte und Google Scholar. Die Suchstrategien kombinierten die Begriffe "Monte Carlo Tree Search" und "MCTS" mit Ausdrücken im Zusammenhang mit digitalen Spielen, Brettspielen und Mehrspielerspielen. Beim Screening wurden Arbeiten berücksichtigt, deren Titel oder Zusammenfassung MCTS, eine direkte Variante oder eine hybride Methode behandelte, die auf kompetitive oder kooperative Spiele angewendet wurde. Studien außerhalb des Geltungsbereichs, Dokumente ohne Zugang zum Volltext und Arbeiten, deren Umfang nicht mit den Zielen der Übersicht vereinbar war, wurden ausgeschlossen.

Die Suchen ergaben 24 Datensätze, von denen zwei zwischen Abfragen dupliziert waren, was zu 22 eindeutigen potenziell relevanten Arbeiten führte (17 auf Englisch und fünf auf Französisch). Nach dem Screening wurden 18 Studien für die vollständige Analyse ausgewählt und vier ausgeschlossen. Das endgültige Korpus umfasste 13 Studien aus IEEE Xplore, drei aus HAL und zwei, die über Google Scholar gefunden wurden, und unter den ausgewählten waren 15 Texte auf Englisch und drei auf Französisch. Die Arbeiten wurden nach Spieltyp, verwendetem Algorithmus, Umgebungsbeschränkungen, berichteten Ergebnissen und Milderungsstrategien klassifiziert. Die thematische Analyse wurde in drei strukturelle Kategorien von Einschränkungen organisiert – Leistungsgrenzen, taktische blinde Flecken und Kompromisse bei der Gegnermodellierung – sowie in zwei domänenabhängige Verstärker: unvollkommene Information und Echtzeitentscheidungen.

4. Ergebnisse und Diskussion

Die analysierten Studien deuten darauf hin, dass MCTS in Spielen mit wohldefinierten Zuständen, einem moderaten Verzweigungsfaktor und einem ausreichend großen Rechenbudget für eine hohe Anzahl von Simulationen am konsistentesten abschneidet. Von den 18 ausgewählten Arbeiten befassten sich acht mit digitalen Spielen, sechs untersuchten Brett- oder Tischspiele und die übrigen analysierten Kartenspiele, allgemeine Spielumgebungen oder verwandte Anwendungen. MCTS-basierte Algorithmen wurden in 14 Studien verwendet, oft kombiniert mit neuronalen Netzen, Abstraktionen des Aktionsraums, Simulationsrichtlinien und Techniken zur Parameterabstimmung.

Die erste identifizierte Einschränkung betrifft die Suchleistung. Obwohl eine Erhöhung der Anzahl von Simulationen normalerweise die Entscheidungsqualität verbessert, nehmen die marginalen Gewinne tendenziell ab, wenn neue Simulationen beginnen, bereits ausreichend erkundete Trajektorien erneut zu besuchen. Ergebnisse aus Go, Echtzeit-Strategiespielen und Tischspielen zeigen, dass eine Verdopplung des Rechenbudgets nach einem bestimmten Punkt reduzierte oder keine Vorteile bringen kann. Darüber hinaus zeigen Studien zur Fähigkeitstiefe, dass diese Grenze sowohl von der Komplexität des Spiels als auch von der Konfiguration des Agenten abhängt. Milderungsstrategien umfassen die Abstraktion des Aktionsraums, die Vereinfachung von Simulationen und die automatische Abstimmung von Richtlinien, Explorationskonstanten und Rollout-Strategien durch den N-Tuple Bandit Evolutionary Algorithm (NTBEA) (GOODMAN; PEREZ-LIEBANA; LUCAS, 2024).

Die zweite Einschränkung entspricht den blinden Flecken des taktischen Denkens. Da MCTS den Durchschnittswert der abgetasteten Fortsetzungen schätzt, kann der Algorithmus in Positionen versagen, die das Erkennen spezifischer taktischer Sequenzen, langfristiger Drohungen oder seltener Konfigurationen erfordern. In Go veranschaulichen Situationen wie Leitern und Semeai Szenarien, in denen eine taktische Struktur, die für erfahrene Spieler offensichtlich ist, von der Suche möglicherweise nicht identifiziert wird.

Die dritte Einschränkung betrifft die Gegnermodellierung. In Spielen mit drei oder mehr Teilnehmern muss der Suchprozess nicht nur die Entscheidungen des Spielers an der Wurzel des Baums darstellen, sondern auch die möglichen Antworten jedes Gegners. Modelle, die unabhängige Strukturen für jeden Gegner beibehalten, neigen dazu, strategisches Verhalten besser darzustellen, obwohl sie die Rechenkosten erheblich erhöhen. Im Gegensatz dazu reduzieren vereinfachte Ansätze wie Paranoid Search und generalisierte Richtlinien diese Kosten, können jedoch relevante Verhaltensweisen nicht darstellen. Die Literatur legt nahe, dass Ansätze, die auf selektivem Fokus, Generalisierung der Antworten der Gegner und Baumzerlegung basieren, vielversprechende Alternativen sind, obwohl sie in Spielen mit einer großen Anzahl von Teilnehmern noch wenig evaluiert sind (BAIER; KAISERS, 2020).

Unvollkommene Information verstärkt diese Einschränkungen. In Kartenspielen, Pokémon und anderen Umgebungen mit verborgenen Zuständen kann die Determinierung, die darin besteht, eine mögliche Konfiguration der unbekannten Information anzunehmen und zu suchen, als ob sie wahr wäre, die Verschmelzung inkompatibler Strategien verursachen. Information Set MCTS, eine Variation der Monte-Carlo-Baumsuche, die entwickelt wurde, um mit Unsicherheit umzugehen, reduziert dieses Problem, indem sie Zustände gruppiert, die der Spieler nicht unterscheiden kann, und nur die Informationen bewahrt, die zum Zeitpunkt der Entscheidung tatsächlich verfügbar sind (COWLING; POWLEY; WHITEHOUSE, 2012). Dennoch schränken die der Umgebung inhärente Zufälligkeit und die Notwendigkeit, das Verhalten der Gegner abzuleiten, weiterhin die Zuverlässigkeit der erzeugten Schätzungen ein.

In Echtzeitumgebungen wie Strategiespielen, MOBAs und Ego-Shootern werden Zeitbeschränkungen zu einem kritischen Faktor. MCTS muss Aktionen in sehr kurzen Intervallen auswählen, während es kombinatorische Aktionsräume, mehrere Einheiten und teilweise Beobachtungen verwaltet. In diesem Kontext erscheinen hierarchische Abstraktionen, Makro-Aktionen, Aktionsbeschneidung und Richtlinien, die durch überwachtes Lernen oder Verstärkungslernen gewonnen werden, als wiederkehrende Strategien (ONTAÑÓN, 2013). In einigen Situationen können alternative Methoden besser abschneiden. Der Rolling Horizon Evolutionary Algorithm (RHEA) beispielsweise entwickelt kurze Aktionssequenzen und führt eine kontinuierliche Neuplanung durch, was sich als besonders geeignet für kooperative Spiele und hochstochastische Umgebungen erweist, in denen sich der Suchbaum schnell ändert (SFIKAS; LIAPIS, 2022).

Es wurden auch Anwendungen von MCTS identifiziert, die weniger von Echtzeitentscheidungen abhängen, wie automatische Balance, Playtesting und Unterstützung für Spieldesign. In diesen Szenarien ist die Verarbeitungszeit keine kritische Einschränkung mehr, sodass verschiedene Konfigurationen umfassend erkundet, Ungleichgewichte identifiziert und Designalternativen bewertet werden können. Obwohl die meisten Studien Ergebnisse berichten, die für die vorgeschlagenen Ansätze günstig sind, beobachteten einige Arbeiten eine geringere Leistung von MCTS im Vergleich zu konkurrierenden Techniken, wie in den Spielen Kingdomino und Pandemic.

5. Schlussfolgerung

Die Übersicht identifizierte auch fünf relevante Möglichkeiten für zukünftige Forschung: (i) Annahme und Standardisierung gemeinsamer Benchmarks für Mehrspielerspiele mit unvollkommener Information; (ii) systematische Bewertung von Techniken zur Gegnermodellierung in Spielen mit einer größeren Anzahl von Teilnehmern; (iii) Untersuchung der Beziehung zwischen der von menschlichen Spielern wahrgenommenen Komplexität und der effektiven Suchtiefe; (iv) Untersuchung von Best-of-Three- und Best-of-Five-Wettkampfserien unter Berücksichtigung der Geschichte von Picks und Bans; und (v) Ausweitung der MCTS-Anwendungen auf automatische Balance, Playtesting und prozedurale Inhaltsgenerierung.