Tic-Tac-Toe

Tic-Tac-Toe oder Drei gewinnt (auch Kreis und Kreuz, Dodelschach) ist ein klassisches, einfaches Zweipersonen-Strategiespiel, dessen Geschichte sich bis ins 12. Jahrhundert v. Chr. zurückverfolgen lässt.

Auf einem quadratischen, 3×3 Felder großen Spielfeld setzen die beiden Spieler abwechselnd ihr Zeichen (ein Spieler Kreuze, der andere Kreise) in ein freies Feld. Der Spieler, der als Erster drei Zeichen in eine Zeile, Spalte oder Diagonale setzen kann, gewinnt. Wenn allerdings beide Spieler optimal spielen, kann keiner gewinnen, und es kommt zu einem Unentschieden. Das heißt, alle neun Felder sind gefüllt, ohne dass ein Spieler die erforderlichen Zeichen in einer Reihe, Spalte oder Diagonalen setzen konnte.

Erster Spieler (X) gewinnt, weil Spieler Zwei (O) beim ersten Zug einen Fehler macht:

${\displaystyle {\begin{array}{c|c|c}\,\,&\,\,&\!\color {green}\times \!\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\color {green}\circ \!&\,\,&\!\times \!\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\,\,&\!\times \!\\\hline \,\,&\,\,&\,\,\\\hline \!\color {green}\times \!&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\,\,&\!\times \!\\\hline \,\,&\!\color {green}\circ \!&\,\,\\\hline \!\times \!&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\,\,&\!\times \!\\\hline \,\,&\!\circ \!&\,\,\\\hline \!\times \!&\,\,&\!\color {green}\times \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\,\,&\!\times \!\\\hline \,\,&\!\circ \!&\!\color {green}\circ \!\\\hline \!\times \!&\,\,&\!\times \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\,\,&\!\times \!\\\hline \,\,&\!\circ \!&\!\circ \!\\\hline \!\times \!&\!\color {green}\times \!&\!\times \!\\\end{array}}}$

Erster Spieler (X) gewinnt, weil Spieler Zwei (O) beim ersten Zug einen Fehler macht:

${\displaystyle {\begin{array}{c|c|c}\,\,&\,\,&\,\,\\\hline \,\,&\!\color {green}\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\,\,&\!\color {green}\circ \!&\,\,\\\hline \,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\color {green}\times \!&\!\circ \!&\,\,\\\hline \,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\circ \!&\,\,\\\hline \,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\!\color {green}\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\circ \!&\,\,\\\hline \!\color {green}\times \!&\!\times \!&\,\,\\\hline \,\,&\,\,&\!\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\circ \!&\,\,\\\hline \!\times \!&\!\times \!&\,\,\\\hline \!\color {green}\circ \!&\,\,&\!\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\circ \!&\,\,\\\hline \!\times \!&\!\times \!&\!\color {green}\times \!\\\hline \!\circ \!&\,\,&\!\circ \!\\\end{array}}}$

Erster Spieler (X) verliert, weil er beim zweiten Zug einen Fehler macht:

${\displaystyle {\begin{array}{c|c|c}\,\,&\!\color {green}\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\,\,&\!\times \!&\,\,\\\hline \,\,&\!\color {green}\circ \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\,\,&\!\times \!&\,\,\\\hline \,\,&\!\circ \!&\,\,\\\hline \,\,&\!\color {green}\times \!&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\,\,&\!\times \!&\,\,\\\hline \,\,&\!\circ \!&\,\,\\\hline \!\color {green}\circ \!&\!\times \!&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\,\,&\!\times \!&\!\color {green}\times \!\\\hline \,\,&\!\circ \!&\,\,\\\hline \!\circ \!&\!\times \!&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\color {green}\circ \!&\!\times \!&\!\times \!\\\hline \,\,&\!\circ \!&\,\,\\\hline \!\circ \!&\!\times \!&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\!\times \!&\!\times \!\\\hline \,\,&\!\circ \!&\,\,\\\hline \!\circ \!&\!\times \!&\!\color {green}\times \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\!\times \!&\!\times \!\\\hline \!\color {green}\circ \!&\!\circ \!&\,\,\\\hline \!\circ \!&\!\times \!&\!\times \!\\\end{array}}}$

Erster Spieler (X) verliert, weil er beim zweiten Zug einen Fehler macht:

${\displaystyle {\begin{array}{c|c|c}\,\,&\!\color {green}\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\!\color {green}\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\color {green}\times \!&\!\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\!\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\times \!&\!\color {green}\circ \!\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\!\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\times \!&\!\circ \!\\\hline \,\,&\,\,&\!\color {green}\times \!\\\hline \,\,&\,\,&\!\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\times \!&\!\circ \!\\\hline \,\,&\,\,&\!\times \!\\\hline \!\color {green}\circ \!&\,\,&\!\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\times \!&\!\circ \!\\\hline \,\,&\!\color {green}\times \!&\!\times \!\\\hline \!\circ \!&\,\,&\!\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\times \!&\!\circ \!\\\hline \,\,&\!\times \!&\!\times \!\\\hline \!\circ \!&\!\color {green}\circ \!&\!\circ \!\\\end{array}}}$

Kein Spieler gewinnt, da beide fehlerfrei spielen:

${\displaystyle {\begin{array}{c|c|c}\!\color {green}\times \!&\,\,&\,\,\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\,\,&\,\,\\\hline \,\,&\!\color {green}\circ \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\,\,&\,\,\\\hline \,\,&\!\circ \!&\!\color {green}\times \!\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\,\,&\!\color {green}\circ \!\\\hline \,\,&\!\circ \!&\!\times \!\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\,\,&\!\circ \!\\\hline \,\,&\!\circ \!&\!\times \!\\\hline \!\color {green}\times \!&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\,\,&\!\circ \!\\\hline \!\color {green}\circ \!&\!\circ \!&\!\times \!\\\hline \!\times \!&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\,\,&\!\circ \!\\\hline \!\circ \!&\!\circ \!&\!\times \!\\\hline \!\times \!&\!\color {green}\times \!&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\,\,&\!\circ \!\\\hline \!\circ \!&\!\circ \!&\!\times \!\\\hline \!\times \!&\!\times \!&\!\color {green}\circ \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\times \!&\!\color {green}\times \!&\!\circ \!\\\hline \!\circ \!&\!\circ \!&\!\times \!\\\hline \!\times \!&\!\times \!&\!\circ \!\\\end{array}}}$

Kein Spieler gewinnt, da beide fehlerfrei spielen:

${\displaystyle {\begin{array}{c|c|c}\,\,&\!\color {green}\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\,\,&\!\times \!&\,\,\\\hline \,\,&\!\color {green}\circ \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\,\,&\!\times \!&\!\color {green}\times \!\\\hline \,\,&\!\circ \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\color {green}\circ \!&\!\times \!&\!\times \!\\\hline \,\,&\!\circ \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\!\times \!&\!\times \!\\\hline \,\,&\!\circ \!&\,\,\\\hline \,\,&\,\,&\!\color {green}\times \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\!\times \!&\!\times \!\\\hline \,\,&\!\circ \!&\!\color {green}\circ \!\\\hline \,\,&\,\,&\!\times \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\!\times \!&\!\times \!\\\hline \!\color {green}\times \!&\!\circ \!&\!\circ \!\\\hline \,\,&\,\,&\!\times \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\!\times \!&\!\times \!\\\hline \!\times \!&\!\circ \!&\!\circ \!\\\hline \,\,&\!\color {green}\circ \!&\!\times \!\\\end{array}}\quad {\begin{array}{c|c|c}\!\circ \!&\!\times \!&\!\times \!\\\hline \!\times \!&\!\circ \!&\!\circ \!\\\hline \!\color {green}\times \!&\!\circ \!&\!\times \!\\\end{array}}}$

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. (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.)

Viele Spielverläufe sind gleich in dem Sinne, dass sie sich durch Drehungen oder Spiegelungen des Spielfelds ineinander überführen lassen. Gleiche Verläufe zusammengefasst, vermindert sich die Zahl der verschiedenen Spielverläufe auf ein Achtel: insgesamt 31.896, wobei 16.398 vom ersten und 9.738 vom zweiten Spieler gewonnen werden und 5.760 unentschieden ausgehen. (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.)

Es gibt 5.478 verschiedene Spielsituationen, ohne Rotation oder Spiegelung 765. Im Vergleich zu Spielen wie Go, 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 (gespiegelte und rotierte Möglichkeiten sind nicht dargestellt):

${\displaystyle {\begin{array}{c|c|c}\!\times \!&\,\,&\,\,\\\hline \,\,&\!\circ \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\,\,&\,\,&\!\circ \!\\\hline \,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\,\,&\!\times \!&\,\,\\\hline \,\,&\!\circ \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\!\circ \!&\,\,\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\!\circ \!\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\,\,&\!\times \!&\!\circ \!\\\hline \,\,&\,\,&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}}$

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

${\displaystyle {\begin{array}{c|c|c}\!\times \!&\!\times \!&\!\circ \!\\\hline \!\circ \!&\!\times \!&\!\times \!\\\hline \!\times \!&\!\circ \!&\!\circ \!\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\!\times \!&\!\times \!&\!\circ \!\\\hline \!\circ \!&\!\circ \!&\!\times \!\\\hline \!\times \!&\!\times \!&\!\circ \!\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\!\times \!&\!\times \!&\!\circ \!\\\hline \!\circ \!&\!\circ \!&\!\times \!\\\hline \!\times \!&\!\circ \!&\!\times \!\\\end{array}}}$

Meist setzt der erste Spieler (X) in die Mitte. Der zweite Spieler muss, um ein Unentschieden zu erzwingen, in die Ecke setzen, sonst kann Spieler 1 mühelos einen Sieg erringen:

${\displaystyle {\begin{array}{c|c|c}\,\,&\!\circ \!&\,\,\\\hline \,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\,\,\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\!\times \!&\!\circ \!&\,\,\\\hline \,\,&\!\times \!&\,\,\\\hline \,\,&\,\,&\!\circ \!\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\!\times \!&\!\circ \!&\,\,\\\hline \!\circ \!&\!\times \!&\,\,\\\hline \!\times \!&\,\,&\!\circ \!\\\end{array}}\qquad \quad {\begin{array}{c|c|c}\!\times \!&\!\circ \!&\!{\boldsymbol {\times }}\!\\\hline \!\circ \!&\!{\boldsymbol {\times }}\!&\,\,\\\hline \!{\boldsymbol {\times }}\!&\,\,&\!\circ \!\\\end{array}}}$

Der britische Informatiker und KI-Forscher Donald Michie entwickelte 1960 mit MENACE („Machine Educable Noughts And Crosses Engine“) einen „Computer“ auf Basis hunderter Streichholzschachteln, der Tic-Tac-Toe lernen konnte. In den Schächtelchen, die jeweils einen möglichen Spielstand repräsentierten, waren durch verschiedenfarbige Perlen die möglichen Züge gespeichert. Je nachdem, ob ein Spiel verloren ging oder gewonnen wurde, wurden die entsprechenden Perlen entfernt oder gleichfarbige dazugelegt. Dadurch lernte das System erfolgreiche Züge und war nach einigen hundert Partien unbesiegbar.^[1]

Tic-Tac-Toe war auch eines der ersten Spiele, die auf Computern (bereits vor Tennis for Two, 1958) erschienen (Spiel OXO auf einem EDSAC-Computer, 1952).

Eine entscheidende Rolle spielt Tic-Tac-Toe auch im Film WarGames – Kriegsspiele.

Der Toilettenreiniger Hirayama im Film Perfect Days beginnt ein Tic-Tac-Toe Spiel mit einem Fremden, nachdem er ein, in einem Schlitz verstecktes Papierstück in einer Kabine findet. Das Spiel wird im Laufe des Films fortgesetzt.

Tic-Tac-Toe lief 1992 als tägliche Gameshow TicTacToe (wie die ältere ARD-Show Tick-Tack-Quiz nach dem US-Vorbild Tic-Tac-Dough) auf RTL. Moderator war Michael Förster. Dort verbarg sich hinter jedem der Felder eine in vier Sekunden zu beantwortende Frage; es gewann, wer als Erster eine Dreierreihe von Feldern erobert hatte. In den Folgen 31 bis 33 hatte der Quizspieler Thomas Kinne einen seiner ersten Fernsehauftritte.^[2]

Das Spiel war auch die Basis für die US-Gameshow Hollywood Squares, die in Deutschland in den 1990er Jahren als XXO – Fritz und Co auf Sat.1 lief.

Man kann es im Browser auf mehreren verschiedenen Schwierigkeitsgraden oder gegen einen Freund spielen.

• Teeko, Vier gewinnt, Fünf in eine Reihe
• Meta-Tic-Tac-Toe, ein Tic-Tac-Toe aus neun Tic-Tac-Toe-Feldern
• Erweiterungen auf drei Dimensionen: Qubic, Sogo
• Tick-Tack-Quiz, ein Tic-Tac-Toe das per Quiz gefüllt wird
• Tick oaT Two: Die Spieler setzen abwechselnd waagerechte und senkrechte Striche in ein 3x3-Feld, wodurch auf manchen Feldern Kreuze entstehen. Der Spieler, der zuerst drei Kreuze in einer Reihe bildet, gewinnt.

• Norman Do: How to Win at TicTacToe (PDF; 2,5 MB), The Australian Mathematical Society, Gazette, Volume 32 Number 3, July 2005, S. 151–161

Commons: Tic Tac Toe – Sammlung von Bildern, Videos und Audiodateien

• Folge A008907 in OEIS (englisch; Anzahl der möglichen Stellungen im Spielverlauf bis auf Rotation oder Spiegelung)
• (englisch) Anleitung zum Spiel ohne Niederlage

1. ↑ Oliver Child: Menace: the Machine Educable Noughts And Crosses Engine. 13. März 2016, abgerufen am 19. Dezember 2017 (englisch). 
2. ↑ TicTacToe 33 1992-03-30. In: YouTube. 24. Juli 2018, abgerufen am 3. August 2018.