Informationen zum Spiel "X gewinnt in N Richtungen"
Auch bekannt als "Kringel und Kreuzchen".
Hier kann man es übrigens spielen...Einleitung
Eines meiner Lieblingsspiele ist "5 gewinnt", da man für das Spiel nur ein Blatt Papier und zwei Stifte benötigt, und es recht interessant und anspruchsvoll ist. Nach einer Weile beschlossen Frank Grieger - ein Klassenkamerad, den ich an dieser Stelle recht herzlich grüße - und ich, uns das Spiel etwas näher zu betrachten. Das Ergebnis sollte eine perfekte Strategie zum Blocken des Gegners oder Siegen über den Gegner sein, was wir aufgrund der Kompliziertheit des Problems damals leider nicht schafften. Auch entstand aus dieser Arbeit ein Programm, das ich, in klein wenig vereinfachter Form, als Java-Applet hier veröffentlicht habe. Das Ziel des Programmes war vor allem, alle uns bekannten perfekten Strategien zu implementieren. Für offene Probleme implementierten wir zwar Heuristiken, doch sind diese einem guten menschlichen Gegner weit unterlegen.
Was ist "X gewinnt in N Richtungen"?
Die am weitesten verbreiteste Variante ist 5 gewinnt in 4 Richtungen - oder kurz "5 gewinnt" bzw. "Kringel und Kreuzchen". Dabei wird auf einem "unendlich großem", karierten Blatt Papier gespielt, wobei zwei Spieler ihre Symbole (X und O) abwechselnd in freie Kästchen setzen. Ziel des Spieles ist es, 5 eigene Symbole hintereinander in einer Richtung (waagerecht, senkrecht oder diagonal) zu bekommen.
"X gewinnt in N Richtungen" ist nun die verallgemeinerte Variante des Spieles. Zum einen ist die Anzahl der Symbole, die man zum Sieg braucht, variabel (und mit X bezeichnet worden), zum anderen wird die Anzahl der Richtungen (N) allgemein gehalten. Hier betrachte ich allerdings nur bis zu 4 Richtungen, da ich keine Ahnung habe, wie das Spielfeld mit 5 Richtungen aussehen soll. Ideen dazu an mich...
Begriffsklärung
- Blocken:
- Besetzen von Feldern, die der Gegner bei einer Struktur zum Sieg benötigt.
- Offensivblock:
- Ein Block mit dem man eine Struktur bekommt, welche der Gegner wiederum unbedingt blocken muß, so daß man die Offensive übernimmt.
(Vielleicht fällt mir irgendwann noch etwas ein...)
Strategien
Möglichkeiten des Spielausgangs
Es gibt drei Möglichkeiten, wie ein Spiel enden kann: Spieler 1 gewinnt, unentschieden oder Spieler 2 gewinnt. Ein Spiel mit zwei perfekten Spielern wird immer die gleiche dieser Möglichkeiten als Ausgang haben. Falls das nicht der Fall wäre, hängt der Ausgang des Spielers von einer Entscheidung eines Spielers ab, da es keine Zufallselemente im Spiel gibt. Er wird immer die für ihn bessere Entscheidung fällen, so daß es immer zum gleiche Ergebnis kommt. Für Spieler 2 kann es keine perfekte Strategie zum Gewinnen geben, denn wenn es eine solche Strategie gibt, könnte Spieler 1 sie nehmen, sein ersten Zug irgendwo machen und als Spieler 2 spielen, denn ein zusätzliches eigenes Zeichen kann nie schaden. Das heißt Spieler 1 würde auch gewinnen, da er die perfekte Strategie von Spieler 2 anwenden kann. Da aber zwei Spieler nicht gleichzeitig gewinnen können, wird es keine perfekte Strategie für den Sieg von Spieler 2 geben. Es gibt also folgende zwei Möglichkeiten:
- Spieler 1 gewinnt immer, wenn er perfekt spielt.
- Es gibt immer ein Unentschieden, wenn mindestens einer der beiden Spieler perfekt spielt.
Bei diesen beiden Möglichkeiten hat sich unser 2-Mann-Forschungsteam in zwei Lager geteilt, was an unserem eigenen Spielverhalten liegt, denn während Frank sehr oft und gerne offensiv spielt, ziehe ich das defensive Spielverhalten vor.
Einfache Blockstrategie
Eine perfekte Defensivstrategie ist die Hales-Jewett-Paarmethode. Hierbei weist man jedem Feld ein anderes Feld zu, so daß immer zwei Felder ein Paar bilden. Wenn nun der Gegner in ein solches Feld setzt, nimmt man selbst den Partner des besetzten Feldes. So stellt man sicher, daß man immer eines von zwei Feldern besitzt. Wir fanden in einem Buch eine solche Paarung für "9 gewinnt" auf einem solchen unendlich großen Spielfeld mit 4 Richtungen:
Ein Feld nimmt immer das Feld, welches am anderen Ende der Linie, welches vom eigenen Feld ausgeht, liegt, als Partner. Wie man sieht erreicht der Gegner im schlimmsten Fall 8 in einer Reihe, da man dann immer links und rechts die beiden Felder besitzt. Weil bei dieser Paarmethode alle Felder besetzt sind, kann man mit dieser Methode keine Strategie für "5 gewinnt" finden, da dann nämlich mehr Striche gebraucht werden, denn dann muß in einer Reihe der Zwischenraum zwischen zwei Strichen, welche in dieselbe Richtung zeigen, von 6 auf 2 reduziert werden, denn nur bei folgender Paarung auf einer Linie ist 5 in einer Reihe unmöglich:
Im schlimmsten Fall bekommt man selbst die beiden äußeren Felder, und dabei bekommt der Gegner nur 4 in einer Reihe zusammen.
Wir betrachteten nun dieses Spiel mit weniger Richtungen. Die dichteste Paarmethode für eine Richtung sieht folgendermaßen aus:
Hier bekommt man höchstens 2 in einer Reihe zusammen. Bei 2 Richtungen gibt es folgende Möglichkeiten: nur die waagerechten und senkrechten Richtungen zulassen oder nur die Diagonalen nehmen. (Das Java-Applet nimmt die waagerechte und senkrechte Richtung.) Für beide Varianten gibt es eine Paarung für "5 gewinnt". Da auch diese Paarung dicht ist, kann man bei 5 in einer Reihe keine Richtung hinzufügen, so daß es sich wieder zeigt, daß man mit dieser Methode keine Strategie für "5 gewinnt" in 4 Richtungen findet.
Nun haben wir versucht bei "X gewinnt" in N Richtungen eine
mathematische Beziehung zwischen X und N herzustellen.
Der Abstand zwischen zwei Strichen ist X-1, denn soviel Symbole darf der Gegner
maximal in einer Reihe nebeneinander bekommen.
Da nun für jede Richtung sich immer 2 von X-1 Felder paaren,
und kein Feld übrigbleiben soll, heißt die Beziehung:
X-1 = 2*N
Nach X umgestellt ergibt sich:
X=2*N+1
Wir erhalten:
| Anzahl an Richtungen | Berechnete Anzahl an benötigten Symbolen in einer Reihe |
|---|---|
| 1 | 3 |
| 2 | 5 |
| 3 | 7 |
| 4 | 9 |
Für 1,2 und 4 Richtungen ergeben sich also die zuvor gefunden Zahlen. So suchten wir nun für 3 Richtungen die Paarmethode für "7 gewinnt", welche wir dann auch bald fanden:
Perfekte Strategien
Wir betrachteten ebenfalls, wann Spieler 1 mit N Richtungen X Symbole in einer Reihe garantiert bekommen kann. Wir kamen dabei zu folgenden Ergebnissen:
| Anzahl an Richtungen | Berechnete Anzahl an garantierten Symbolen in einer Reihe |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 4 |
| 4 | 4 |
Für diese Spiele haben wir jeweils eine perfekte Strategie herausgefunden. Das heißt also nicht, daß es man nicht noch mehr Symbole in einer Reihe garantiert bekommt. (Für perfekte Gewinnstrategien für höhere Anzahlen an Symbolen bin ich jederzeit dankbar!)
Zusammen mit den Zahlen der Blockstrategie ergibt sich:
| Anzahl an Richtungen | perfekte Strategie für: | |
|---|---|---|
| Spieler 1 | Unentschieden | |
| 1 | 2 und weniger | 3 und mehr |
| 2 | 4 und weniger | 5 und mehr |
| 3 | 4 und weniger | 7 und mehr |
| 4 | 4 und weniger | 9 und mehr |
Es lohnt sich also nicht, nur mit einer oder zwei Richtungen zu spielen, da es hierfür immer eine perfekte Strategie gibt. Interessant ist auch, daß die Maximalanzahl an Symbolen für eine perfekte Strategie ab 2 Richtungen konstant bleibt. Hier sollte man also nochmal kräftig nach einer möglichen perfekten Strategie suchen.
Defensivstrukturen
Zum Schluß noch ein paar besonders effektive Strukturen, wenn es darum geht, den Gegner beim "5 gewinnt" zu blocken. Dem Gegner wird nur Platz für einen Vierer gelassen. Diese Struktur bietet auch eine hervorragende Basis für eine Offensive.
