¶ Einleitung und Motivation
Siedler von Catan ist eines der weltweit erfolgreichsten Brettspiele und stellt aufgrund seiner Komplexität ein faszinierendes Feld für die Forschung in der Lösung von Spielen mit Algorithmen dar [2]. Während klassische Spiele wie Schach oder Go durch "perfekte Information" gekennzeichnet sind, führt Catan Elemente ein, die weit über rein kombinatorische Berechnungen hinausgehen.
¶ Motivation der algorithmischen Analyse
Die Herausforderung, Catan algorithmisch zu lösen, liegt in der Kombination dreier Schwierigkeiten:
- Stochastik: Der Spielverlauf wird massiv durch Würfelergebnisse beeinflusst.
- Unvollständige Information: Algorithmen müssen damit umgehen, dass die Entwicklungskarten der Gegner unbekannt sind.
- Soziale Dynamik: Der Handel zwischen den Spielern erfordert eine Bewertung von Ressourcen, welche über den rein mathematischen Wert hinausgeht.
Das Ziel der hier betrachteten Ansätze ist es, den Monte Carlo Tree Search (MCTS) Algorithmus so zu optimieren, dass er trotz des enormen Suchraums und der Zufallselemente strategisch fundierte Entscheidungen trifft.
¶ Spielregeln und Zielsetzung
Um die algorithmischen Herausforderungen zu verstehen, muss zunächst das Spielprinzip und die Spielregeln verstanden werden.
¶ Grundlegende Spielregeln
Das Spiel findet auf einer Insel statt, die aus 19 hexagonalen Landschaftsfeldern besteht. Jedes Landschaftsfeld produziert ein bestimmten Rohstoff abgesehen von der Wüste.
- der Wald produziert Holz
- das Hügelland produziert Lehm
- das Weideland produziert Wolle
- das Ackerland produziert Getreide
- das Gebirge produziert Erz
¶ Spielzug eines Spielers
Ein Spielzug eines Spielers besteht aus drei Phasen:
-
Rohstoffertrag: Es wird mit zwei Würfeln gewürfelt. Jeder Spieler, der eine Siedlung bzw. Stadt an einem angrenzenden Feld mit der gewürfelten Zahl besitzt, erhält einmal bzw. zweimal (bei einer Stadt) den entsprechenden Rohstoff.
-
Handeln: Der aktive Spieler kann Rohstoffe mit der Bank (4:1), an Häfen (3:1 oder 2:1) oder mit seinen Mitspielern tauschen.
-
Bauen: Rohstoffe können ausgegeben werden, um die Infrastruktur zu erweitern:
* Straßen: Ermöglichen die Expansion zu neuen Bauplätzen.- Siedlungen: Generieren Rohstoffe und werden als 1 Siegpunkt gewertet.
- Städte: Verdoppeln den Rohstoffertrag einer Siedlung und werden als 2 Siegpunkte gewertet.
- Entwicklungskarten: Bieten Spezialfähigkeiten oder versteckte Siegpunkte.
Hinweis zum Räuber: Wird eine 7 gewürfelt, erhält niemand Rohstoffe. Der Räuber wird versetzt, blockiert ein Feld und Spieler mit mehr als 7 Handkarten müssen die Hälfte abgeben. Zudem darf der Spieler, der die 7 gewürfelt hat, bei einem Spieler eine Karte ziehen, welcher nun von dem Räuber blockiert wird.
¶ Spielziel
Das Ziel jedes Spielers in Siedler von Catan ist es als erster 10 Siegpunkte zu erreichen. Diese Punkte können durch den Bau von Strukturen wie Siedlungen und Städte, durch Entwicklungskarten oder durch bestimmte Erfolge wie die längste Handelsstraße erreicht werden.
¶ Adaption von MCTS in Siedler von Catan
Wie bereits erwähnt, stellt die Anwendung von Monte Carlo Tree Search (MCTS) auf Siedler von Catan algorithmisch eine signifikante Herausforderung dar.
Die Forschung von Guimarães et al. [1] zeigt, dass die Standard-Variante von UCT aufgrund des extrem hohen Branching Faktors nicht in der Lage ist, den Suchraum in akzeptabler Zeit tief genug zu explorieren. Ein weiteres Problem ist das "Rauschen" in den Simulationsergebnissen: Zufällige Simulationen (Random Playouts) enden bei Catan fast nie in einem realistischen Sieg, da koordinierte Aktionen - wie das Ansparen auf eine Siedlung oder Stadt - durch reinen Zufall statistisch unwahrscheinlich ist.
Um dieses Problem anzugehen, wird der Algorithmus durch domänenspezifisches Wissen in Form von Heuristiken erweitert.
¶ Move-Heuristik
Der bedeutendste Eingriff erfolgt in der Simulations-Phase des MCTS. Anstatt Züge rein zufällig auszuwählen, implementieren Guimarães et al. eine deterministische Strategie. Dies wird als Move-Heuristik bezeichnet.
Ziel dieser Heuristik ist es, die Varianz der Simulationsergebnisse zu verringern und sicherzustellen, dass die Simulationen aussagekräftige Rückschlüsse auf die Qualität eines Knotens zulassen. Der Agent agiert dabei greedy und priorisiert Aktionen, die den Spielstand unmittelbar verbessern.
/**
* Erweitert einen Knoten v im Suchbaum
* @param {Node} v - Der zu expandierende Knoten
* @returns {Node} v' - Der neu erstellte Kindknoten
*/
function EXPAND(v) {
// 1. Wähle eine bisher nicht versuchte Aktion 'a' aus der Menge A(v)
let a = chooseUntriedAction(A(v));
// 2. Erstelle einen neuen Kindknoten v'
let v_prime = createNewChild(v);
// 3. Initialisierung des neuen Knotens
v_prime.s = APPLYACTION(v.s, a); // Neuer Zustand durch Aktion a
v_prime.a = a; // Speichere die ausgeführte Aktion
v_prime.A = MOVEPRUNING(v_prime.s); // Reduziere verfügbare Folgeaktionen via Heuristik
return v_prime;
}
/**
* Filtert die möglichen Aktionen (Pruning), um den Branching Factor zu senken
* @param {State} s - Der aktuelle Spielzustand
* @returns {List} Eine gefilterte Liste prioritärer Aktionen
*/
function MOVEPRUNING(s) {
let A = [];
// Priorität 1: Städte bauen
A = GETPOSSIBLECITIES(s);
if (A.length > 0) return A;
// Priorität 2: Siedlungen bauen
A = GETPOSSIBLESETTLEMENTS(s);
if (A.length > 0) return A;
// Priorität 3: Alle anderen legalen Aktionen (Straßen, Karten, Handel, etc.)
return GETOTHERPOSSIBLEACTIONS(s);
}
¶ Die Trade-Heuristik
Der Handel ist die komplexeste Komponente in Siedler von Catan. In jeder Spielphase könnte ein Agent theoretisch hunderte verschiedene Tauschangebote mit der Bank oder mit den Häfen generieren. In anderen Papers führt diese Komplexität häufig dazu, dass bei der Anwendung von MCTS auf Siedler von Catan oft die Spielregeln vereinfacht werden, indem der Handel ausgelassen wird.
Guimarães hingegen verfolgt einen "Trade-Optimistic" Ansatz. Das Ziel ist es, den Suchbaum nicht mit jedem möglichen Handel zu fluten, sondern nur solche Handelssequenzen zu betrachten, die unmittelbar eine nützliche Bauaktion ermöglichen.
¶ Das Konzept der "Trade-Optimistic-Moves"
Anstatt Handel als eigenständige, isolierte Aktion im Baum zu betrachten, identifiziert der Algorithmus zunächst Bauaktionen, die der Spieler fast bezahlen könnte. Ein Zug gilt als trade-optimistic, wenn der Spieler zwar nicht die exakten Rohstoffe besitzt, aber die Summe seiner Rohstoffe ausreicht, um die Kosten durch Tauschaktionen mit der Bank zu decken.
¶ Implementierung in JavaScript
Die folgende Implementierung zeigt, wie der Agent fehlende Ressourcen identifiziert und die notwendige Handelssequenz in eine Aktions-Queue einreiht, um ein Bauziel zu erreichen (Auszug aus gesamten Code für die Trade-Heuristik):
/**
* Identifiziert Züge, die durch Handel ermöglicht werden könnten.
* Entspricht 'GetTradeOptimisticMoves' aus Algorithm 2.
*/
function getTradeOptimisticMoves(v) {
let player = getCurrentPlayer(v.state);
let optimisticActions = [];
let legalActions = getAllPossibleActions(v.state);
for (let action of legalActions) {
// Prüfe: Kann es sich der Spieler aktuell NICHT leisten,
// aber ist die Gesamtmenge seiner Ressourcen >= Kosten der Aktion?
if (!canAfford(player, action) &&
totalResourceCount(player) >= totalResourceCost(action)) {
optimisticActions.push(action);
}
}
return optimisticActions;
}
/**
* Berechnet die notwendigen Tauschvorgänge für eine Zielaktion.
* Basierend auf 'GetTradesNeeded' aus Algorithm 2.
*/
function getTradesNeeded(player, targetAction) {
let trades = [];
let missingResources = getMissingResources(player.resources, targetAction.cost);
// Für jede fehlende Ressource wird ein Trade-Vorgang generiert
for (let resource of missingResources) {
let tradeAction = {
type: "TRADE",
give: selectExcessResource(player), // Wähle eine Ressource, die man übrig hat
get: resource
};
trades.push(tradeAction);
}
return trades;
}
¶ Integration der Heuristiken in den MCTS-Zyklus
Im Folgenden ist nun zu sehen in welchen Phasen von MCTS die beiden Heuristiken angewandt werden.
¶ 1. Selection
In dieser Phase navigiert der Algorithmus vom Wurzelknoten (dem aktuellen Spielzustand) abwärts zu einem Blattknoten. Hierbei wird die UCT-Formel (Upper Confidence Bound applied to Trees) angewendet:
Die Selektion ist bereits durch die Move-Heuristik (Pruning) beeinflusst, da nur Knoten zur Auswahl stehen, die in der vorherigen Expansions-Phase als "sinnvoll" erachtet wurden.
¶ 2. Expansion
In der Expansionphase wird der Baum um neue Knoten erweitert. Hier greifen beide Heuristiken von Guimarães ein:
Move-Pruning:
- Wenn eine neue Aktion gewählt wird, um einen Kindknoten zu erzeugen, berechnet die Funktion
MOVEPRUNING(s(v'))sofort die Menge der für diesen neuen Knoten verfügbaren Folgeaktionen . - Es findet eine hierarchische Filterung statt:
- Sind Städtebau-Aktionen möglich, werden ausschließlich diese als zukünftige Optionen für diesen Zweig zugelassen.
- Sind keine Städte, aber Siedlungen möglich, werden nur diese zugelassen.
- Dadurch wird verhindert, dass der Baum in die Breite wächst, wenn starke strategische Züge verfügbar sind.
Trade-Optimistic Search:
- Während der Expansion prüft der Algorithmus, ob ein Spieler eine Aktion (z. B. eine Siedlung) durch Handel mit der Bank ermöglichen könnte.
- Gilt eine Aktion als trade-optimistic (Summe der Ressourcen reicht aus), wird sie künstlich in die Menge der verfügbaren Aktionen aufgenommen, auch wenn die exakten Rohstoffe noch fehlen.
¶ 3. Simulation
Sobald ein neuer Knoten hinzugefügt wurde, startet das Playout. In herkömmlichen MCTS-Ansätzen erfolgt dies zufällig. Jedoch führt dies selten zum Sieg.
- An dieser Stelle ersetzt die Move-Heuristik den Zufall durch eine Simulation Policy.
- Jeder simulierte Spieler (auch der Gegner) entscheidet nach der Prioritätenliste: Städte > Siedlungen > andere Züge.
- Dies führt zu einer realistischeren Bewertung des Endzustands, da die simulierten Agenten aktiv versuchen, Siegpunkte zu generieren.
¶ 4. Backpropagation
Das Ergebnis der Simulation (Gewinn oder Verlust) wird im Baum nach oben gereicht.
¶ Analyse und Vergleich der Implementationen
In den Versuchen spielte der MCTS-Agent jeweils gegen drei Instanzen der standardmäßigen JSettlers-KI. Die Ergebnisse wurden in zwei Kategorien ausgewertet: der Einfluss der Simulationsanzahl (Rollouts) und der Vergleich verschiedener Heuristik-Konfigurationen.
¶ Übersicht der Algorithmus-Varianten
Guimarães et al. [1] testen verschiedene Konfigurationen des UCT-Algorithmus, die sich durch die Kombination unterschiedlicher Optimierungen unterscheiden:
| Abkürzung | Bedeutung | Beschreibung |
|---|---|---|
| PlainUCT | Standard UCT | Basis-Implementierung ohne Heuristiken. Züge werden zufällig simuliert. |
| VW-UCT | Virtual Wins UCT | UCT mit Virtual Wins: Neue Knoten werden mit einem fiktiven Startwert initialisiert, um die Exploration zu stabilisieren. |
| MP-UCT | Move Pruning UCT | UCT mit Move-Heuristik: Der Suchraum wird durch hierarchisches Filtern (Städte > Siedlungen > Rest) eingeschränkt. |
| MP-EnsembleUCT | Move Pruning + Ensemble | Kombination aus Move Pruning und Ensemble UCT: Mehrere UCT-Bäume werden parallel betrieben und ihre Ergebnisse aggregiert. |
| MPT-EnsembleUCT | Move Pruning + Trade + Ensemble | Vollständige Kombination: Move Pruning, Trade-Optimistic Search und Ensemble UCT. Dies ist die leistungsstärkste Variante. |
¶ Die experimentelle Umgebung: JSettlers
Für die Durchführung der Simulationen und den Vergleich der Algorithmen wurde auf das Framework JSettlers zurückgegriffen. Dabei handelt es sich um eine Open-Source-Implementierung von Siedler von Catan in Java, die in der KI-Forschung als Standard-Benchmark etabliert ist.
Warum JSettlers?
Das Framework bietet eine robuste Client-Server-Architektur. Dies erlaubt es, KI-Bots als Clients an einen Server anzubinden, der die Einhaltung der Spielregeln überwacht und den Spielzustand verwaltet. Für die Forschung entscheidend ist die Möglichkeit, Spiele ohne grafische Oberfläche (Headless Mode) in Hochgeschwindigkeit durchzuführen. Nur so können die für Monte-Carlo-Methoden notwendigen tausenden Testpartien in akzeptabler Zeit generiert werden.
Ressource: Der Quellcode und die ausführbare Anwendung sind frei zugänglich.
Hier gelangen Sie zur offiziellen JSettlers Projektseite (SourceForge)
¶ Tabelle: Einfluss der Berechnungstiefe (Rollouts)
Die folgende Tabelle zeigt, wie sich die Gewinnrate verändert, wenn dem Agenten mehr "Bedenkzeit" (von 1.000 auf 10.000 Simulationen pro Zug) gegeben wird.
| Agent | UCT Rollouts | Win Rate (Gewinnrate) |
|---|---|---|
| MP-UCT | 1,000 | 26.1% ± 7.14% |
| MP-EnsembleUCT | 1,000 | 32.8% ± 6.31% |
| MPT-EnsembleUCT | 1,000 | 40.0% ± 6.81% |
| MP-UCT | 10,000 | 38.4% ± 8.64% |
| MP-EnsembleUCT | 10,000 | 41.3% ± 7.66% |
| MPT-EnsembleUCT | 10,000 | 58.2% ± 7.09% |
Tabelle 1: Vergleich der Gewinnraten basierend auf der Anzahl der UCT-Rollouts [[1]](#literaturverzeichnis).
¶ Diagramm: Vergleich der Agenten-Konfigurationen
Die folgende Grafik visualisiert die Performance-Steigerung durch die verschiedenen Optimierungsstufen (bei 1.000 Rollouts). Man erkennt deutlich, wie die Kombination aus Move-Pruning und Trade-Heuristik (MPT) den Standard-Ansatz (PlainUCT) übertrifft.
Win Rate nach Agenten-Konfiguration (1.000 Rollouts)
════════════════════════════════════════════════════════
PlainUCT ██████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ 14%
VW-UCT ███████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ 17%
MP-UCT ███████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ 27%
MP-Ensemble █████████████░░░░░░░░░░░░░░░░░░░░░░░░░░░ 33%
MPT-Ensemble ████████████████░░░░░░░░░░░░░░░░░░░░░░░░ 40% ★
───────────────┼─────────┼─────────┼─────────┼─────────┤
0% 25% 50% 75% 100%
Abbildung 2: Grafische Auswertung der Gewinnraten bei 1.000 Rollouts. MPT-EnsembleUCT zeigt die stärkste Performance [1].
Interpretation der Ergebnisse:
- PlainUCT (ca. 14%): Ein Standard-MCTS ohne Heuristiken performt schlechter als ein Zufallsspieler (der theoretisch 25% Gewinnchance hätte). Dies liegt daran, dass der Suchbaum zu breit ist und der Agent sich "verläuft".
- MP-UCT (ca. 27%): Allein durch das Move Pruning (MP), also das Filtern sinnloser Bauzüge, steigt die Leistung auf ein kompetitives Niveau.
- MPT-EnsembleUCT (ca. 40% - 58%): Die Hinzunahme der Trade-Heuristik (T) bringt den entscheidenden Vorteil. Besonders bei hoher Rechentiefe (10.000 Rollouts, siehe Tabelle) dominiert dieser Agent das Spiel mit fast 60% Gewinnrate gegen drei Gegner.
Fazit: Die Daten belegen eindrucksvoll, dass MCTS in Siedler von Catan nur dann funktioniert, wenn der Suchraum durch domänenspezifisches Wissen (Heuristiken) massiv eingeschränkt wird.
¶ Fazit und Ausblick
Die Untersuchung von Guimarães (2012) liefert einen wichtigen Beitrag zur Anwendung von Monte Carlo Tree Search (MCTS) auf Spiele mit unvollständiger Information und hoher stochastischer Varianz. Die Ergebnisse zeigen deutlich, dass ein naiver MCTS-Ansatz (Vanilla UCT) an der Komplexität von Siedler von Catan scheitert, da der Suchraum durch Würfelglück und Handelsoptionen zu stark verzweigt ist.
Erst durch die Integration von domänenspezifischem Wissen in Form von Heuristiken wird der Algorithmus wettbewerbsfähig:
- Effizienzsteigerung: Das Move Pruning reduziert die Breite des Suchbaums effektiv, indem es strategisch sinnlose Züge (wie das wahllose Bauen von Straßen) frühzeitig ausschließt.
- Strategische Tiefe: Die Trade-Heuristik (Trade-Optimistic Search) ermöglicht es dem Agenten, komplexe Züge zu planen, die erst durch Handel möglich werden, ohne den Suchbaum mit irrelevanten Tauschangeboten zu überfluten.
- Spielstärke: Mit einer Gewinnrate von rund 58% gegen etablierte Heuristik-Bots (bei 10.000 Simulationen) beweist der Ansatz, dass MCTS auch in solch komplexen Umgebungen überlegen sein kann
¶ Zukünftige Forschung
Obwohl der optimierte UCT-Agent erstaunliche Erfolge erzielt, werden weiterhin wesentliche Aspekte des Spiels Siedler von Catan ausgelassen.
¶ Performance gegen Menschen
In dem Paper von Guimarães wurde der Agent nur gegen drei JSettler Agenten verglichen, jedoch ist es weiterhin unklar wie dieser gegen Menschen performt.
¶ Handeln zwischen Spielern
Die größte Limitation des aktuellen Modells ist die Beschränkung auf den Handel mit der Bank oder mit Häfen. In der Realität ist der Handel zwischen Spielern ein zentrales Element, um Win-Win-Situationen zu schaffen oder Gegner gezielt zu blockieren. Ein Agent müsste bewerten, ob ein Handel dem Gegner mehr nutzt als ihm selbst.
Beide Themen wären noch interessant zu erforschen.
¶ Literaturverzeichnis
| Nr. | Quelle |
|---|---|
| [1] | Guimarães, I. A.; Santos, E. S. Optimizing UCT for Settlers of Catan. Pontifícia Universidade Católica do Rio Grande do Sul (PUCRS), 2017. Online verfügbar: repositorio.pucrs.br |
| [2] | Wikipedia. Die Siedler von Catan. Online verfügbar: de.wikipedia.org, abgerufen am 14. Januar 2026. |