¶ Einleitung
eigene Aufnahme CC BY 4.0
Carcassonne, benannt nach der gleichnamigen, mittelalterlichen Festungsstadt in Südfrankreich, wurde im Jahr 2000 von Klaus-Jürgen Wrede im Verlag Hans im Glück veröffentlicht. [1] Es handelt sich um ein Plättchenlegespiel, in der Standardversion, für 2-5 Spieler mit einer Spieldauer von 30-45 Minuten. [2]
Das Spiel wurde über 6 Millionen Mal weltweit verkauft und in über 20 Sprachen übersetzt. [3] Damit zählt es zu einem der bekanntesten modernen Gesellschaftsspielen weltweit. Das Spiel wurde 2001 mit dem Kritikerpreis des „Spiel des Jahres“ [4] und dem „Deutschen Spielepreis“ [5] ausgezeichnet. Im Laufe der Jahre erschienen immer mehr Erweiterungen und Neuauflagen, sodass die Carcassonne-Spielefamilie mittlerweile 8 Erweiterungen, 4 Abwandlungen, 17 Mini-Erweiterungen, sowie die Carcassonne Big-Box umfasst.[2:1]
Im Folgenden wird zunächst einmal in die Spielregeln eingeführt, bevor verschiedene Algorithmen für KI-Agenten untersucht werden. Dabei werden Monte Carlo Tree Search mit UCT, Monte Carlo Tree Search mit Rapid Action Value Estimation und Star2.5 näher betrachtet.
¶ Spielregeln [6]
Carcassonne ist ein strategisches Legespiel, bei dem Landschaftsplättchen angelegt und Meeples eingesetzt werden. Dadurch erschaffen die Spieler zusammen im Spielverlauf den Spielplan und es entsteht eine Landschaft aus Wiesen, Städten und Wegen. Ziel des Spiels ist es, durch das geschickte Anlegen von Plättchen und das Einsetzen von Meeples viele Punkte zu erzielen.
¶ Spielablauf
eigene Aufnahme CC BY 4.0
Zu Spielbeginn wird das Startplättchen in die Tischmitte gelegt. Dies bildet die Ausgangslage für das Spiel. Jeder Spieler wählt eine der verfügbaren Farben und erhält 7 Spielfiguren in der gewählten Farbe. Eine weitere Spielfigur wird auf das Punktetableau eingesetzt.
Carcassonne wird im Uhrzeigersinn gespielt, wobei der jüngste Spieler beginnt. Der Spieler, der am Zug ist, führt folgende Aktionen durch:
eigene Aufnahme · Lizenz: CC BY 4.0
eigene Aufnahme · Lizenz: CC BY 4.0
eigene Aufnahme · Lizenz: CC BY 4.0
¶ 1. Landschaftsplättchen legen
Der aktive Spieler zieht zufällig ein verdecktes Plättchen und legt es passend an ein bestehendes Plättchen in der Tischmitte an. Passend bedeutet dabei, dass sämtliche Landschaften fortgeführt werden müssen. Auf diese Weise entsteht nach und nach eine zusammenhängende Landschaft, die sich mit jedem Zug verändert und neue Anlegemöglichkeiten schafft. Sollte es keine Anlegemöglichkeit geben, so wird ein neues Plättchen gezogen.
¶ 2. Einen Meeple einsetzen
Nun besteht die Möglichkeit, ein Meeple auf das soeben gelegte Plättchen zu setzen. Dabei kann der Spieler frei entscheiden, auf welche Landschaft der Meeple eingesetzt werden soll. Voraussetzung dabei ist, dass der Spieler noch ein Meeple in seinem Vorrat zur Verfügung hat und dass das gewählte Gebiet noch frei von anderen Meeple ist – unabhängig davon, welcher Spieler sie dort platziert haben könnte. Dies ist optional, aber die einzige Möglichkeiten Punkte zu erhalten.
¶ 3. Eine Punktewertung auslösen
Nach dem Legen eines Landschaftsplättchens wird überprüft, ob durch das neue Plättchen ein Gebiet abgeschlossen wurde. Ist dies der Fall, wird sofort eine Punktewertung ausgelöst. Dabei können auch mehrere Gebiete gleichzeitig gewertet werden. Alle Spieler, die Meeple in den abgeschlossenen Gebieten platziert haben, können Punkte erhalten, nicht nur der aktive.
- Eine Straße gilt als abgeschlossen, wenn keine Fortsetzung mehr möglich ist. Für jede an der Straße beteiligte Plättchen erhält der Spieler einen Punkt.
- Eine Stadt ist abgeschlossen, wenn sie vollständig von einer Stadtmauer umgeben ist. Jedes beteiligte Plättchen und Wappen innerhalb der Stadt bringt zwei Punkte.
- Ein Kloster bringt 9 Punkte, wenn es von allen acht angrenzenden Feldern – orthogonal und diagonal – mit Plättchen umgeben ist.
Sollten mehrere Spieler Meeple in einem abgeschlossenen Gebiet haben, erhält der mit der Mehrheit die Punkte. Bei Gleichstand erhalten alle beteiligten Spieler die volle Punktzahl. Solche Situationen entstehen, wenn durch das Anlegen eines Plättchens zwei zuvor getrennte Gebiete miteinander verbunden werden.
Wiesen können während des Spiels nicht abgeschlossen werden und werden daher erst in der Schlusswertung berücksichtigt.
Zusätzlich gilt: Nach jeder Wertung werden die betroffenen Meeple zurück in den Vorrat genommen, sodass sie im weiteren Spiel erneut eingesetzt werden können.
¶ Spielende und Schlusswertung
Das Spiel endet, sobald kein Landschaftsplättchen mehr gezogen und angelegt werden kann. Anschließend erfolgt die Schlusswertung.
Am Spielende erhalten alle Spieler Punkte für noch nicht abgeschlossene Straßen, Städte und Klöster. Offene Straßen und Städte bringen jeweils einen Punkt pro Plättchen, sowie pro Wappen. Ein Kloster zählt einen Punkt für das Kloster selbst und zusätzlich je einen Punkt für jedes angrenzende Plättchen.
Nun werden auch die Wiesen gewertet. Diese sind durch Straßen und Städte voneinander getrennt. Der Eigentümer der Wiese, also der Spieler mit der Mehrheit, bzw. alle Beteiligten bei einem Unentschieden, der Meeple erhält 3 Punkte pro abgeschlossene Stadt innerhalb seiner Wiese.
Nun ist der Spieler mit den meisten Punkte der Sieger.
¶ Lösungsalgorithmen [7]
In diesem Experiment wurden drei verschiedene Algorithmen als Agenten zum Spielen von Carcassonne untersucht: Monte Carlo Tree Search (MCTS), Monte Carlo Tree Search RAVE (MCTS RAVE) und Star2.5.
¶ Baumstrukur
Die Grundlage aller untersuchten Algorithmen bildet die Modellierung des Spiels als Spielbaum. Ein Spielbaum beschreibt die Menge aller möglichen Spielverläufe, wobei jeder Knoten einen vollständigen Spielzustand repräsentiert und jede Kante eine mögliche Aktion darstellt. Die Blätter des Baums entsprechen Endzuständen, also vollständig ausgespielten Partien.
Ein Spielzustand umfasst in diesem Projekt:
- alle bisher gelegten Plättchen,
- die Position und Zugehörigkeit aller Meeples,
- sowie alle daraus resultierenden offenen und abgeschlossenen Landschaften.
Von jedem Zustand aus verzweigt sich der Baum in alle legalen Platzierungsoptionen des gezogenen Plättchens sowie in die möglichen Meeple‑Entscheidungen (Meeple setzen oder nicht, und falls ja: auf welche Landschaft).
Während der Spielbaum die theoretisch vollständige Menge aller möglichen Partien beschreibt, durchsuchen die Algorithmen in der Praxis nur einen Ausschnitt davon. Jeder der drei untersuchten Ansätze erzeugt daher seinen eigenen Suchbaum, der genau die Knoten enthält, die der jeweilige Algorithmus tatsächlich untersucht.
¶ Versuchsaufbau
Obwohl Carcassonne einen stochastischen Anteil besitzt – das zufällige Ziehen der Plättchen – wurde in den Experimenten versucht, diesen Zufallsfaktor so weit wie möglich zu reduzieren. Ziel war es, zuverlässige und vergleichbare Aussagen über die Leistungsfähigkeit der untersuchten Algorithmen zu ermöglichen. Dafür waren faire, identische und vor allem wiederholbare Ausgangsbedingungen entscheidend.
Jedes Experiment besteht aus n Partien. In der ersten Hälfte der Partien ist Spieler A Startspieler, in der zweiten Hälfte Spieler B, um einen möglichen Startspielervorteil auszugleichen. Zusätzlich wurde ein Set von 100 vordefinierten Plättchensequenzen erzeugt. Jede Sequenz entspricht einer festen Reihenfolge der 71 Plättchen eines vollständigen Spiels. Für jede Partie wird exakt dieselbe Sequenz verwendet, sodass Unterschiede im Ergebnis ausschließlich durch die verschiedenen Algorithmen entstehen.
Kann ein gezogenes Plättchen nicht regelkonform gelegt werden, wird es unter den Stapel gelegt und ein neues Plättchen gezogen.
Für alle Algorithmen wurden feste Parameterwerte definiert, die zuvor mithilfe von Testspielen des Zufallsagents bestimmt wurden.
Zufallsagent:
Der Zufallsagent wählt die Positionierung eines gezogenen Plättchens und das Einsetzen eines Meeples gleichverteilt zufällig aus.
¶ Vergleichsmetriken
Alle Algorithmen bewerten Spielzustände anhand der Differenz der virtuellen Punkte der beiden Spieler:
= eigene virtuelle Punkte
= virtuelle Punkte des Gegners
Als virtuelle Punkte werden dabei die aktuellen Punkte, addiert mit den Punkten, die der Spieler erhalten würde, wenn jetzt das Spielende eintritt bezeichnet.
Weiter wurden folgende Parameter erhoben, um die verschiedenen Algorithmen untereinander zu vergleichen:
- – durchschnittlich erreichte virtuelle Punkte
- – durchschnittlich erreichte Belohnung
- – Mittelwert der eingesetzten Meeple pro Spiel
- – durchschnittliche Anzahl der Züge pro Spiel mit mindestens einem verfügbaren Meeple
- Mit t = Anzahl der Runden, in denen p1 mit einem verfügbaren Meeple begann
- Konstanten 28 und 29 = Gesamtzahl der Züge eines Spielers, also die Möglichkeit keine Meeples mehr zum Einsetzen zur Verfügung zu haben
¶ Monte Carlo Tree Search
Der verwendete MCTS‑Agent basiert auf dem klassischen Monte‑Carlo‑Tree‑Search‑Algorithmus mit UCT. MCTS kombiniert zufällige Simulationen mit einer schrittweisen Erweiterung des Suchbaums und eignet sich daher besonders gut für Spiele mit großer Verzweigungsbreite und langfristigen strategischen Abhängigkeiten – beides zentrale Eigenschaften von Carcassonne.
Carcassonne erzeugt in jedem Zug eine Vielzahl möglicher Anlegepositionen und Meeple‑Entscheidungen. MCTS kann diesen komplexen Raum effizient erkunden, da der Suchbaum nicht durch eine feste Tiefe begrenzt ist, sondern dynamisch entlang der vielversprechendsten Pfade wächst. Dadurch kann der Algorithmus sowohl kurzfristige Punktgewinne (z. B. durch abgeschlossene Städte oder Straßen) als auch langfristige Strategien wie die Nutzung von Wiesen berücksichtigen.
Für die Experimente wurde der Explorationsparameter auf C=3 gesetzt und pro Entscheidungsschritt wurden s=100 vollständige Simulationen durchgeführt. Jede Simulation spielt das Spiel bis zum Ende durch; der resultierende Endzustand wird mithilfe der virtuellen Punkte bewertet und fließt als Belohnung in die UCT‑Formel ein. Auf diese Weise erhält der Agent eine robuste Einschätzung darüber, welche Aktion langfristig vorteilhaft ist.
C = 3
100 Simulationen pro Simuklationsschritt
¶ Monte Carlo Tree Search mit rapid action value estimation
MCTS‑RAVE erweitert den klassischen MCTS‑Ansatz, indem zusätzlich zum UCT‑Wert ein AMAF‑Wert („All Moves As First“) berücksichtigt wird. Dabei werden Züge, die irgendwann in einer Simulation ausgeführt wurden, so behandelt, als wären sie bereits im aktuellen Knoten gespielt worden. Dadurch erhält der Algorithmus schon in frühen Suchphasen deutlich mehr verwertbare Informationen.
Für Carcassonne ist dieser Ansatz besonders hilfreich, da viele Züge strukturell ähnlich sind und ihre Auswirkungen erst spät sichtbar werden. MCTS‑RAVE erkundet den Spielbaum zu Beginn breiter und identifiziert vielversprechende Aktionen schneller. Mit zunehmender Anzahl an Simulationen verliert der RAVE‑Anteil an Gewicht, sodass der Algorithmus schrittweise zu einer Bewertung übergeht, die dem klassischen MCTS entspricht.
In den Experimenten wurden – analog zum MCTS‑Agenten – pro Entscheidungsschritt 100 Simulationen durchgeführt und der Explorationsparameter auf C=3 gesetzt. Zusätzlich wurde ein RAVE‑Bias von β=10 verwendet, der die Gewichtung der AMAF‑Schätzwerte in der Anfangsphase steuert.
C = 3
100 Simulationen pro Simulationsschritt
Bias β=10
¶ Star2.5
Der Star2.5‑Agent basiert auf einer Weiterentwicklung der *‑Minimax‑Familie, die speziell für Spiele mit stochastischen Elementen entwickelt wurde. Da Carcassonne durch das zufällige Ziehen der Plättchen Zufallsknoten enthält, verarbeitet Star2.5 neben regulären Entscheidungsknoten auch diese Zufallsknoten und bewertet die daraus entstehenden Spielzustände.
Im Gegensatz zu MCTS durchsucht Star2.5 jedoch nur einen begrenzten Ausschnitt des Spielbaums. Für die Experimente wurde eine maximale Suchtiefe von dmax=3 gewählt, da größere Tiefen aufgrund der hohen Verzweigungsbreite nicht praktikabel waren. Zusätzlich wurde ein Probing‑Faktor von b=5 eingesetzt, der bestimmt, wie viele Kinder eines Zufallsknotens untersucht werden, bevor potenzielle Teilbäume verworfen werden.
Um die Suche zu stabilisieren, wurde eine feste Reihenfolge für die Bewertung möglicher Meeple‑Einsätze definiert: Zunächst werden Städte betrachtet, gefolgt von Klöstern, Straßen, Zügen ohne Meeple und schließlich Wiesen. Diese Reihenfolge dient als heuristische Einschätzung typischer Wertigkeiten. Die Bewertung der betrachteten Zustände erfolgt mithilfe der virtuellen Punktefunktion, sodass der Algorithmus abschätzen kann, welcher Zug innerhalb der vorgegebenen Tiefe den günstigsten erwarteten Spielzustand erzeugt.
Prioritäten beim Meeple einsetzen: Stadt, Kloster, Straße, keine, Wiese
Simulationsfaktor: b = 5
Theoretischer Minimalwert: L = -100
Theoretischer Maximalwert: U = 100
Max Verzweigungstiefe: dmax = 3
Ein Psydocode von dem Star1.5 Algorithmus für Carcassonne wir hier vorgestellt.
¶ Ergebnisse und Analyse[7:1]
Um das Verhalten der verschiedenen Algorithmen unter identischen Bedingungen untersuchen zu können, wurden die darauf basierenden Agenten sowohl gegeneinander als auch gegen einen Zufallsagenten antreten gelassen. Alle Parameter wurden zuvor, wie bereits erläutert, festgelegt und während der gesamten Experimente beibehalten. Auf diese Weise lassen sich die beobachteten Unterschiede im Spielverhalten direkt auf die jeweiligen Entscheidungsmechanismen zurückführen. In den folgenden Abschnitten werden die daraus resultierenden Ergebnisse vorgestellt und eingeordnet.
¶ Agenten vs. Zufallsagent
Um das Verhalten der verschiedenen Algorithmen unter identischen Bedingungen untersuchen zu können, wurden die darauf basierenden Agenten sowohl gegeneinander als auch gegen einen Zufallsagenten antreten gelassen. Alle Parameter wurden zuvor, wie bereits erläutert, festgelegt und während der gesamten Experimente beibehalten. Auf diese Weise lassen sich die beobachteten Unterschiede im Spielverhalten direkt auf die jeweiligen Entscheidungsmechanismen zurückführen. In den folgenden Abschnitten werden die daraus resultierenden Ergebnisse vorgestellt und eingeordnet.
| Agent | \bar{r}_ | \bar{v}_ | \bar | \bar |
|---|---|---|---|---|
| MCTS | 93.45 | 107.44 | 14.98 | 0.57 |
| MCTS-RAVE | 95.74 | 109.42 | 15.47 | 0.59 |
| Star2.5 | 69.93 | 85.41 | 12.91 | 0.47 |
Tabelle 1: Ergebnisse der verschiedenen Agenten im Spiel gegen den Zufallsagenten
= durchschnittlich erreichte virtuelle Punkte
= durchschnittlich erreichte Belohnung
= Mittelwert der eingesetzten Meeple pro Spiel
= durchschnittliche Anzahl der Züge pro Spiel mit mindestens einem verfügbaren Meeple
Die Ergebnisse zeigen, dass alle drei Agenten in der Lage sind, gegen zufällige Entscheidungen konsistent zu punkten, wobei sich deutliche Unterschiede im Umgang mit den Ressourcen und in der Ausnutzung offener Landschaften abzeichnen.
Der MCTS Agent erzielt im Durchschnitt die höchsten virtuellen Punkte und auch die größte Punktedifferenz, während der Star2.5 Agent in beiden Kennzahlen die niedrigsten Werte erreicht. Dennoch liegen alle drei Agenten klar über dem Zufallsniveau. Die beiden MCTS basierten Verfahren zeigen untereinander sehr ähnliche Ergebnisse, was auf ein stabiles und konsistentes Entscheidungsverhalten hinweist.
Deutlicher fallen die Unterschiede in der Meeple Nutzung auf. Die MCTS basierten Agenten setzen im Durchschnitt mehr Meeples pro Spiel ein als Star2.5. Auch beim Anteil der Züge mit mindestens einem verfügbaren Meeple zeigt sich ein ähnliches Bild: Die MCTS Agenten bleiben über einen größeren Teil des Spiels hinweg handlungsfähig, während Star2.5 häufiger in Situationen gerät, in denen keine Meeples mehr zur Verfügung stehen. Diese Unterschiede deuten auf verschiedene Spielstrategien hin. Die MCTS basierten Agenten nutzen häufiger kurzfristige Punktgewinne durch Städte und Straßen, während Star2.5 vergleichsweise stärker auf langfristige Strukturen wie Wiesen setzt. Dadurch ergeben sich unterschiedliche Muster im Ressourcenverbrauch und in der Flexibilität während des Spiels.
Insgesamt wird deutlich, dass alle drei Agenten gegen den Zufallsagenten erfolgreich agieren, jedoch mit unterschiedlichen Schwerpunkten und Spielweisen. Die MCTS RAVE Variante erzielt im Durchschnitt die besten Werte über alle Kennzahlen hinweg, während Star2.5 die niedrigsten Werte erreicht. Diese Beobachtungen bilden die Grundlage für die anschließenden direkten Duelle zwischen den Agenten.
¶ MCTS-Agent vs. Star2.5-Agent
Im direkten Duell zwischen MCTS und Star2.5 wurden beide Agenten unter identischen Bedingungen getestet. Beide traten gleich häufig als Startspieler an, sodass mögliche Startspielereffekte ausgeglichen wurden. Unabhängig vom konkreten Ergebnis zeigt sich jedoch, dass der Startspieler in vielen Partien einen strukturellen Vorteil besitzt: Die jeweiligen Kennzahlen fallen tendenziell höher aus, wenn ein Agent den ersten Zug ausführt.
| Kriterium | MCTS als 1. Spieler | Star2.5 als 1. Spieler | MCTS als 2. Spieler | Star2.5 als 2. Spieler |
|---|---|---|---|---|
| Gewinnrate | 88.57 % | 22.86 % | 77.14 % | 2.86 % |
| \bar{r}_ | 20.29 | −16.82 | 16.82 | −20.29 |
| \bar{v}_ | 80.54 | 60.29 | 77.11 | 60.26 |
| \bar | 13.10 | 11.63 | 12.72 | 11.03 |
| \bar | 0.48 | 0.41 | 0.49 | 0.41 |
Tabelle 2: Ergebnisse der Spiele des MCTS-Agenten gegen den Star2.5-Agenten
Gewinnrate = in wie viel Prozent der Spiele der jeweilige Spieler gewonnen hat
= durchschnittlich erreichte virtuelle Punkte
= durchschnittlich erreichte Belohnung
= Mittelwert der eingesetzten Meeple pro Spiel
= durchschnittliche Anzahl der Züge pro Spiel mit mindestens einem verfügbaren Meeple
Die Auswertung der Gewinnraten und der erzielten Belohnung zeigt, dass der MCTS Agent in den meisten Partien erfolgreicher agiert als Star2.5, unabhängig davon, wer den ersten Zug macht. Dies spiegelt sich auch in den erzielten virtuellen Punkten wider, die beim MCTS Agenten im Durchschnitt höher liegen. Beide Agenten erreichen jedoch Werte, die deutlich über dem Zufallsniveau liegen, was auf konsistente und nachvollziehbare Entscheidungsmechanismen hinweist.
Deutliche Unterschiede zeigen sich im Umgang mit den Meeple Ressourcen. Der MCTS Agent setzt im Durchschnitt mehr Meeples pro Spiel ein und verfügt gleichzeitig in einem größeren Anteil der Züge über mindestens einen verfügbaren Meeple. Dadurch bleibt er über weite Teile des Spiels flexibel und kann auf kurzfristige Gelegenheiten reagieren, etwa indem er Städte oder Straßen zeitnah abschließt und die Meeples schnell wieder zurückerhält. Star2.5 agiert dagegen zurückhaltender: Er setzt weniger Meeples ein und hat häufiger Phasen, in denen keine Meeples mehr zur Verfügung stehen. Dies deutet darauf hin, dass Star2.5 stärker auf langfristige Strukturen wie große Gebiete oder Wiesen setzt, was jedoch mit geringerer Flexibilität im weiteren Spielverlauf verbunden ist.
Insgesamt zeigt der direkte Vergleich, dass der MCTS Agent in den meisten simulierten Partien erfolgreicher agiert als Star2.5 und eine Gewinnrate deutlich über 50 % erreicht. Beide Agenten verfolgen jedoch klar erkennbare, konsistente Strategien, die sich in ihren Ressourcenentscheidungen und Prioritäten widerspiegeln.
¶ MCTS-RAVE-Agent vs. Star2.5-Agent
Im direkten Vergleich zwischen dem MCTS RAVE Agenten und dem Star2.5 Agenten zeigt sich ein ähnliches Bild wie im Duell zwischen MCTS und Star2.5. Auch hier erzielt der MCTS RAVE Agent in den meisten Kennzahlen höhere Werte und gewinnt einen deutlich größeren Anteil der Partien. Auch in diesem Experiment erzielen beide Agenten unabhängig voneinander leicht bessere Ergebnisse, wenn sie der Startspieler sind.
| Kriterium | MCTS-RAVE als 1. Spieler | Star2.5 als 1. Spieler | MCTS-RAVE als 2. Spieler | Star2.5 als 2. Spieler |
|---|---|---|---|---|
| Gewinnrate | 84.29 % | 20.00 % | 78.57 % | 14.29 % |
| \bar{r}_ | 18.30 | −17.54 | 17.54 | −18.30 |
| \bar{v}_ | 80.66 | 62.46 | 80.00 | 62.36 |
| \bar | 13.33 | 11.48 | 13.17 | 11.11 |
| \bar | 0.5 | 0.41 | 0.52 | 0.4 |
Tabelle 3: Ergebnisse der Spiele des MCTS-RAVE-Agenten gegen den Star2.5-Agenten
Gewinnrate = in wie viel Prozent der Spiele der jeweilige Spieler gewonnen hat
= durchschnittlich erreichte virtuelle Punkte
= durchschnittlich erreichte Belohnung
= Mittelwert der eingesetzten Meeple pro Spiel
= durchschnittliche Anzahl der Züge pro Spiel mit mindestens einem verfügbaren Meeple
Betrachtet man sowohl die Gewinnrate als auch die erreichten virtuellen Punkte, so ist erkennbar, dass der MCTS-RAVE-Agent deutlich besser abschneidet als der Star2.5Agent und in mehr als der Hälfte der Partien als Sieger hervorgeht.
Wie bereits in den vorherigen Vergleichen lassen sich auch hier deutliche Unterschiede im Umgang mit den Meeple Ressourcen erkennen. Der MCTS RAVE Agent setzt im Durchschnitt mehr Meeples pro Spiel, der (mpg) ‾-Wert ist höher, ein und verfügt gleichzeitig in einem größeren Anteil der Züge über mindestens einen verfügbaren Meeple, der (twm) ‾-Wert ist ebenfalls höher als beim Star2.5-Agenten. Dies deutet darauf hin, dass er häufiger kurzfristige Punktgewinne realisiert und abgeschlossene Landschaften effizient nutzt, wodurch Meeples schneller wieder freigegeben werden. Dagegen setzt der Star2.5-Agent eher auf langfristige Punktgewinne, was zur Folge hat, dass dieser einen geringeren Anteil an Zügen mit einsetzbaren Meeple hat.
Zusammenfassend zei8gt der direkte Vergleich, dass der MCTS-RAVE-Agent den Star2.5-Agenten in den meisten Partien schlägt, unabhängig davon, welcher Agent den ersten Zug ausführt.
¶ MCTS-Agent vs. MCTS-RAVE-Agent
Der direkte Vergleich zwischen dem MCTS Agenten und dem MCTS RAVE Agenten ist besonders interessant, da beide Verfahren in den vorherigen Experimenten deutlich besser abschnitten als der Star2.5 Agent. Im Folgenden wird untersucht, wie sich die beiden MCTS Varianten im direkten Duell zueinander verhalten.
| Kriterium | MCTS-RAVE als 1. Spieler | MCTS als 1. Spieler | MCTS-RAVE als 2. Spieler | MCTS als 2. Spieler |
|---|---|---|---|---|
| Gewinnrate | 51 % | 64 % | 36 % | 49 % |
| \bar{r}_ | 0.11 | 2.67 | -2.67 | −0.11 |
| \bar{v}_ | 80.05 | 80.75 | 78.08 | 79.94 |
| \bar | 13.49 | 13.71 | 12.61 | 13.32 |
| \bar | 0.5 | 0.51 | 0.48 | 0.51 |
Tabelle 4: Ergebnisse der Spiele des MCTS-RAVE-Agenten gegen den MCTS-Agenten
Gewinnrate = in wie viel Prozent der Spiele der jeweilige Spieler gewonnen hat
= durchschnittlich erreichte virtuelle Punkte
= durchschnittlich erreichte Belohnung
= Mittelwert der eingesetzten Meeple pro Spiel
= durchschnittliche Anzahl der Züge pro Spiel mit mindestens einem verfügbaren Meeple
Bei der Betrachtung der Gewinnraten zeigt sich ein differenziertes Bild. Der MCTS RAVE Agent gewinnt als Startspieler rund die Hälfte der Partien, während der MCTS Agent als Startspieler einen höheren Anteil seiner Spiele für sich entscheidet. Insgesamt ergibt sich daraus kein eindeutiger Vorteil für eine der beiden Varianten über alle Partien hinweg. Auffällig ist jedoch, dass der MCTS Agent als Startspieler konstanter gewinnt, was auf ein stabileres Entscheidungsverhalten in frühen Spielphasen hindeuten könnte. Dieses Ergebnis steht im Gegensatz zu den Experimenten gegen den Zufallsagenten, in denen der MCTS RAVE Agent die besseren Werte erzielte, was sich auch vermuten lässt, da er mehr Informationen früher zur Verfügung hat.
Ein Blick auf die weiteren Kennzahlen zeigt, dass beide Agenten insgesamt sehr ähnlich agieren. Unterschiede treten vor allem dann auf, wenn der MCTS RAVE Agent als zweiter Spieler agiert: In diesem Fall setzt er im Durchschnitt etwas weniger Meeples ein, was mit den geringeren erzielten Punkten korrespondieren könnte. Auch bei der Verteilung der Meeple auf verschiedene Landschaftsarten zeigen sich nur geringe Abweichungen. Eine Ausnahme bilden die Wiesen, auf denen der MCTS RAVE Agent etwas seltener Meeples (2,8 Meeple) platziert als der MCTS Agent (3 Meeple). Dies könnte darauf hindeuten, dass der MCTS Agent den Zeitpunkt für das Setzen eines Meeples auf Wiesen etwas zuverlässiger einschätzt.
Detaillierte Analysen einzelner Partien lassen außerdem vermuten, dass der MCTS RAVE Agent in bestimmten Situationen risikofreudiger agiert. Dies spiegelt sich in etwas niedrigeren (twm) ‾-Werten, was darauf hindeutet, dass er häufiger in Situationen gerät, in denen keine Meeples mehr eingesetzt werden können.
Insgesamt zeigt der direkte Vergleich, dass beide MCTS Varianten eine recht ähnliche Spielstrategie verfolgen. Während der MCTS RAVE Agent in den Spielen gegen den Zufallsagenten die besseren Ergebnisse erzielte, schneidet der MCTS Agent im direkten Duell geringfügig besser ab. Diese scheinbar widersprüchlichen Beobachtungen verdeutlichen, dass die Leistungsfähigkeit der Algorithmen stark vom jeweiligen Gegenspieler und der Spielsituation abhängt. Eine größere Anzahl unterschiedlicher Agenten oder zusätzlicher Varianten könnte helfen, die Robustheit der Verfahren noch zuverlässiger zu beurteilen.
¶ Fazit
Die durchgeführten Experimente zeigen, dass unter konstanten Rahmen- und Spielbedingungen alle drei untersuchten Agenten individuelle Spieltaktiken entwickeln, die sich in ihrem Ressourcenmanagement und der Nutzung verschiedener Landschaftsarten widerspiegeln.
Der Leistungsunterschied zwischen dem MCTS Agenten und dem MCTS RAVE Agenten fällt insgesamt gering aus, beide Verfahren agieren in vielen Spielsituationen ähnlich und erreichen vergleichbare Werte. Dennoch ergeben sich in einzelnen Tests, im Spiel gegen den Zufallsagenten und im direkten Vergleich, scheinbar widersprüchliche Ergebnisse, was eine genauere Untersuchung benötigt. Deutlichere Unterschiede zeigen sich hingegen im Vergleich zu Star2.5: Die MCTS basierten Agenten erzielen in nahezu allen Metriken höhere Werte und agieren insgesamt stabiler.
Diese Unterschiede lassen sich durch die zugrunde liegenden Suchstrategien erklären. Beide Varianten von MCTS basieren auf vollständigen Simulationen von Spielbaumzweigen und berücksichtigen dadurch potenzielle Entwicklungen über mehrere Züge hinweg bis hin zum Spielende, was eine Form der langfristigen Planung ermöglicht. Star2.5 hingegen arbeitet mit einer festen Suchtiefe von 3 und orientiert sich somit stärker am aktuellen Zustand des Spielbaums und wählt darauf basierend den nächsten Zug aus. Dadurch optimiert er vor allem die aktuelle Situation, bzw. den nächsten Spielzug, ohne weiterreichende Entwicklungen einzubeziehen. Aus diesen unterschiedlichen Ansätzen ergeben sich charakteristische Muster im Umgang mit offenen Landschaften, abgeschlossenen Features und der Nutzung begrenzter Meeple Ressourcen.
Auf Grundlage dieser Analyse erscheinen die MCTS basierten Verfahren insgesamt geeigneter für den Einsatz in einem Carcassonne KI Agenten als der Star2.5 Algorithmus. Die Experimente liefern ein umfassendes Bild über die Leistungsfähigkeit der drei untersuchten Ansätze und bilden eine solide Grundlage für weiterführende Untersuchungen. Dennoch sollten auch diese Verfahren in zukünftigen Studien mit einer größeren Stichprobe, variierenden Parametereinstellungen und insbesondere weiteren Priorisierungen der Meeple Einsatzmöglichkeiten beim Star2.5 Agenten erneut getestet werden. Weiterführende Arbeiten könnten zusätzliche Varianten der Algorithmen einbeziehen, Parameter gezielt optimieren oder hybride Verfahren entwickeln, um das Potenzial der unterschiedlichen Suchstrategien zu kombinieren und noch besser auszuschöpfen.
¶ Ausblick
Weiterführende Arbeiten könnten und sollten zusätzliche Varianten der Algorithmen einbeziehen, Parameter gezielt optimieren oder hybride Verfahren entwickeln, um das Potenzial der unterschiedlichen Suchstrategien zu kombinieren und noch besser auszuschöpfen. Auch ist es sinnvoll weitere Algorithmen systematisch zu untersuch, zu vergleichen und zu evaluieren.
Ein Ansatz zur Veränderung des Experiments besteht darin, den Aufbau des Spielbaums anzupassen, um den Verzweigungsgrad deutlich zu reduzieren. In der aktuellen Modellierung wird jeder Zug auf einer einzigen Ebene abgebildet, was zu einem durchschnittlichen Verzweigungsgrad von 55 führt [8]. Stattdessen kann der Zug in seine drei Schritte aufgeteilt und auf drei getrennten Baumebenen modelliert werden [9]:
- zufälliges Plättchen ziehen
- Plättchen platzieren
- Meeple setzen
Für jedes mögliche Plättchen, das an einem Zufallsknoten gezogen werden kann, wird ein Platzierungsknoten erzeugt, gefolgt von einem Knoten für die Meeple Platzierung. Im Expansionsschritt werden stets alle drei Ebenen erweitert, sodass pro Expansion genau eine Aktion hinzugefügt wird. Der Zufallsknoten geht dabei von einer Gleichverteilung über alle verbleibenden Plättchen aus, unabhängig davon, wie viele Exemplare eines Typs noch verfügbar sind. Dadurch wird der Verzweigungsgrad auf 4-30 verringern [9:1].
Darüber hinaus könnten anstelle der varianten des UCT Werts weitere Tree Policies untersucht werden, etwa Greedy oder ε Greedy [9:2]. Eine weitere interessante Variante ist UCT Tuned [10], bei der der Explorationsterm wie folgt angepasst wird:
mit
Des Weiteren ist es empfehlenswert, weitere heuristische Bewertungsfunktionen näher zu betrachten, um die Qualität und Effizienz der Agenten zu optimieren.
Abschließend erscheint es sinnvoll, weitere Algorithmen, Parameterkonfigurationen und Modellierungsansätze zu untersuchen, um den für den KI Agenten optimalen Ansatz zu erhalten.
¶ Referenzen
¶ Bildquellen
- Abbildung 1: eigene Aufnahme
- Abbildung 2: eigene Aufnahme
- Abbildung 3: eigene Aufnahme
- Abbildung 4: eigene Aufnahme
- Abbildung 5: eigene Aufnahme
¶ Gleichungsverzeichnis
- Gleichung 1: (4) aus "Playing carcassonne with monte carlo tree search"[7:2]
- Gleichung 2: (5) aus "Playing carcassonne with monte carlo tree search"[7:3]
- Gleichung 3: (3) aus "Monte Carlo Tree Search for Carcassonne"[9:3]
- Gleichung 4: (4) aus "Monte Carlo Tree Search for Carcassonne"[9:4]
¶ Literatur
https://rollenspiel-welt.de/carcassonne-brettspiel-familie/ (letzer Zugriff 04.01.2026 um 13:10 Uhr) ↩︎
https://www.hans-im-glueck.de/carcassonne-familie/ (letzer Zugriff 04.01.2026 um 14:17 Uhr) ↩︎ ↩︎
https://de.wikipedia.org/wiki/Carcassonne_(Spiel) (letzer Zugriff 04.01.2026 um 13:25 Uhr) ↩︎
https://www.spiel-des-jahres.de/spiele/carcassonne/ (letzer Zugriff 04.01.2026 um 12:05 Uhr) ↩︎
https://www.spiel-essen.de/de/programm/dsp/deutscher-spielepreis-historie ↩︎
https://www.hans-im-glueck.de/_Resources/Persistent/3581b911bf5113e36646fe91e1f4b47ee03f67b0/CarcBB6_Rule_D_Final_2_Web.pdf ↩︎
Ameneyro, Fred Valdez, Edgar Galván, and Ángel Fernando Kuri Morales. “Playing carcassonne with monte carlo tree search.” 2020 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2020 pdf ↩︎ ↩︎ ↩︎ ↩︎
Cathleen Heyden. Implementing a computer player for carcassonne. Master’s thesis, Maastricht University, Department of Knowledge Engineering, 2009.pdf ↩︎
Jappert, Max. “Monte Carlo Tree Search for Carcassonne.” (2022). pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235–256, 2002. pdf ↩︎