Chain Recation ist ein deterministisches Zwei-Spieler Spiel mit vollständiger Informiertheit. Es existieren auch Mehrspieler-Varianten von Chain Reaction. Dieser Wiki-Artikel befasst sich nur mit der Zwei-Spieler Variante.
¶ Spielprinzip
Wie auch bei der Spieleranzahl, existieren mehrere Auslegungen der Spielregeln für Chain Reaction. Die algorithmischen Betrachtungen dieses Artikels basieren auf den Spielregeln aus dem Paper Highly Volatile Game Tree Search in Chain Reaction[1].
Unabhängig von den konkreten Regeln, ist das Ziel des Spiels, jedoch immer alle gegenerischen Felder zu erobern, sodass die Gegenspielerin keine Spielsteine bzw. Felder im Besitz mehr hat. Ein Feld ist in eigenem Besitz, sobald mindestens ein eigener Spielstein darauf platziert ist.
¶ Spielaufbau
Gespielt wird auf einem Spielbrett. Dabei hat jedes einzelne Feld eine Kapazität in Höhe der Anzahl seiner Nachbarfelder. Zwei Felder gelten als benachbart, wenn sie mit ihren Kanten aneinander grenzen.
¶ Spielzüge
Ist eine Spielerin am Zug, platziert sie einen Spielstein auf einem Feld, das leer oder bereits in eigenem Besitz ist.
¶ Spielfeld-Explosion
Entspricht die Anzahl an Spielsteinen auf einem Spielfeld seiner Kapazität, kommt es zur "Explosion". Das bedeutet, dass die Spielsteine auf die benachbarten Felder verteilt werden. Je ein Spielstein pro Nachbarfeld.
Etwaige gegnerische Nachbarfelder fallen, inklusive der dort vorhandenen gegnerischen Spielsteine, in Besitz der "explodierenden" Spielerin.
¶ Kettenreaktion
Wird ein Feld eingenommen, das zuvor nur einen Spielstein von seiner Kapazitätsgrenze entfernt gewesen ist, so explodiert es auch. Dadurch kommt es zu Kettenrekationen (engl.: chain reactions), die das Spiel nahezu unvorhersehbar machen. Ein Zug kann dabei das gesamte Spiel beenden (s. Abb. 4).
¶ Klassische Lösungsansätze
¶ Minimax
¶ Funktionsweise
Durch seinen Zwei-Spieler Aufbau eignet sich für Chain Reaction der Minimax-Algorithmus, der auf dem 1928 von John von Neumann bewiesenen Min-Max-Theorem [2] fußt:
: Strategie des Spielers A
: Strategie des Spielers B
: Gewinnfunktion aus Sicht des Spielers A
: Spielwert
Linker Teil der Gleichung:
Spieler B versucht zunächst, durch seine Strategie , den Gewinn für Spieler A zu minimieren. Spieler A wählt daraufhin eine Strategie , um den Gewinn zu maximieren.
Rechter Teil der Gleichung:
Der erzielte Gewinn ist dabei genauso hoch, wie wenn B versucht durch seine Strategie den Gewinn zu minimieren, nachdem A durch seine gewählte Strategie versucht hat, seinen Gewinn zu maximieren.
Es wird davon ausgegangen, dass beide Spieler rational und optimal spielen. Somit ist der Gewinn für beide Situationen der gleiche und hat den Spielwert .
¶ Einschränkungen
Der hohe Verzweigungs- bzw. Branching-Faktor von Chain Reaction erhöht die Zeitkomplexität des Minimax-Algorithmus und erschwert damit dessen Anwendung.
Zusätzlich wird die Wirksamkeit des Minimax-Algorithmus durch den Horizont-Effekt eingeschränkt: je nachdem wie weit ein Spielbaum entwickelt wird, bleiben alle möglichen Spielzüge jenseits des zuletzt betrachteten Knotens, des Horizonts, unberücksichtigt.
Da viele Züge in Chain Reaction komplexe Kettenreaktionen auslösen, bewertet der Minimax-Algorithmus viele Spielsituationen unpräzise.
¶ Monte Carlo Tree Search
¶ Funktionsweise
Monte Carlo Tree Search (MCTS) basiert auf der Monte-Carlo-Simulation und damit auf einem stochastischen Verfahren. Der Algorithmus wurde erstmalig von Rémi Coulom 2006 auf das Spiel Go angewandt [3]. Go hat, wie auch Chain Reaction, einen sehr hohen Branching-Faktor und ist genauso dynamisch, was dafür spricht MCTS für Chain Reaction zu verwenden.
MCTS erfordert kein Dömanenwissen und führt, anders als beim Minimax-Algorithmus, keine optimalen sondern zufällige Züge aus.
Die Vorgehensweise besteht darin, ausgehend von einem Knoten im Spielbaum, eine feste Anzahl an Spielen pro Knoten zu simulieren. Eine Simulation besteht aus zufälligen Zügen und jedes Spiel wird bis zum Spielende simuliert. Anhand der Simulations-Spielergebnisse wird ein Erwartungswert und damit eine Bewertung für den Knoten generiert. Der Knoten mit dem besten Wert wird ausgewählt und weiterentwickelt.
¶ Einschränkungen
Durch den hohen Branching-Faktor von Chain Reaction ist die Durchführung von MCTS, wie auch bei der Anwendung des Minimax-Algorithmus, sehr zeit- und ressourcenintensiv. Ein weiterer Nachteil der Verwendung von Monte Carlo Tree Search ist die schwache Bewertung starker, aber volatiler, Züge.
¶ Spielspezifische Konzepte[1:1]
¶ Progressive Pruning
Progressive Pruning ist eine Erweiterung der Monte Carlo Methode, die für die Lösung von Chain Reaction entwickelt wurde. Es handelt sich um ein turnierbasiertes Bewertungsverfahren, das in der Volatile Game Tree Search verwendet wird.
Zunächst einmal werden für jeden möglichen Spielzug Partien mit der Monte Carlo Methode simuliert. Die Bewertung von Spielzügen wird nach einer gewissen Anzahl von Simulationen jedoch verglichen und die der Spielzüge mit der schlechtesten bisherigen Bewertung werden nicht weiter untersucht.
ergibt sich dabei aus wobei die Anzahl an Runden ist, in denen die Knoten verglichen werden. Nach der letzen Runde, wird der bestbewertete Knoten der übrig gebliebenen Knoten noch einmal weiter untersucht.
Wenn beispielsweise 20 Knoten in 4 Runden verglichen werden, reduziert sich die Anzahl an zu untersuchenden Knoten pro Runde um und dadurch um 5 Knoten pro Runde:
Jeder Knoten erhält im Anschluss eine Pay-Off-Bewertung, die den zu erwartenden Gewinn angibt.
Bei der Entwicklung von Progressive Pruning haben D. Jenkins und C. Frayn festgestellt, dass Progressive Pruning bei gleichbleibender Performance rund 30% weniger Simulationen als klassische MCTS benötigt und daher gut für das ohnehin rechenintensive Chain Reaction geeignet ist.
¶ Volatilitätsheuristik
Volatilität bezeichnet im allgemeinen das Ausmaß der Veränderung einer Größe.
So wird beispielsweise ein Wertpapier, das schnell und oft seinen Preis ändert, als volatil bezeichnet.
Im Kontext von Chain Reaction ist die Volatilität ein Schlüsselkonzept zur algorithmischen Lösung des Spiels.
In dem Volatile Game Tree Search-Algorithmus, wird jedem Blattknoten am Spielbaum bzw. jedem potenziellen Spielzug im Rahmen einer Monte Carlo Simulation ein Volatilitätswert zugewiesen. Er ergibt sich aus der durchschnittlichen Änderung der Besitzverhältnisse beider Spielerinnen pro Spielzug pro Spielsimulation.
: Anzahl Züge (moves) in der Simulation
: i-ter Zug
: Anzahl Felder in Spielerbesitz
: Anzahl Felder in Gegenspielerbesitz
In Volatile Game Tree Search wird Volatilität verwendet, um das Suchfenster für optimale Spielzüge zu vergrößern, damit auch volatilere, aber potenziell gewinnbringende, Spielzüge berücksichtigt werden.
¶ Lösungsansatz Volatile Game Tree Search[1:2]
Dadurch, dass sich der Spielzustand in Chain Reaction sehr schnell drastisch ändern kann, wird seine Bewertung erschwert. Volatile Game Tree Search ist ein von D. Jenkins und C. Frayn entwickelter Ansatz, der dieser Herausforderung gerecht werden soll.
¶ Grundkonzept
Volatile Game Tree Search basiert auf einem --Suchalgorithmus in Kombination mit Progressive Pruning und einer Volatilitätsheuristik.
Das Vorgehen kann in 4 Schritte unterteilt werden:
¶ Algorithmus
¶ 1. Statistiken generieren
Im ersten Schritt werden mithilfe von Progressive Pruning und der Volatilitätsheuristik Statistiken für alle möglichen Spielzüge generiert:
Jedem möglichen Spielzug wird ein Pay-Off und eine Volatilität zugewiesen.
¶ 2. Spielbaum generieren
Der nächste Schritt ist die Generierung eines Spielbaums.
Zu Beginn wird festgelegt wie tief der Baum generiert werden soll. Jeder Knoten wird anhand einer weiteren Heuristik bewertet und die Bewertung anschließend anhand dem zu erwarteten Pay-Off, der in Schritt 1 errechnet wurde, skaliert.
Um die Knoten zu bewerten, ist eine weitere Heuristik nötig.
In der sehr begrenzt verfügbaren Literatur zu Chain Reaction wird darauf leider nicht weiter eingegangen.
Denkbar wäre aber eine Heuristik, durch die die Anzahl an Spielsteinen, Spielfeldern oder benachbarter Spielfelder mit beinahe ausgeschöpfter Kapazität (also kurz vor der Explosion) betrachtet werden.
¶ 3. --Suchfenster modifizieren
Um starke, aber volatile, Züge nicht vorschnell abzuschneiden, werden und , und damit das Suchfenster für die Suche des passenden Spielzugs, verändert:
Ein starker, aber volatiler, Zug hat eine höhere Wahrscheinlichkeit eine niedrige Pay-Off-Bewertung zu erhalten. Somit würde er ohne eine Anpassung des Suchfensters weniger berücksichtigt werden.
¶ 4. Bestmöglichen Zug mit --Suche ermitteln
Um den bestmöglichen Zug zu ermitteln, wird nun mithilfe des neuen Suchfensters und der Knotenbewertungen der Spielbaum nach dem bestmöglichen Zug durchsucht.
¶ Performance
In Ihrem Paper Highly Volatile Game Tree Search in Chain Reaction[1:3] haben D. Jenkins und C. Frayn den Volatile Game Tree Search Algorithmus einmal gegen ein Programm, das rein zufällig spielt, und einmal gegen einen Minimax-Algorithmus antreten lassen. Die Heuristik des Minimax-Algorithmus bestand darin die Anzahl der eigenen Spielsteine zu zählen.
Es wurden je 1000 Partien auf einem 5x5 Brett gespielt. In der Volatile Game Tree Search wurden immer 1 bis 100 Monte Carlo Simulationen mit einer anschließenden Suchtiefe von 1 bis 4 durchgeführt.
Gegen zufällig generierte Spielzüge konnte sich Volatile Game Tree Search gut durchsetzen, gegen den Minimax-Algorithmus, der immer die selbe Suchtiefe wie Volatile Game Tree Search hatte wurden schlechte Ergebnisse erzielt.
Bei beiden Konstellationen nimmt der Anteil gewonnener Spiele mit wachsender Anzahl an Monte Carlo Simulationen zu.
Eine Ausnahme bildet das untere Ende der Simulations-Anzahlen: bei 0 Simulationen, also Bewertung lediglich nach der hinzugezogenen Heuristik, hat der Anteil gewonnener Spiele wieder zugenommen.
Aus den Versuchsergebnissen lässt sich nicht ableiten, dass Volatile Game Tree Search der perfekte Algorithmus für Chain Reaction ist, jedoch ist er dem Minimax-Algorithmus. bei einer ausreichenden Zahl an Monte Carlo Simulationen, mindestens ebenbürtig und dabei ressourcensparender als MCTS.
¶ Ausblick
Da Chain Reaction im Vergleich zu anderen prominenteren Brettspielen noch relativ unerforscht ist, gibt es noch viel Raum für zukünftige Forschung.
Denkbar wären größere Suchtiefen, erweiterte --Suchfenster oder auch die Anwendung von Deep-Learning, das vor rund 20 Jahren, als Chain Reaction untersucht wurde, noch nicht so ausgereift wie heute war.
¶ Anmerkungen
Die bei den Präsentationen im Seminar präsentierten Spielregeln weichen leicht von denen im Paper und Wiki-Artikel ab.
¶ Bildquellen
Abb. 1: Screenshot aus dem Mobile Game 2 Player Games The Challenge
Abb. 2: Editierte Bildschirmaufnahme aus dem Mobile Game 2 Player Games The Challenge
Abb. 3: Bildschirmaufnahme aus dem Mobile Game 2 Player Games The Challenge
Abb. 4: Bildschirmaufnahme aus dem Mobile Game 2 Player Games The Challenge
Abb. 5: Selber erstellt
Abb. 6: Selber erstellt
Abb. 7: Übernommen aus dem Paper Highly Volatile Game Tree Search in Chain Reaction[1:4]
Abb. 8: Übernommen aus dem Paper Highly Volatile Game Tree Search in Chain Reaction[1:5]
¶ Referenzen
Jenkins, D., & Frayn, C. (2006, May). Highly Volatile Game Tree Search in Chain Reaction. In 2006 IEEE Symposium on Computational Intelligence and Games (pp. 217-223). IEEE. IEEE ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
v. Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100(1), 295-320.Springer ↩︎
Coulom, R. (2006, May). Efficient selectivity and backup operators in Monte-Carlo tree search. In International conference on computers and games (pp. 72-83). Berlin, Heidelberg: Springer Berlin Heidelberg. Core ↩︎