Tic Tac Toe

Aus Wikiludia
Wechseln zu: Navigation, Suche

Tic Tac Toe

Sehr schwach gelöst ist ein Spiel, wenn man für die Startposition des Spieles dasjenige Spielergebnis bestimmen kann, das jeder der beiden Spieler unabhängig von der Spielweise seines Gegners mindestens erzwingen kann. Ein diesbezüglicher Nachweis muss über die dafür notwendigen Spielweisen keine Aussage machen.

Schwach gelöst ist ein Spiel,wenn darüber hinaus ein praktisch realisierbarer Algorithmus angegeben werden kann, mit dem die beidseitig optimalen Spielweisen ausgehend von der Startposition des Spiels bestimmt werden können.

Stark gelöst ist ein Spiel,wenn ein allgemeiner, praktisch realisierbarer Algorithmus existiert, mit dem für jede Position ein optimaler Zug berechnet werden kann. Im Unterschied zu schwach gelösten Spielen muss dieser Algorithmus auch für solche Positionen funktionieren, die ausgehend von der Ausgangsposition nur bei fehlerhafter Spielweise vorkommen.

Ein Beispiel für ein stark gelöstes Spiel ist z.B das Mühle-Spiel,Dame oder das Tic Tac Toe Spiel:

Tic Tac Toe Spiel

Das Tic Tac Toe Spiel ist ein klassisches 2-Personen-Strategiespiel. Seine Gescshichte lässt sich bis ins 12.Jahrhundert v. Chr. zurückverfolgen.


Spielverlauf

Auf einem 3×3 Felder großen Spielfeld machen zwei Spieler abwechselnd ihre Zeichen (Kreuze und Kreise). Der Spieler, der als erstes drei seiner Zeichen in einer Reihe, Spalte oder einer der beiden Hauptdiagonalen setzen kann, gewinnt. Wenn allerdings beide Spieler optimal spielen, kann keiner gewinnen. Es kommt zu einem Unentschieden.

Strategie und Taktik

Für Tic Tac Toe gibt es 255.168 verschiedene Spielverläufe, von denen 131.184 mit einem Sieg des ersten Spielers enden, 77.904 mit einem Sieg des zweiten Spielers und 46.080 mit einem Unentschieden.(1) Viele Spielverläufe sind gleich in dem Sinne, dass sie sich durch Drehungen oder Spiegelungen des Spielfelds ineinander überführen lassen. Fasst man diese Verläufe zusammen, vermindert sich die Anzahl der Spielverläufe(2) auf 31.896, wobei 16.398 vom ersten und 9.738 vom zweiten Spieler gewonnen werden und 5.760 unentschieden ausgehen. Es gibt 5.478 verschiedene Spielsituationen, 765 bis auf Rotation oder Spiegelung. Im Vergleich zu Spielen wie Dame oder Schach ist die Anzahl der Spielverläufe und Spielsituationen verschwindend gering. Wegen dieser geringen Komplexität lässt sich leicht zeigen, dass beide Spieler ein Unentschieden erzwingen können.

Der erste Spieler kann nicht bereits im ersten Zug verlieren. Der zweite Spieler hält nur in 24 von den 72 Möglichkeiten für die beiden ersten Züge ein Unentschieden.

Erster Spieler (X) beginnt, zweiter Spieler (O) hält ein Unentschieden:

X - -    - - O   - X -    - X -    - X O
- O -    - X -   - O -    - - -    - - - 
- - -    - - -   - - -    - O -    - - -

Es gibt 16 Unentschieden-Positionen, die aus folgenden drei durch Spiegelung oder Rotation erhalten werden können:

X X O   X X O   X X O
O X X   O O X   O O X
X O O   X X O   X O X

(1) Bei diesen Zahlenangaben wird die erste Konfiguration mit drei X oder drei O in einer Reihe, Spalte oder Diagonale oder ein vollständig ausgefülltes Spielfeld, aber nicht bereits die Situation, ab der der Ausgang feststeht, als Ende des Spiels betrachtet. (2)Aus jedem Spielverlauf erhält man durch Rotationen und Spiegelungen sieben weitere Spielverläufe, denn da am Ende immer mindestens fünf Felder belegt sind, ist kein Spielverlauf symmetrisch bezüglich einer Rotation oder Spiegelung.

Meine Werkzeuge