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.

Nim 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.

Quelltext ein-/ausblenden

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.

Quelltext ein-/ausblenden

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.

Quelltext ein-/ausblenden

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.

Quelltext ein-/ausblenden

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.

Quelltext ein-/ausblenden

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.

Quelltext ein-/ausblenden

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.

Quelltext ein-/ausblenden

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.

Quelltext ein-/ausblenden