Nim - Zugsuche mit MiniMax
Nim ist ein zwei Personenspiel. In der einfachsten Variante werden von einem Haufen von 13 Streichhölzern abwechselnd wahlweise 1 bis 3 Hölzer
entfernt. Der Spieler, der das letzte Streichholz nimmt, hat gewonnen. Varianten mit mehr oder wenigern Streichhölzern, in einem oder mehren
Haufen, anderer Wegnahmeregel und gegenteiliger Gewinnbedingung sind möglich.
Nim ist als Einstieg prima geeignet. Das Spiel kann gut ohne Graphik dargestellt werden. Der Suchbaum ist klein, Threads sind unnötig.
Man kann eine optimale Strategie angeben und prüfen, ob das Suchverfahren sie findet.
Was wird benutzt?
Das Programm wird mit dem MS Visual Studio 12 mit C# als Konsolenanwendung entwickelt. Der Baum möglicher Züge/Stellungen wird rekursiv mit MiniMax durchsucht/erzeugt.
Was wird alles implementiert?
Eine Übersicht über alle implementierte Klassen, ihre Abhängigkeiten, Variablen, Funktion usw. bietet das Klassendiagramm.
Das Programm
Die wesentliche Funktion der Main Methode liegt darin, eine Instanz der Game Klasse zu halten und sie in der do while Schliefe zu initalisieren und zu starten.
Die Game Klasse
Sie hält die Spieler und das Spielfeld. Ihre Aufgabe besteht in der Initalisierung und Ausführung des Spieles.
In der Run Methode findet sich die initiale Darstellung des Spielfeldes (board.DrawBoard())
und die eigentliche Spielschliefe. Man beachte, dass die Spielschleife nicht vor Ende des Spiels zurückkehrt. Das legt in komplexeren Spielen
die Verwendung eines Threads nahe, da ansonsten die Bedienung des Programms behindert wird.
In der Schleife wird der Spielzug des aktuellen Spielers geholt und angezeigt bzw. intern ausgefuhrt. Anschließend wird die aktualisierte Darstellung des Spielfeldes
angezeigt.
Die Board Klasse
Die Board Klasse ist 'Spiel global' d.h. alle Klassen, die auf das Board zugreifen, nutzen die einzige existierende Instanz. Ihre Aufgabe besteht in der Initialisierung, der (internen) Ausführung und Rücknahme von Zügen und der Darstellung des aktuellen Zustandes. Da insbesonders die Zugsuche das 'globale' Board nutzt und verändert, ist die Funktion der Zugrücknahme unverzichtbar. Siehe MiniMax bei PlayerComputer.
Die PlayerBase Klasse
Diese Klasse ist Basisklasse aller Spieler. Sie enthält als Felder die Stellungsbewerung, den besten / aktuellen Zug, das Board und den Namen des Spielers.
Die PlayerHuman Klasse
Diese Klasse repräsentiert den menschlichen Spieler. Ihre wesentliche Aufgabe ist Abfrage eines Zuges und dessen Prüfung auf Einhaltung der Spielregeln. Falls dem so ist, wird dieser an den Aufrufer zurückgegeben.
Die PlayerComputer Klasse
Der PlayerComputer nutzt das Minimax Verfahren zur Zugsuche. Es ist ein indirekt rekursives Verfahren zur Tiefensuche. Es erzeugt/durchsucht den
Spielbaum aller möglichen Züge/Stellungen
bis zu den Blättern oder einer vorgegeben Tiefe. Die Blätter werden bewertet. Diese Bewertung wird nach oben im Spielbaum weitergereicht.
Üblicherweise erfolgt der Einstieg in die Zugsuche als maximierender Spieler(22) mit dem aktuellen Zugrecht und der beabsichtigten Suchtiefe.
Da er versucht eine möglichst hohe Bewertung zu erhalten, ruft er die Max Methode auf.
Zuerst wird geprüft, ob ein weiterer Zug möglich ist(28). Falls nicht, wird die Bewertung an den Aufrufer zurückgegeben(29). Andernfalls
wird die Bewertung mit einem möglichst kleinem Wert, den es im Laufe der Suche zu übertreffen gilt(37, 39), initialisiert(30).
Als nächstes wird die Liste aller möglichen Züge vom Zuggenerator geholt(31). Diese Liste wird in der Schliefe Zug für Zug abgearbeitet.
Zuerst wird der Zug auf dem 'globalen' Board ausgeführt(34), um im Anschluss mit geändertem Zugrecht und der um 1 verringerten Suchtiefe
die Min Methode zu bemühen(35). Zur Min Methode etwas später. Nach einiger Zeit kehrt die Min Methode zurück und liefert einen Stellungswert.
Dann wird der zuvor ausgeführte Zug zurückgenammen(36). Falls der zurückgegebene Stellungswert besser als der bisher erreichte ist, wird er gespeichet(37, 39).
Falls die Suche an der Wurzel(der Einstiegsstellung für die Suche) ist, wird der Zug, der offensichtlich zur bis jetzt besten Stellungsbewertung führte
gespeichert(40,41). Sind alle Züge aus der Liste des Zuggenerators abgearbeitet, kehrt die Max Methode mit ihrem besten Wert zurück(44).
Die Min Methode verhält sich sehr ähnlich. Sie unterscheidet sich in der Initialisierung ihres besten Wertes(51), sie ruft die Max Methode auf(56)
und sie speichert keine besten Züge, da sie nie direkt an der Wurzel sein kann.
Die Min und Max Methoden sind sich so ähnlich, dass sie geradezu darum flehen vereinigt zu werden. Das spart Code und verringert den Pflegeaufwand.
Das NegaMax Verfahren ist dann das Mittel der Wahl.
Die Move Klasse
Eine Klasse Move zu erzeugen, erscheint vielleicht etwas überdimensioniert, da sie hier nur aus einem Konstruktor und einer integer Eigenschaft besteht. Da jedoch in anderen Spielen ein Zug deutlich komplexer sein kann, scheint es angemessen diese Klasse schon jetzt einzuführen.
Die MoveGenerator Klasse
Die Aufgabe des Zugeneraturs besteht darin, eine Liste mit allen auf dem aktuellen Board möglichen regelgerechten Zügen zu füllen und diese Liste an den Aufrufer zurückzugeben. Zu diesem Zweck ist das Board hier als Feld und die Kodierung der Zugregeln im Schleifenkopf implementiert.
