TicTacToe

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, muß 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 muß 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, muß 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 Auswahl von 2 Spielertypen (Max und Min) ermöglichen. (2 Comboboxen weil für Max- und Minspieler mehrere unterschiedliche Suchverfahren wählbar sein sollen.)
  • Informationen über den aktuellen Spielzustand anzeigen können. (Textblock)
  • das Spiel starten und beenden können. (Start- und Quitbutton)
  • das Spielfeld darstellen. (Canvas)
  • ein Protokoll mit Information der letzten Zugsuche anzeigen. (ListView)
  • Eingaben des menschlichen Spielers annehmen. (MausClick Handler am Spielfeld Canvas)
  • jederzeit bedienbar sein. (GameLoop im Thread)
  • die Oberflächenelemente beschriften und anordnen. Dazu braucht es Grids und Labels.
  • 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

Der zugehörige Code behind gestaltet sich so:

Quelltext ein-/ausblenden

Um überhaupt irgendwie spielen zu können, müssen die Game, Board und PlayerHuman Klassen vollständig implementiert werden.

Was muß die Game Klasse können?

Sie muß:

  • auf Spielstart und -ende Button der Oberfläche reagieren. (Start, Abort)
  • die gewählten Spielertypen handeln. (GetActivePlayer)
  • den Spielablauf regeln (Zugrechte verteilen, Züge wählen, das Spielfeld aktualisieren, Protokoll schreiben) und dabei NICHT die Bedienung des Programms behindern. Sie soll daher einen Thread für die Gameloop starten.

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 im thread laufenden Gameloop sind diverse delegates und die Kenntnis des Hauptfensters nötig. Das geht so:

Quelltext ein-/ausblenden

Wie ist das Board organisiert?

Das Board erfüllt zwei wesentliche Funktionen.

  1. Es speichert die zur Zugsuche notwendigen Daten. Das sind:
    • das Zugrecht (playerHasToMove)
    • die Boardbelegung als 3 Bitboards (playerMaxPieces, playerMinPieces, usedCells)
    • 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)
    • Bitmasken für ein leeres und gefülltes Spielfeld, sowie eine Liste für Masken von Gewinnpositionen.(EmptyBoard, FilledBoard, winningPositions)
    • einen struct mit den Zuginformationen.(Move)
    • und eine Funktion, die einen Zug auf dem internen Brett ausführt(Do). Wegen der schönen XOR Eigenschaften kann man mit der gleichen 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)
  2. und es ist in der Lage, seine internen Daten graphisch im Canvas darzustellen. Dazu nutzt es Draw Funktionen
    • zur Zellbeschriftung mit Indexnummern.
    • zum Zeichnen der Feldtrennlinien.
    • zum Malen der Spielsteine.

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