TicTacToe - Varianten der NegaAlphaBeta Zugsuche und notwendige Klassen

Die Regeln

TicTacToe wird auf einem 3X3 Feld gespielt. Es wird abwechselnd gezogen. Der Spieler, der zuerst 3 Spielsteine in einer diagonalen, vertikalen oder horizontalen Reihe anordnet, hat gewonnen und beendet damit unmittelbar das Spiel. Ansonsten endet das Spiel, wenn kein weiterer Zug möglich ist, unentschieden.

Wie groß ist das Problem?

Jedes Feld kann drei Zustände annehmen: leer, MaxStein, MinStein. Das Feld kann also 39 = 19683 verschiedene Zustände einnehmen. Wie kann es gefüllt werden? Für die Position des ersten Steins gibt es 9 Möglichkeiten, für den Zweiten 8, für den Dritten 7 usw.. Es kommen also 9! = 362880 verschiedene Zugmöglichkeiten in Betracht. Weil diese Züge in unterschiedlicher Reihenfolge ausgeführt werden können, muss ein Baum mit (laut Programm) 549945 Stellungen untersucht werden. Für heutige Rechner ist es kein Problem diese Varianten vollständig durchzurechnen. Außerdem ist da noch ordentlich Platz für Optimierungen: Es gibt z.B. für den ersten Zug nur 3 prinzipielle Positionen, alle anderen lassen sich durch Rotation oder Spiegelung des Spielfeldes erreichen.

Wie löst man das Problem?

Man muss eine Möglichkeit schaffen, alle Züge auszuführen und zu bewerten. Üblicher Weise wird wie folgt bewertet: Gewinnt Spieler Max, erhält die Stellung den Wert +1, Gewinnt Spieler Min, erhält die Stellung den Wert -1, bei Unentschieden erhält die Stellung den Wert 0. Der eine, der Max Spieler, hat die Aufgabe den Stellungswert zu maximieren. Sein Gegner, der Min Spieler, muss den Stellungswert minimieren.

Da auf jeden Zug in der Regel mehrere Antwortzüge möglich sind, ergibt sich ein verzweigter Baum, bei dem die Kanten Züge und die Knoten Stellungen entsprechen.

Im folgenden Bild ist ein Ausschnitt eines auf diese Art erzeugeten Baumes zu sehen. Min (Rot) hat gesetzt, Max (Blau) hat das Zugrecht. Eine bestimmte Stellungsfolge ergibt sich, von der Startstellung (Wurzel) entlang der Kanten bis zum jeweiligen Blatt.

Ausschnitt des TicTacToe Suchbaumes
Ausschnitt des TicTacToe Suchbaumes

Schwarze Ziffern stellen Ergebnisse der Stellungsbewertung des Blattes dar, rote Ziffern sind im Baum von unten nach oben weitergereichte Stellungswerte.
Max wählt den Zug mit der höchsten Bewertung in der tieferen Ebene, Min den mit der niedrigsten. Bei gleich guten wird der Erste gewählt. Das Spiel wird unentschieden enden.

Es gibt zwei Möglichketen den Baum zu untersuchen. Die Breitensuche, die jeweils die Stellungen in einer Ebene untersucht (unter Umständen sehr hoher Speicherbedarf) oder die Tiefensuche, die jeweils einen Pfad von der Wurzel bis zum Blatt untersucht.

Hier wird die Tiefensuche verwendet. Der MiniMax bzw. AlphaBeta Algorithmus und deren Erweiterungen bewerkstelligen genau das. Schöne Artikel finden sich in der Wikipedia zur Minimax- und AlphaBetasuche.

Was wird benutzt?

Das Programm wird mit dem MS Visual Studio 12, WPF und C# entwickelt. Bäume werden rekursiv untersucht. Das Spielfeld wird wegen der enormen Rechenzeitvorteile als Bitboard realisiert. Daher kommen logische Verknüpfungen auf Bit Ebene vor. Arrays, Listen, Maps und Hashtables sind wichtig. Delegates werden hauptsächlich wegen der thread übergreifenden Aufrufe vom Spiel zur Oberfläche vorkommen.

Was wird alles implementiert?

Eine Übersicht über alle implementierte Klassen, ihre Abhängigkeiten, Variablen, Funktion usw. bietet das Klassendiagramm.

Tic Tac Toe Klassendiagramm

Wie anfangen?

Ich mag die Top-Down Entwicklungsstrategie und beginne mit der Frage: Was soll das Programm können und welche Oberflächenelemente werden dazu benötig? Es soll:

Tic Tac Toe UserInterface
Die Oberfläche
  • die Oberflächenelemente (Ribbon, Canvas, Listview) anordnen. (Grid)
  • die Auswahl von 2 Spielertypen (Max und Min) ermöglichen. (2 RibbonComboboxen weil für Max- und Minspieler mehrere unterschiedliche Suchverfahren wählbar sein sollen.)
  • Informationen über den aktuellen Spielzustand anzeigen können. (Label im Ribbon)
  • das Spiel starten und beenden können. (Button im Ribbon)
  • das Spielfeld darstellen. (Canvas)
  • ein Protokoll mit Information zu den Zügen anzeigen. (ListView)
  • Eingaben des menschlichen Spielers annehmen. (MausClick Handler am Spielfeld Canvas)
  • jederzeit bedienbar sein. (GameLoop im Thread)
  • die eigentliche Spiel Klasse enthalten.

Mit WPF im MS Visual Studio bekommt die Oberfläche dieses Aussehen. Der Code wird vom Visual Studio erzeugt, wenn man die Elemente im Editor setzt. Einzig die Zeilen 6 - 20 (Window.Resources) sind händisch erzeugt und dienen dazu, die Zeilen im Listview abwechseln zu färben. Der zugehörige XAML Code sieht so aus:

Quelltext ein-/ausblenden

Im zugehörigem Code behind werden

  • die globale Game und Board Klasse gehalten,
  • die Kommunikation der Game- und der SearchHumanKlasse mit den Oberflächenelementen (Comboboxen, Buttons, Listview, Canvas usw.) hergestellt und
  • auf Useranforderungen zu reagiert.
Diese Aufgaben werden über die On...(object sender, ...EventArgs e) Eventhandler wahrgenammen. Sie gestaltet sich so:

Quelltext ein-/ausblenden

Um überhaupt irgendwie spielen zu können, müssen mindestens die Game, Board, MoveGenerator, Move, SearchHuman, EvaluateMinMax und Player Klassen vollständig implementiert werden.

Was muss die Game Klasse können?

Sie muss:

  • auf Spielstart und -ende Button der Oberfläche reagieren. (Start, Abort)
  • die gewählten Spielertypen handeln. (Start Parameterübergabe)
  • das Board auf Startzustand setzen.
  • den Spielablauf in der Gameloop regeln (Zugrecht, Zugsuche starten, via Nachrichten Oberfläche aktualisieren) und dabei NICHT die Bedienung des Programms behindern. Die Gameloop soll daher einen Thread laufen.

Für diese Aufgaben kennt die Game Klasse:

  • den aktuelle Gamestatus,
  • die Spieler und
  • das Spielfeld

Wegen der Zugriffe auf die Anwendungsoberfäche aus der Gameloop sind diverse Delegates und Events nötig. Das geht so:

Quelltext ein-/ausblenden

Wie ist das Board organisiert?

Die wesentliche Aufgabe des Boards besteht darin, die zur Zugsuche notwendigen Daten zu speichern. Das sind:

    • das Zugrecht (maxPlayerHasToMove)
    • die Boardbelegung als 3 Bitboards (playerMaxPieces, playerMinPieces, usedCells)
    • Bitmasken für ein leeres und gefülltes Spielfeld, sowie eine Liste für Masken von Gewinnpositionen.(EmptyBoard, FilledBoard, winningPositions)
    • Funktionen, die einen Zug auf dem internen Brett ausführt(Do) und zurücknimmt(Undo). Wegen der schönen XOR Eigenschaften kann man mit der Do Funktion den Zug auch rückgängig machen. Der besseren Lesbarkeit wegen wird ein delegate mit dem Namen 'UnDo' erzeugt und diesem die Do Funktion zugewiesen.(DelegateUnDo)
    • einen (Zobrist)Schlüssel, der das ganze Board repräseniert und später fürs hashing verwendet wird. (boardKey)
    • 2 Listen mit Zufallswerten für die Spielsteine, mit denen der Schlüssel erzeugt wird. JEDER Zufallswert repräsentiert EINEN Spielsteintyp EINER Partei auf EINER bestimmten Position. Es sind also 2 Parteien * 1 Steintyp * 9 Positionen = 18 Zufallswerte nötig.(keyPlayerMinPiecesPos, keyPlayerMaxPiecesPos)

Bitboards sind bei TicTacToe nicht unbedingt notwendig. Sie werden hier aber zum Training benutzt. Was sind die Vorteile von Bitboards?

  • Sie sind klein im Vergleich mit Arrays.
  • Sie sind enorm schnell beim Zugriff im Vergleich mit Arrays, weil keine Adressberechnung nötig ist.
  • Mit Bitmasken kann man mit EINEM Vergleich mehrere Steinpositionen abfragen. (z.B. die Gewinnpositionen)
  • Züge werden mittels logischer Operationen ausgefüht. Bei Arrays müssten Feldinhalte geändert werden, was Zuweisungen und Adressberechnungen notwendig macht.

Leider sind Bitboards auch gewöhnungsbedürftig und im Gegensatz zum Array nicht so intuitiv. Aus diesem Grund haben die Spielfelder auch Indexnummern, die mit dem jeweiligen Bitindex im Bitboard übereinstimmen. Die Zuordnung von Feld zu Bitindex ist beliebig und richtet sich danach, was fürs Programm (Züge setzten) oder fürs eigene Denken am praktischsten ist.

Quelltext ein-/ausblenden

Wie alle Spieler grundsätzlich sind.

Die Player Base Klasse

Die PlayerBase Klasse ist, wie der Name schon sagt, Basis aller Player Klassen. Für die PlayerHuman und PlayerRandom Klasse ist lediglich die Fähigkeit, sich den letzten Zellenindex und das Board zu merken, von Bedeutung. Alle anderen Klassen nutzen zusätzlich den Zuggenerator, der alle (in der aktuellen Spielsituation) möglichen Züge in eine Liste scheibt, die während der Zugsuche abgearbeitet wird. Wichtig: der jeweilige Zug wird ohne Vertiefung (statisch) bewertet, um später eine Sortierung der Züge zu ermöglichen. Die Qualität dieser Bewertung ist von zentraler Bedeutung für die Beschleunigung der Suchverfahren, die von einer Zugsortierung Gebrauch machen. Es kann von erheblichem Vorteil sein, zwei unterschiedliche Bewertungsverfahren für die statische (hier) und die dynamische Bewertung (am Blatt) zu nutzen. Im Idealfall liefern beide den selben (korrekten) Wert. Leider wird das kaum gelingen. Wäre das möglich, könnte man sich den Aufwand mit der Suche klemmen. Grobe Abweichungen in der Bewertung sind aber dringend zu vermeiden. TicTacToe nutzt nur ein Bewertungsverfahren.

SearchMove und Evaluate sind abstract damit jedes Suchverfahren seine eigene Variante nutzen kann.

Quelltext ein-/ausblenden

Der menschliche Faktor.

Der human Player ist einfach gestrickt. Im Wesentlichen wartet er nur auf eine Eingabe, überprüft ihre Gültigkeit und führt gegebenenfalls den Zug auf dem Board aus.

Quelltext ein-/ausblenden

Der Gegner NegaAlphaBeta

Die Klasse PlayerNegaAlphaBeta besteht aus drei Funktionen. SeachMove ruft den eigenlichen NegaAlphaBeta auf und führt den gefundenen Zug aus. Evaluate bewertet die Blätter des von NegaAlphaBeta erzeugten Baumes. Ein Blatt ist erreicht, wenn die maximale Suchtiefe erreicht oder kein weiterer Zug möglich ist. Zentral ist die Funktion NegaAlphaBeta. Ihr Arbeitspferd ist die foreach Schliefe, die nacheinander alle Züge des Zuggenerators abarbeitet. Zu diesem Zweck führt sie den Zug aus und ruft sich selbst wieder auf. Jedes Mal, wenn sie aus der Rekursion zurückkommt nimmt sie den vorher ausgeführten Zug zurück, so daß bei vollständiger Rückkehr das Board wieder im ursprüngichen Zustand ist. Sie merkt sich den Zug als besten Zug, der auf der obersten Rekusionsebene zur besten Bewertung führt.

Quelltext ein-/ausblenden

Der Gegner NegaAlphaBeta mit Zugsortierung und Transpositions Hashtable

Man ahnt es bereits: diese Klasse unterscheidet sich kaum von der vorherigen. SearchMove unterscheidet sich nur in einer Zeile wegen der Transpositionstabelle. Evaluate ist identisch. Die Funktion hätte man auch in PlayerBase ausformulieren können. Ist aber nicht passiert, um die Möglichkeit zu haben, in späteren Projekten gleiche Suchalgorithmen mit unterschiedlichen Bewertungsfunktionen zu testen. Hauptunterschiede sind in der Funktion 'NegaAlphaBetaSortTrans'. Sie betreffen Zugriffe auf die Transpositionstabelle und die Sortierung der vom Zuggenerator gelieferten Züge.

Quelltext ein-/ausblenden

Kommentar(e)

Kommentarformular ein-/ausblenden