¶ Einleitung
Vier gewinnt (englisch: Connect Four) ist ein Zweipersonen-Strategiespiel mit dem Ziel, vier eigene Spielsteine in eine Linie zu bringen.
Entwickelt wurde es von Howard Wexler und 1974 in den USA von Milton Bradley(später Hasbro) vertrieben. [1]
¶ Spielregeln
¶ Aufbau
Die am meisten verbreitete Variante ist ein Spielfeld mit sechs Reihen und sieben Spalten. Genau diese Standartgröße wurde auch in dem zugrunde liegenden Paper untersucht.[2]
Es existieren weitere Varianten wie z.B. ein Spielfeld mit 5x5 oder 8x8 Feldern. Diese sind jedoch nicht Gegenstand der Untersuchungen in dem Paper,
¶ Spielablauf
Es spielen 2 Spieler gegeneinander, welche abwechselnd einen ihrer Steine in eine der Spalten setzen. Der Stein fällt in der Spalte soweit nach unten, bis er auf einem anderen Stein oder dem Boden aufliegt
Wenn ein Spieler 4 in einer Reihe hat (senkrecht, waagerecht oder diagonal), hat dieser gewonnen. Wenn alle Felder belegt sind und kein Spieler das Ziel erreicht hat, geht das Spiel unentschieden aus.
Auch hier gibt es alternative Varianten, z.B. dass die unterste Reihe ähnlich wie bei Tetris verschwindet, wenn sie voll ist, welche aber nicht weit verbreitet und auch nicht Teil der Untersuchung sind.
¶ Grundlage der Forschung
In dem Paper "Monte-Carlo Tree Search and Minimax Hybrids" von Hendrik Baier und Mark H.M. Winands wird untersucht, ob ein Hybrid aus Monte-Carlo Tree Search (MCTS) und Minimax besserer Ergebnisse liefert als eine reine MCTS Implementation.
Der Grund ihrer Annahme, dass dies der Fall sein könnte, ist, dass die MCTS zwar langfristig gute Strategien findet, aber kurzzügige Fallen (Shallow Traps) übersieht, da diese nicht garantiert in den zufälligen Simulationen auftauchen.
Um das zu testen haben sie den MCTS-Solver 1000-mal gegen sich selber spielen lassen und nach jedem Zug geguckt, ob es eine Falle in 3 oder weniger Zügen gibt, welche zu einer sicheren Niederlage führt.
Wie man in der Abbildung 1 sieht, gibt es schon ab dem 20. Zug in ca. 50% der Positionen eine solche Falle und es werden mit jedem Zug mehr.
Dieses häufige Auftreten von Shallow Traps lässt stark darauf schließen, dass der Einsatz von Minimax den Algorithmus stark verbessern würde, da Minimax kurze taktische Fallen zuverlässig erkennen kann.
¶ Experiment Setup
Um die Ergebnisse einordnen zu können ist es wichtig, was im Paper genau als Baseline verwendet wird:
- Als Vergleich dient nicht nur MCTS, sondern ein MCTS mit Solver Erweiterung, der "proven win/proven loss" propagieren kann, sobald terminale Zustände im Suchbaum erreicht werden. [2]
- Für die Auswahl im Suchbaum wird die klassische UCT Strategie (UCB1-Prinzip) eingesetzt
- Es wird bewusst ohne Heuristiken oder Evaluationsfunktionen gearbeitet. Minimax kann daher innerhalb der betrachteten Tiefe nur sichere Gewinne/Niederlagen erkennen. Ansonsten bleibt der Zustand "nicht bewiesen".
- Standartmäßig beträgt die Rechenzeit 1 Sekunde pro Zug. Unentschieden werden als halber Sieg gewertet.
¶ Einsatz von Minimax
Es ist nun klar, dass der Einsatz von Minimax den Algorithmus verbessern wird, die Frage ist nur, in welcher Phase der MCTS es am meisten Sinn ergibt. im Paper wurden die folgenden 3 Varianten untersucht.
¶ Minimax in der "Rollout" Phase (MCTS-MR)
In der Baseline wird einfach ein zufälliger Zug (Knoten) gewählt. Stattdessen wird nun wird Minimax mit Tiefe 1-4 eingesetzt. Da es keine Heuristiken gibt, kann Minimax nur einen sicheren Sieg oder eine Niederlage finden. Falls keins von beidem zutrifft, also das Spiel noch nicht terminiert ist, wird dann doch einfach ein zufälliger Knoten gewählt.
¶ Minimax in "Selection and Expansion" (MCTS-MR)
Bei MCTS-MR wird Minimax direkt beim Aufbau und Durchlaufen des Suchbaums genutzt. Als Kriterium, wann Minimax eingesetzt wird, haben sie die Anzahl der Besuche pro Knoten gewählt. Sobald ein Knoten eine Besuchszahl erreicht, wird für diesen Zustand Minimax Tiefe gestartet (otation: MCTS-MS--Visit-)
Es gibt auch andere Kriterien, diese haben sie aber außenvor gelassen und sind eventuell Stoff für zukünftige Forschungen. Außerdem wollen Sie in dieser Phase nur erzwungene Niederlagen finden und da man sich selbst nicht schachmatt setzen kann, wird also nur Tiefe 2 und 4 betrachtet.
¶ Minimax in der "Backpropagation" Phase (MCTS-MB)
Als dritte Variante wird Minimax in der Backpropagation Phase eingesetzt, also wenn MCTS Ergebnisse einer Simulation im Baum nach oben zurückmeldet. Als Baseline wird ja ein MCTS-Solver genutzt, der bewiesene Werte (proven win / proven loss) propagieren kann, wenn terminalzustände erreicht sind. Allerdings braucht es oft viele Simulationen, um das für alle Kinder durch reine MCTS zu ermitteln. Hier soll Minimax eingesetzt werden, um möglichst früh zusätzliche proven loss Informationen zu finden um daraus proven win abzuleiten und nach oben zu propagieren. Dadurch sollen unnötige weitere Simulationen in bereits "eigentlich entschiedenen" Teilbäumen vermieden werden.
¶ Ergebnisse
¶ Minimax in der "Rollout" Phase
¶ Tiefe 1
Bei Tiefe 1 sinkt die Gewinnrate deutlich auf ca. 32%, schneidet also sogar schlechter ab, als die Baseline. Das können sich die Autoren auch nicht genau erklären, haben es aber auch erstmal nicht weiter untersucht und geben es als Denkanstoß für zukünftige Forschungen aus.
¶ Tiefe 2
Bei Tiefe 2 sehen wir nun aber einen deutlichen Anstieg der Gewinnrate auf ca. 72%. Der Algorithmus schafft zwar nur noch ca. 18% der Simulationen im Gegensatz zur Baseline, aber Minimax macht das so effektiv, dass es sich deutlich lohnt.
¶ Tiefe 3-4
Bei Tiefe 3 und 4 sinkt die Spielstärke wieder. Es wird nur noch 57% bzw. 50% Gewinnrate erzielt, was daran liegt, dass Minimax zu teuer wird. Es können nur noch 6% bzw. 2% der Simulationen durchgeführt werden in der Sekunde Rechenzeit, was der Vorteil von Minimax nicht genug kompensieren kann.
¶ Minimax in der "Selection and Expansion" Phase
¶ Minimax in der "Backpropagation" Phase
In der Backpropagation Phase wird Minimax nicht als permanenter Bestandteil jeder Simulation genutzt, sondern gezielt dann, wenn ein terminaler Zustand gefunden wurde und zusätzliche proven Informationen benötigt werden.
Es wurde mit Tiefen 1-6 getestet und auch die ungraden Tiefen. Auch hier war die Erfolgreichste Einstellung die mit Tiefe 2. 52,1% der Spiele wurden damit gewonnen, womit alle 3 Varianten besser abschneiden als die Baseline.
¶ Vergleich
Neben dem Vergleich gegen die Baseline betrachtet das Paper zum Schluss noch den Vergleich der Varianten untereinander. In Abbildung 5 sieht man an den hellgrauen Balken, wie die Algorithmen gegeneinander abschneiden, auch da ist der Hybrid mit Minimax in der Rolloutphase am erfolgreichsten.
Man sieht außerdem an den dunkelgrauen Balken, welche das gleiche Experiment am beim Spiel Breakthrough darstellen, dass diese Ergebnisse nicht 1:1 auf alle Spiele anwendbar sind, sondern man von Spiel zu Spiel andere Hybride mit anderen Parametern betrachten muss.
¶ Fazit
Das Paper zeigt für Vier gewinnt klar: Gezielte, flache Minimax Suchen können MCTS spürbar verbessern, auch ohne Heuristiken oder Evaluationsfunktionen.
Besonders stark ist es, Minimax in der Rollout Phase zu nutzen. Damit wurden über 70% der Spiele gewonnen. Aber auch in allen anderen Varianten wurden Verbesserungen erzielt, wenn auch deutlich geringer.
Der wichtigste Punkt ist dabei die Balance. Minimax bringt nur dann einen Vorteil, wenn die Parameter so gewählt werden, dass noch genug Ressourcen für MCTS übrig sind. Die gefundenen Optimale sind also stark von Rechenleistung und Rechenzeit abhängig, welche in dem Experiment genutzt werden.
¶ Weiterführende Fragen
- Warum ist MCTS-MR mit Tiefe 1 schlechter als die Baseline?
- Was passiert, wenn man zusätzlich noch eine Bewertungsfunktion einführt?
- Wie stark hängen die Ergebnisse von den Eigenschaften des Spiels ab?
- Welche anderen Trigger Kriterien für MCTS-MS könnten sinnvoll sein?
¶ Bildquellen
- Abbildung 1-5: Diagramme/Plots aus dem Paper "Monte-Carlo Tree Search and Minimax Hybrids" von Baier & Winnands)
¶ Literatur
- https://de.wikipedia.org/wiki/Vier_gewinnt
- Baier, Hendrik, and Mark HM Winands. "Monte-carlo tree search and minimax hybrids." 2013 IEEE Conference on Computational Inteligence in Games (CIG). IEEE, 2013. pdf