Mühle - Der perfekt spielende Computer

Spielbeschreibung:

Das Spielbrett des Mühlespiels umfasst 24 Felder, bei denen zwei Spieler abwechselnd zum Zug kommen. Der Spielablauf besteht aus drei Phasen:
Die Anfangsphase: Abwechselnd setzt jeder Spieler einen seiner neun Spielsteine auf ein freies Feld. Wird eine Mühle geschlossen so darf er einen Stein des Gegners entfernen, sofern dieser nicht Teil einer Mühle ist. Die Zugphase: Abwechselnd zieht jeder Spieler einen beliebigen eigenen Stein entlang einer der 24 Verbindungslinien. Beim Schließen einer Mühle wird auch hier wieder ein beliebiger Stein des Gegners entfernt, der nicht Teil einer geschlossenen Mühle ist. Die Springphase: Sobald ein Spieler nur noch drei Stein besitzt darf er beim Ziehen auf ein beliebiges freies Feld springen. Eine Mühle gilt als geschlossen, wenn drei gleichfarbige Steine in einer Reihe angeordnet sind.

Prinzip des perfekt spielenden Mühle-Computers:

Das Prinzip des perfekt spielenden Mühle-Computers basiert auf einer Datenbank, die Informationen über jede mögliche Spielsituation enthält. Jede Spielsituation ist dabei aus der Perspektive des Spielers, der gerade am Zug ist, zu betrachten. Die gespeicherte Information pro Spielsituation besteht aus „Situationswert“ und der Mindestanzahl an Zügen, die zum Gewinn, bzw. der Maximalanzahl an Zügen bis das Spiel verloren ist, hier „Zuganzahlwert“ genannt. Der Situationswert kann folgende vier Werte annehmen:

+,	wenn es unabhängig von den Aktionen des Gegners möglich ist zu gewinnen,
0,	wenn der Spielausgang unentschieden ist,
-,	wenn der Gegner durch perfektes Spielen gewinnen kann.
x,	wenn der Situationswert noch nicht berechnet worden ist oder die Situation ungültig ist.

Wie kann nun der perfekte Zug anhand dieser Informationen abgeleitet werden? Nehmen wir eine beliebige Spielsituation an, die den Situationswert '+' hat. Folgende Abbildung zeigt für diese Situation vier mögliche Züge sowie den Situationswert nach jedem dieser vier Züge. Hier wird ersichtlich, dass die Durchführung des zweiten oder des vierten Zuges angestrebt werden sollte, da diese zu Spielsituationen führen die aus der Sicht des Gegners verloren zu sein scheinen.



Nach dem gleichen Prinzip ist es auch für Situationen mit den Wert '0' möglich, den perfekten Spielzug zu ermitteln, während es für Situationen mit dem Wert '-' irrelevant ist, welcher Spielstein bewegt wird, da der Gegner bei perfektem Spiel so oder so gewinnen wird. Die hier zur Berechnung der Datenbank verwendeten Algorithmen sind zum einen der Minimax-Algorithmus und zum anderen die Retro-Analyse.

Benutzeroberfläche:

Der jeweilige Ausgang eines jeden Zuges wird mit einem der folgenden drei Symbole sowie 4 Zahlen gekennzeichnet:

5 | 0 | 0 | 22		Gewonnenes Spiel in 22 Zügen - Der nächste Zug beinhaltet 5 und keine bzw. . Der nächste Zug wird vom Gegenspieler ausgeführt, sofern keine Mühle geschlossen wird.
4 | 1 | 0 | -		Unentschieden - Der nächste Zug beinhaltet 4 und keine . Hierbei ist natürlich keine Anzahl Züge angegeben, da ein Unentschieden unendlich lange ist.
0 | 11 | 2 | 7		Verlorenes Spiel in 7 Zügen - Der nächste Zug beinhaltet 11 und 2 .

Im folgenden Bild wurde der perfekte Zug in der vorigen Abbildung, Schieben des unteren schwarzen Steines nach links, durchgeführt. Zu erkennen ist nun die ausweglose Situation des Gegenspielers, d.h. jede seiner 6 Zugmöglichkeiten wird mit einem roten Minus markiert. Um dennoch den Gegner zu möglichst vielen Zügen zu zwingen, sollte er den weißen Stein rechts unten bewegen.

Downloads:

Exe-Datei (ACHTUNG: Datenbank muss ebenfalls heruntergeladen werden.):
MuehleWin_Executable_ver1.0.zip (Version 1.0, 1. Januar 2019, Win10, DirectX 11)

Datenbank (ACHTUNG: 8,3 GB !!!):
MuehleWin_Database_ver1.0.zip (Version 1.0, 1. Januar 2019, 8'300 MB)

Quellcode:
GitHub repositories Muehle und weaselLibrary

Dokumentation:
Der perfekte Mühle-Computer.pdf (1. Dez 2009)