nclskfm
commented
3 years ago Endspieldatenbank
Eine Endspieldatenbank enthält vollständiges Wissen über ein Spielbrett mit einer maximalen Anzahl an Steinen auf dem Brett. So können in dem Endspiel perfekte Spielzüge ohne Rechenzeit gespielt werden. Endspieldatenbanken haben einen großen Speicherbedarf, weil die Anzahl an möglichen Spielstellungen mit mehr Steinen auf dem Brett extrem wächst. So gibt Ralf Gasser in seinem Paper an, dass es in der Zug- und Endphase des Spiels unter Berücksichtigung von Spiegelungen und ungültigen Zuständen noch $7.673.759.269$ Zustände gibt [RG97].
Algorithmus zur Erstellung von Endspieldatenbanken
Schon 1912 soll der Mathematiker Ernst Zermelo auf einem Mathematikerkongress den folgenden Algorithmus zur Herstellung von Endspieldatenbanken vorgestellt haben. Dieser Algorithmus findet auch heutzutage noch Anwendung und lässt sich in vier Schritten theoretisch beschreiben. Die genaue Implementierung und Abwandlung für das Brettspiel Mühle wird in dem Kapitel #REF beschrieben.
Schritt 1: Es werden alle gültigen Zustände mit nicht mehr als $n$ Steinen auf dem Spielbrett erzeugt.
Schritt 2: Im zweiten Schritt werden alle Gewinnstellungen für weiß gesucht:
- Es werden alle Zustände gesucht, bei denen schwarz direkt verloren hat.
- Es werden alle Zustände gesucht, an denen weiß am Zug ist und mindestens ein Zug zu einer Stellung unter 1. führt. Bei diesen Zuständen hat schwarz in einem Zug verloren.
- Es werden alle Zustände gesucht, bei denen schwarz am Zug ist und bei dem jeder Zug zu einer Stellung aus 2. führt. Hier kann schwarz eine Niederlage in einem Zug nicht verhindern.
- Es werden alle Zustände gesucht, an denen weiß am Zug ist und mindestens ein Zug zu einer Stellung unter 3. führt. Bei diesen Zuständen hat schwarz in zwei Zügen verloren.
- Es werden alle Zustände gesucht, bei denen schwarz am Zug ist und bei dem jeder Zug zu einer Stellung aus 2. oder 4. führt. Hier kann schwarz eine Niederlage in zwei Zügen nicht verhindern.
- Es werden alle Zustände gesucht, an denen weiß am Zug ist und mindestens ein Zug zu einer Stellung unter 5. führt. Bei diesen Zuständen hat schwarz in drei Zügen verloren.
Es werden alle Zustände gesucht, bei denen schwarz am Zug ist und bei dem jeder Zug zu einer Stellung aus 2., 4. oder 6. führt. Hier kann schwarz eine Niederlage in drei Zügen nicht verhindern.
usw.
Der Schritt wird solange wiederholt, bis es keine neuen Zustände mehr gibt. Damit sind alle Stellungen gefunden, mit denen weiß bei maximal $n$ Steinen auf dem Brett gewinnt.
Schritt 3: Im dritten Schritt werden alle Gewinnstellungen für schwarz gesucht, dies erfolgt analog wie Schritt 2. Da Mühle ein komplett symmetrisches Spiel für weiß und schwarz ist, sind die Mengen für das Gewinnen auf dem Brett identisch.
Schritt 4: Alle Zustände, die nicht in Schritt zwei auftauchen, laufen bei einem perfekten Spiel von beiden Spielern auf ein Unentschieden hinaus, da keiner der beiden Spieler verlieren kann.
Der Algorithmus von Zermelo ist allgemein formuliert und es existieren einige Verbesserungen für den Algorithmus, besonders für das Schachspiel. Eine abgewandelte Implementierung für das 3-3 Endspiel für Mühle wird in dem Kapitel beschrieben.
Mühle
Das Spiel Mühle ist ein Brettspiel für zwei Spieler, welches schon im vor Christus gespielt worden sein soll. Somit zählt es neben Spielen wie Schach und Go zu den ältesten uns bekannten Brettspielen, welches noch gespielt wird. In dieser Hausarbeit wird das Spiel nach den offiziellen Turnierregeln des Weltmühlespiel Dachverband gespielt. Im englischen Sprachraum wird Mühle als Nine men's morris bezeichnet.
Das Spielbrett besteht aus drei Quadraten, die durch vier Verbindungslinien verbunden sind. An den Eck- und Verbindungspunkten können die Spielsteine platziert werden. Insgesamt gibt es für jeden Spieler neun Spielsteine, in der Regel in den Farben weiß und schwarz. In der folgenden Abbildung ist ein leeres Spielbrett dargestellt.
Das Spiel gliedert sich in drei Spielphasen:
Das Spiel ist vorbei, sobald ein Spieler verloren hat. Ein Spieler hat dann genau dann verloren, wenn
Um das Spiel gewinnen zu können, müssen die Spieler versuchen, Mühlen zu bauen. Eine Mühle besteht aus drei Steinen, die sich auf einer Linie befinden. Es gibt 16 verschiedene Möglichkeiten eine Mühle auf dem Spielbrett zu bauen (jeweils vier auf den Seitenlinien der drei Quadrate und auf den vier Verbindungslinien). Hat der Spieler eine Mühle gebaut, darf er von dem Gegenspieler einen Spielstein vom Brett entfernen. Dabei ist darauf zu achten, dass sich der Spielstein nicht in einer Mühle befindet (Ausnahme: Alle Spielsteine des Gegenspielers befinden sich in einer Mühle). Es ist in jeder Spielphase möglich eine Mühle zu bilden. In der Setzphase kann ein Spieler mit einem Zug zwei Mühlen gleichzeitig bilden, dann darf er auch zwei Steine von dem Gegenspieler entfernen.