¶ Einführung
Game of Tron ist ein Computerspiel, welches ursprünglich in dem Kinofilm "Tron" von Disney aus 1982 vorkommt. In dem Film fuhren Avatare von Programmen in der virtuellen Welt auf Motorrädern, welche Linien hinter sich ziehen (Abb. 1), um feindliche Programme zu löschen.
¶ Spielregeln
¶ Spielfeld
Die betrachtete Version von Game of Tron wird auf einem n x m gridbasierten Spielfeld gespielt. Das Spielfeld wird durch eine Wand nach außen begrenzt. Um Varianz ins Spiel zu bringen, werden innerhalb des Spielfeldes Wände als Hindernisse platziert. Um das Spiel fair zu halten, wird oft ein symmetrisches Spielfeld gewählt mit symmetrischen Startpositionen. Auf symmetrischen Spielfeldern besteht eine höhere Wahrscheinlichkeit für Unentschieden, weshalb teilweise auf diese Symmetrie verzichtet wird.
¶ Ablauf
Das Spiel wird synchron von allen Spielern gespielt. Die Spieler können sich nur in die vier kardinalen Richtungen bewegen und ziehen hinter sich eine permanente Wand her. Das Ziel der Spieler ist es, die Gegner mit Wänden kollidieren zu lassen. Die kann mit unterschiedlichen Strategien geschehen, wie z. B. direkt vor den Gegnern eine Wand zu ziehen und sie damit einzukesseln.
¶ Spielende
Das Spiel endet, sobald nur noch ein Spieler sich bewegen kann bzw. noch nicht mit einer Wand kollidiert ist. Wenn zwei Spieler gleichzeitig mit einer Wand oder einem anderen Spieler kollidieren, gilt dies als unentschieden. Demnach geht es nicht um eingenommene Fläche, sondern nur ums Überleben.
¶ Alpha/Beta Suche
Ein Lösungsansatz für Game of Tron ist die Alpha/Beta Suche. Damit man diesen Ansatz durchführen kann, muss das Spiel vom gleichzeitigem Spielen zu abwechselndem Spielen geändert werden. Dadurch kann jeder Spielzug als Zweig im Suchbaum modelliert werden und dadurch können einfacher Vorteilspositionen der jeweiligen Spieler bestimmt werden.
Alpha/Beta wird hier dem einfachen MiniMax vorgezogen, da sich trotz nur drei Bewegungsrichtungen eine große Menge möglicher Spielzustände ergibt. Zusätzlich wird die Berechnungszeit pro Spielzug limitiert, wodurch es wichtig ist, einen möglichst effizienten Algorithmus zu haben.
¶ Heuristiken
Eine Heuristik ist eine Abschätzung der Spielposition als numerischer Wert. Dies wird in mehreren Lösungsansätzen verwendet, wenn die vollständige Berechnung aller möglichen Folgepositionen zeitlich nicht annehmbar ist und um das zu umgehen der Suchbaum möglichst schnell eingeschränkt werden soll. Die Heuristik zeigt mithilfe der numerischen Werte, welche Züge die abschätzbar besten sind und demnach den Suchbaum am meisten einschränken.
¶ Voronoi
Die Voronoi Heuristik (Bsp. in Abb. 3) ist eine Abschätzung der Fläche, die ein Spieler vor dem Gegner erreichen kann. Dies wird mithilfe der Manhattandistanz der Spieler zu den jeweiligen Feldern berechnet. Die Heuristik ermöglicht schnell eine Einschätzung der Position auf einfachen Spielfeldern, vor allem auf Spielfeldern ohne viele Hindernisse.
Jedoch treten Probleme in der Einschätzung in der Heuristik auf, wenn das Spielfeld in mehrere Subsectionen unterteilt ist. Wie in Abb 4 erkennbar ist, erklärt die Voronoi Heuristik die Position des blauen Spielers als besser, da er schneller mehr freie Felder erreicht. Problempunkt ist, dass der rote Spieler die Spielsituation bei optimalem Spiel gewinnen würde. Dies wird begründet, da sich der blaue Spieler nur für eine der zwei Richtungen entscheiden kann. Demnach überschätzt die Heuristik die blaue Position und trifft die falsche Entscheidung bei der Wahl der Spielzüge.
¶ Chamber Trees
Die Chamber Trees Heuristik ist besser geeignet für komplexere Spielsituationen mit unterteilten Spielbereichen. Um die Heuristik zu berechnen, wird das Spielfeld als Graph angesehen. Dabei werden die Spielbereiche an Artikulationspunkten unterteilt (Markierung durch Kreise in Abb 5).
Die einzelnen Spielbereiche werden jetzt in zwei Arten unterteilt, die umkämpften und die sicheren Bereiche.
Die Berechnung der erreichbaren Felder wird bestimmt, indem die Menge erreichbarer Felder im aktuellen Bereich mit den erreichbaren Feldern von dem Pfad im Graphen, welcher die meisten Felder besitzt, addiert wird. In umkämpften Bereichen wird mit Voronoi Heuristik bestimmt, wie viele Felder erreicht werden können.
¶ Monte Carlo Tree Search
Monte Carlo Tree Search (MCTS) ist ein Suchbaumalgorithmus, welcher in letzter Zeit in vielen Spielen als Lösungsansatz betrachtet wird. Vor allem in komplexeren Spielen mit viel Varianz findet er oft Anwendung. Deswegen wurde er auch für Game of Tron betrachtet. Um MCTS auf Game of Tron anwenden zu können, muss Game of Tron von synchronen Spielen zu abwechselndem Spielen angepasst werden.
¶ Selection
Die Auswahl des nächsten zu betrachtenden Spielzugs passiert mit UCT. In dem Paper von Den Teuling und Winands [T.1] wurde festgestellt, dass der MCTS Algorithmus die besten Ergebnisse mit einem C Wert von 10 erreicht. Dieser sorgt für eine gute Abwägung zwischen der Expansion neuer und bis jetzt gut bewerteter Knoten. Trotz der größeren Berechnungskosten und demnach weniger Durchführungen von Simulationen schneidet das Programm besser ab.
¶ Expansion
¶ Predictive Expansion Strategy
Um die Expansion Phase von MCTS effizienter zu gestalten, wird bei der Expansion von Knoten im Suchbaum zuerst getestet, ob die Spieler voneinander isoliert sind. Diese Überprüfung findet nach jedem zweiten Zug statt, sodass nur faire Positionen betrachtet werden. Wenn die Spieler isoliert sind, wird der Knoten nicht expandiert, sondern als terminaler Knoten angesehen. Der Ausgang der Position wird demnach sofort in die Backpropogation phase übergegangen. Wenn die Spieler nicht isoliert sind, oder das Spielfeld eine geringe Anzahl freier Felder hat, wird normal expandiert.
Diese Berechnung der Spielposition betrachtet das Spielfeld als Schachfeldmuster und berechnet, welcher Spieler mehr mögliche Züge hat.
Formel für die Berechnung der Anzahl Züge M:
| |
Z: Anzahl freie Felder
: Anzahl grauer Felder
: Anzahl weißer Felder
¶ Simulation
¶ Strategien
Um einen möglichst guten Ansatz für verschiedene Spielfelder zu finden, wurden mehrere unterschiedliche Strategien gewählt, welcher der Algorithmus während des Simulierens der Positionen befolgen soll. Getestet wurden 7 unterschiedliche Strategien: Random, Wall-Following, Offensive, Defensive, Mixed, Move Category und -greedy.
| Strategie | Erläuterung |
|---|---|
| Random | Wähle zufällig eine Bewegungsrichtung (links, geradeaus, rechts) |
| Wall-Following | Wähle Zug zu Feld mit den meisten anliegenden Wänden, aber weniger Wände als 3. Wenn mehrere Züge mit gleicher Anzahl vorliegen, wähle einen dieser zufällig |
| Offensive | Wähle Zug, der Distanz zwischen Spieler und Gegner minimiert |
| Defensive | Wähle Zug, der Distanz zwischen Spieler und Gegner maximiert |
| Mixed | Auswahl Zug findet zufällig aus einer anderen Strategie mit festen Wahrscheinlichkeiten statt. Die Wahrscheinlichkeiten betragen: 50% Wall-Following, 20% Random, 25% Defensive, 5% Offensive |
| Move Category | Diese Strategie ist ähnlich zur Mixed Strategie, jedoch werden die Wahrscheinlichkeiten dynamisch festgelegt. Nach jeder Simulation bekommt die Strategie nach Sieg eine höhere Wahrscheinlichkeit und nach Niederlage eine niedrigere |
| -greedy | Zug wird zufällig aus anderen Strategien mit als Wahrscheinlichkeit gewählt. Die Wall-Following hat 1- und für die restliche wird zufällig eine andere Strategie gewählt |
¶ Cut-Off
Zusätzlich wurde die Simulation durch einen möglichen Cut-Off erweitert. Dieser tritt ein, sobald die Spieler vollständig voneinander getrennt sind. Bei dem Cut-Off wird die Position als terminale Position gewertet und mithilfe der Berechnung der Anzahl erreichbarer freier Felder entschieden, ob die Position Sieg, Niederlage oder Unentschieden ist. Die Berechnung ist die gleiche wie bei Predictive Expansion Strategy.
Formel für die Berechnung der Anzahl Züge M:
| |
Z: Anzahl freie Felder
: Anzahl grauer Felder
: Anzahl weißer Felder
Die Überprüfung für den Cut-Off findet nicht jeden Zug in den Simulationen statt, da dies zu viel Rechenkraft gebrauchen würde.
¶ Score-Bounded MCTS Solver
Score-Bounded MCTS Solver[T.3] ist eine Erweiterung des normalen MCTS Solver[T.2]. Die Knoten des Suchbaumes bekommen einen Spielwert mit oberer (opt) und unterer Schranke (pess) zugeordnet. Die obere und untere Schranke bleiben fix, aus der Sicht eines Spielers. Um die Erweiterung hinzuzufügen, werden zwei Schritte von MCTS abgeändert, Backpropagation und Selection.
Bei Backpropagation werden außer den normalen Werten -1, 0, 1 auch die oberen und unteren Schranken an den Elternknoten gegeben. Wenn der Kindknoten ein terminaler Knoten ist, wird -1, 0 oder 1 geliefert.
Die Aktualisierung des Elternknotens ist abhängig von dem Spieler, welcher am Zug ist. Wie bei MiniMax gibt es einen maximierenden und einen minimierenden Spieler. Wenn der Elternknoten maximierend ist, ist die untere Schranke das Maximum der unteren Schranken des Kind- und Elternknotens. Die obere Schranke ist das Maximum der oberen Schranken aller Kindknoten. Wenn der Elternknoten ein minimierender Knoten ist, dann ist die obere Schranke das Minimum der oberen Schranken der Kinder und die untere Schranke das Minimum der unteren Schranken des Kind- und Elternknotens.
Bei der Selection Phase wird nun kombinierend mit UCT nach den oberen und unteren Schranken entschieden. Dadurch können Spielzüge, die gesichert zum Sieg führen, gewählt werden, auch wenn UCT dies nicht vorsieht.
Durch die Einführung oberer und unterer Schranken werden Cut-Offs wie bei Alpha/Beta Suche durchgeführt, um den Suchbereich zu optimieren.
¶ Vergleiche
Alle Vergleiche der verschiedenen Algorithmen und Strategien wurden auf drei verschiedenen Spielfeldern (Abb. 6) getestet. Alle Spielfelder sind symmetrisch, um faire Bedingungen aller Positionen zu gewähren.
Alle Vergleiche wurden auf der gleichen 2.4 GHz AMD Opteron CPU mit 8 GB of RAM durchgeführt. Pro Spielzug hatten die Algorithmen 1 Sekunde Berechnungszeit und es wurden pro Vergleich 100 Spiele pro Farbe pro Spielfeld gespielt. Demnach wurden für jeden Vergleich 600 Spiele durchgeführt.
Alle nachfolgenden Tabellen stammen aus der wissenschaftlichen Publikation von Den Teuling und Winands [T.1].
¶ Vergleich Simulationsstrategien
| Feld a | Rand. | Wall | Off. | Def. | Mixed | Move Cat. | -Greedy | |
|---|---|---|---|---|---|---|---|---|
| Rand | 58% | 90% | 83% | 71% | 67% | 52% | 70% | |
| Wall | 42% | 90% | 52% | 21% | 40% | 26% | 45% | |
| Off. | 10% | 10% | 31% | 16% | 13% | 12% | 15% | |
| Def. | 17% | 48% | 69% | 55% | 35% | 32% | 43% | |
| Mixed | 29% | 79% | 84% | 45% | 49% | 28% | 52% | |
| Move Cat. | 33% | 60% | 87% | 65% | 51% | 38% | 56% | |
| -Greedy | 48% | 74% | 88% | 68% | 72% | 62% | 69% |
| Feld b | Rand. | Wall | Off. | Def. | Mixed | Move Cat. | -Greedy | |
|---|---|---|---|---|---|---|---|---|
| Rand | 15% | 100% | 70% | 56% | 53% | 58% | 59% | |
| Wall | 85% | 99% | 50% | 78% | 86% | 88% | 81% | |
| Off. | 0% | 1% | 0% | 0% | 0% | 0% | 0% | |
| Def. | 30% | 50% | 100% | 77% | 96% | 51% | 67% | |
| Mixed | 44% | 22% | 100% | 23% | 37% | 45% | 45% | |
| Move Cat. | 47% | 14% | 100% | 4% | 63% | 36% | 44% | |
| -Greedy | 42% | 12% | 100% | 49% | 55% | 64% | 54% |
| Feld c | Rand. | Wall | Off. | Def. | Mixed | Move Cat. | -Greedy | |
|---|---|---|---|---|---|---|---|---|
| Rand | 91% | 98% | 18% | 43% | 50% | 49% | 58% | |
| Wall | 9% | 81% | 15% | 7% | 44% | 9% | 28% | |
| Off. | 2% | 19% | 9% | 20% | 12% | 15% | 13% | |
| Def. | 82% | 85% | 91% | 76% | 80% | 90% | 84% | |
| Mixed | 57% | 93% | 80% | 24% | 40% | 50% | 57% | |
| Move Cat. | 50% | 56% | 88% | 20% | 60% | 57% | 55% | |
| -Greedy | 51% | 91% | 85% | 10% | 50% | 43% | 55% |
Es ist klar zu erkennen, dass der Aufbau der Spielfelder entscheidend dafür ist, welche Strategie wie erfolgreich ist. Durch die unterschiedlichen Eigenschaften der Spielfelder, sind allgemeine Schlussfolgerungen treffbar. Die besten Strategien sind die defensiv orientierten Strategien und die zufälligen Strategien bilden eine solide Basis ohne viel Varianz zwischen den unterschiedlichen Spielfeldtypen.
¶ Vergleich MCTS gegen MCTS mit Cut-Off und MCTS mit Predictive Expansion Strategy
Um die Effizienz der Simulationsverbesserung des Cut-Off zu überprüfen, wurden auch hier Tests ausgeführt. Die Tests wurden jeweils mit der Simulationsstrategie Random getestet, um ein möglichst faires Ergebnis zu liefern. Zusätzlich wurden hier für die Spielfelder a und b 800 Spiele gespielt und für c 400.
| MCTS-PC | Feld a | Feld b | Feld c |
|---|---|---|---|
| Sieg | 54% | 56% | 33% |
Anhand dieser Tests ist ablesbar, dass die Cut-Off Verbesserung, wenn man unterschiedliche Spielfelder betrachtet, keine signifikanten Vorteile bringt.
Die Tests für Predictive Expansion Strategy wurden wieder mit 600 Spielen pro Feld durchgeführt. Es wurde ebenfalls die Simulationsstrategie Random verwendet.
| MCTS-PDE | Feld a | Feld b | Feld c |
|---|---|---|---|
| Sieg | 53% | 58% | 48% |
Dies liefert ähnliche Ergebnisse zum Cut-Off, da sie die gleiche Heuristik zur Bewertung verwenden. Predictive Expansion Strategy verbraucht weniger Berechnungszeit, da es nur einmal pro Expansion durchgeführt wird und nicht bei jeder Simulation. Demnach liefert es bessere Ergebnisse auf Spielfeldern, auf denen die Spieler selten isoliert sind.
¶ Vergleich MCTS gegen Score-Bounded MCTS Solver
Um zu überprüfen ob der MCTS Solver, welcher in den meisten Fällen effizienter ist als normales MCTS, auch bei Game of Tron effizienter ist, wurden hier ebenfalls Tests durchgeführt. Der Solver wurde ebenfalls durch Predictive Expansion Strategy und Cut-Off ergänzt. Hierbei wurden beide Algorithmen mit Simulationsstrategie Random durchgeführt.
| Feld a | Feld b | Feld c | |
|---|---|---|---|
| Solver | 50% | 52% | 57% |
| Solver-PDE | 32% | 74% | 53% |
| Solver-PDE-PC | 30% | 82% | 70% |
Der MCTS Solver ist insgesamt besser als MCTS. Die zusätzlichen Berechnungen sorgen für eine schlechtere Leistung bei einfacheren Spielfeldern.
¶ Vergleich Alpha/Beta gegen MCTS
Um die Leistung der MCTS Algorithmen zu testen, wurden diese gegen Alpha/Beta Suche getestet. Hierbei wurden alle MCTS Algorithmen mit der Simulationsstrategie Random durchgeführt.
| Feld a | Feld b | Feld c | |
|---|---|---|---|
| MCTS-UCT | 40% | 0% | 0% |
| MCTS-PDE | 44% | 0% | 0% |
| Solver-PDE | 13% | 12% | 0% |
| Solver-PDE-PC | 28% | 10% | 16% |
Die Alpha/Beta Suche ist dominant, selbst gegen den besten MCTS Algorithmus.
¶ Quellen
¶ Textquellen
Den Teuling, N. G., & Winands, M. H. (2011). Monte-Carlo Tree Search for the simultaneous move game Tron. Univ. Maastricht, Netherlands, Tech. Rep, 12, 15. pdf
Aikon Google AI Challenge post-mortem
Winands, M. H., Björnsson, Y., & Saito, J. T. (2008, September). Monte-Carlo tree search solver. In International Conference on Computers and Games (pp. 25-36). Berlin, Heidelberg: Springer Berlin Heidelberg. pdf
Cazenave, T., & Saffidine, A. (2010, September). Score bounded Monte-Carlo tree search. In International conference on computers and games (pp. 93-104). Berlin, Heidelberg: Springer Berlin Heidelberg. pdf
¶ Bildquellen
Abb. 1: https://forgedinfilm.org/tron-1982/
Abb. 2: Den Teuling, N. G., & Winands, M. H. (2011). Monte-Carlo Tree Search for the simultaneous move game Tron. Univ. Maastricht, Netherlands, Tech. Rep, 12, 15. pdf
Abb. 3: Selbsterstellt
Abb. 4: Selbsterstellt
Abb. 5: Selbsterstellt
Abb. 6: Den Teuling, N. G., & Winands, M. H. (2011). Monte-Carlo Tree Search for the simultaneous move game Tron. Univ. Maastricht, Netherlands, Tech. Rep, 12, 15. pdf