Meta-Tic-Tac-Toe

Meta-Tic-Tac-Toe ist ein Brettspiel, das aus neun Tic-Tac-Toe-Brettern besteht, die in einem 3 × 3-Raster angeordnet sind. Die Spieler spielen abwechselnd auf den kleineren Tic-Tac-Toe-Brettern, bis einer von ihnen auf dem größeren Tic-Tac-Toe-Brett gewinnt. Im Vergleich zu herkömmlichem Tic-Tac-Toe ist die Strategie in diesem Spiel konzeptionell schwieriger und hat sich für Computer als herausfordernder erwiesen.

Darstellung einer laufenden Partie Meta-Tic-Tac-Toe (die großen „X“ und „O“ markieren bereits gewonnene lokale Bretter). Der letzte Zug von „O“ wurde im mittleren oberen lokalen Brett in das mittlere linke Kästchen gespielt. Daher muss „x“ einen Zug im mittleren linken lokalen Brett (markiert) ausführen.

Regeln

Da „X“ einen Zug in das Kästchen rechts oben auf dem mittleren lokalen Brett spielte, muss „O“ in das lokale Brett rechts oben (markiert) einsetzen.

Es wird auf einem Brett mit 9×9 Feldern gespielt, das in neun kleinere lokale Bretter von 3×3 Feldern eingeteilt ist. Die Spieler, X und O, ziehen abwechselnd, X beginnt. Der Spieler am Zug trägt sein Symbol in ein noch freies Feld ein (setzt in dieses Feld).

Der Startspieler kann sein erstes Symbol in ein beliebiges Feld eintragen. Danach muss jeder Zug in dem lokalen Brett gesetzt werden, das durch die Position des vorhergehenden Zuges in dessen lokalem Brett gegeben ist. Wenn z. B. in das obere rechte Feld eines lokalen Bretts gesetzt wird, muss der nächste Zug im oberen rechten lokalen Brett erfolgen. Der ziehende Spieler kann also nur wählen, in welches freie Feld des gegebenen lokalen Bretts er setzt.

Wenn ein Spieler in einem lokalen Brett eine Dreierreihe seiner Symbole (waagerecht, senkrecht oder diagonal) bildet, hat er damit dieses lokale Brett gewonnen, und in dieses darf dann nicht mehr gesetzt werden. Wenn das durch den vorhergehenden Zug gegebene lokale Brett bereits von einem Spieler gewonnen wurde oder voll besetzt ist, kann der Folgezug in ein beliebiges anderes noch nicht gewonnenes lokales Brett gesetzt werden.

Ziel des Spiels ist es, drei lokale Bretter zu gewinnen, die ihrerseits auf dem globalen Brett eine waagerechte, senkrechte oder diagonale Reihe bilden. Wenn keine Züge mehr möglich sind und kein Spieler die Siegbedingung erfüllt hat, endet das Spiel unentschieden.

Spielweise

Meta-Tic-Tac-Toe ist wesentlich komplexer als die meisten anderen Variationen von Tic-Tac-Toe, da es keine klare Strategie für das Spielen gibt. Dies liegt an der komplizierten Spielverzweigung in diesem Spiel. Obwohl jeder Zug auf einem lokalen Brett gespielt werden muss, das einem normalen Tic-Tac-Toe-Brett entspricht, muss jeder Zug das globale Brett auf verschiedene Weise berücksichtigen:

1. Den nächsten Zug vorwegnehmen: Jeder Zug, der auf einem lokalen Brett gespielt wird, bestimmt, wo der nächste Zug des Gegners gespielt werden darf. Dies kann dazu führen, dass Bewegungen, die im normalen Tic-Tac-Toe-Bereich als schlecht angesehen werden, realisierbar sind, da der Gegner an ein anderes lokales Brett geschickt wird und möglicherweise nicht sofort auf den gemachten Zug reagieren kann. Daher sind die Spieler gezwungen, das größere Spielbrett in Betracht zu ziehen, anstatt sich nur auf das lokale Brett zu konzentrieren.
2. Vorhersehen der Zugfolgen: Das Visualisieren zukünftiger Zweige des Spielbaums ist schwieriger als das Einbrett-Tic-Tac-Toe. Jede Bewegung bestimmt die nächste Bewegung, und daher folgt die Vorhersehung zukünftige Bewegungen einem viel weniger linearen Pfad. Zukünftige Positionen sind nicht mehr austauschbar, jeder Schritt führt zu stark unterschiedlichen möglichen zukünftigen Positionen. Dies macht es schwierig, den Spielbaum zu visualisieren, wodurch möglicherweise viele mögliche Pfade übersehen werden. Auf gegnerische Züge kann möglicherweise nicht sofort reagiert werden. Daher sind die Spieler gezwungen, das größere Spielbrett in Betracht zu ziehen, anstatt sich nur auf das lokale Brett zu konzentrieren.
3. Das Spiel gewinnen: Aufgrund der Regeln des Meta-Tic-Tac-Toe ist das globale Brett niemals direkt betroffen. Es wird nur durch Aktionen beeinflusst, die auf lokalen Brettern stattfinden. Dies bedeutet, dass jeder gespielte lokale Zug nicht dazu gedacht ist, das lokale Brett, sondern das globale Brett zu gewinnen. Lokale Gewinne sind nicht wertvoll, wenn sie nicht zum Gewinnen des globalen Bretts verwendet werden können. Tatsächlich kann es strategisch sein, dem Gegner ein lokales Brett zu opfern, um selbst ein wichtigeres lokales Brett zu gewinnen. Diese zusätzliche Komplexität macht es für den Menschen schwieriger, die relative Wichtigkeit und Bedeutung von Bewegungen zu analysieren, und folglich ist es schwieriger, gut zu spielen.

Variante

„Ti-Tan-Toe“ oder auch „Big-brain-Tic-Tac-Toe“ stellt eine noch komplexere Variante des Spiels dar. Das Spielbrett von Meta-Tic-Tac-Toe befindet sich nun neunmal in einem großen 3x3 Raster. Somit wird durch eine dritte Ebene die Zahl der Einzelfelder von 81 auf 729 erhöht.

Spielweise

Die Regeln entsprechen denen von Meta-Tic-Tac-Toe, allerdings muss erst ein kleineres Raster gewonnen werden, um auf der nächsten Ebene ein Feld beanspruchen zu können. Mit einer Reihe dieser Felder lässt sich dann wiederum das Spiel entscheiden. Die Spielweise folgt ebenfalls den Vorgaben von Meta-Tic-Tac-Toe – es wird nur in die kleinsten Felder eingetragen. Die Zugvorgabe ergibt sich folgendermaßen:

• Spieler 1 trägt ein Symbol in ein beliebiges Feld der 729 kleinen Felder ein.
• Die Position dieses Symbols im kleinsten Raster gibt nun das korrespondierende Feld im mittleren Raster vor und die Position im mittleren Raster wiederum das korrespondierende Feld im großen Raster.
• Spieler 2 muss den nächsten Zug nun also in der so gegebenen Position im mittleren Raster und zugleich in der entsprechenden Position im großen Raster eintragen.
• Ist ein so vorgegebenes kleines Raster bereits vollständig ausgefüllt, darf Spieler 2 in ein freies Feld seiner Wahl eintragen.

Exemplarische Darstellung des Spielbretts

Um die Zugregelung benutzerfreundlicher zu gestalten und eine Notation zu ermöglichen, wurde eine eigene Koordinatenschreibweise entwickelt:

Notation

Ähnlich wie beim Schach ist das Spielbrett mit Buchstaben und Zahlen betitelt um Koordinaten angeben zu können. Horizontal von links aus werden die Spalten auf jeder Ebene mit 1,2 und 3 betitelt, vertikal von unten werden die Zeilen je nach Ebene beschrieben. Auf der ersten Ebene, im kleinsten Raster werden die Zeilen von unten nach oben mit A,B und C beschrieben. Auf der 2. Ebene, dem mittelgroßen Raster sind es von unten nach oben α (alpha) β (beta) und γ (gamma). Auf der 3. Ebene und somit dem größten Raster werden die Zeilen von unten nach oben mit א(aleph), ב(bet) und ג (gimmel) beschrieben.

Wenn ein Zug eingetragen ist, wird vom Großen ins Kleine notiert: Beispiel: | ; ; |

Aus dieser Notation lässt sich nun das vorgegebene Raster für den nächsten Zug einfach ableiten. Dabei werden die beiden letzten Koordinatenzeichen auf die nächste Ebene „erhöht“ und definieren das nächste Spielraster. Somit sind sie Teil des nächsten Zugs: aus A wird α aus α wird א. Der Logik folgend: B→β→ב, C→γ→ג.

Beispiel Notationslogik : 1.|; ; ||; ; | 2.|; ; ||3; ; | 3.|1; ; ||3; ; | 

„Ti-Tan-Toe“ spielt sich noch indirekter als die Meta-Variante, fordert strategisches Denken in mehreren Ebenen und ist intellektuell noch anspruchsvoller. Theoretisch lässt sich das Spiel nach diesem Konzept noch um eine Vielzahl an Ebenen erweitern, es besteht ebenso die Möglichkeit, das Konzept in höheren Dimensionen umzusetzen.

Computerimplementierungen

Während Tic-Tac-Toe elementar zu lösen ist und fast sofort mit der Tiefensuche durchgeführt werden kann, kann das Meta-Tic-Tac-Toe mit keiner Brute-Force-Taktik vernünftigerweise gelöst werden. Daher sind kreativere Computerimplementierungen erforderlich, um dieses Spiel zu spielen.

Die gebräuchlichste Taktik der künstlichen Intelligenz (KI), Minimax, kann verwendet werden, um Meta-Tic-Tac-Toe zu spielen, hat jedoch Schwierigkeiten, dies zu spielen. Das liegt daran, dass dem Meta-Tic-Tac-Toe trotz relativ einfacher Regeln eine einfache heuristische Bewertungsfunktion fehlt. Diese Funktion ist im Minimax erforderlich, da sie bestimmt, wie gut eine bestimmte Position ist. Obwohl elementare Bewertungsfunktionen für das Meta-Tic-Tac-Toe unter Berücksichtigung der Anzahl lokaler Siege erstellt werden können, übersehen diese weitgehend den Positionsvorteil, der viel schwieriger zu quantifizieren ist. Ohne eine effiziente Bewertungsfunktion sind die meisten typischen Computerimplementierungen schwach, und daher gibt es nur wenige Computergegner, die Menschen konsequent übertreffen können.

Algorithmen der künstlichen Intelligenz, die keine Bewertungsfunktionen benötigen, wie der Monte-Carlo-Baumsuchalgorithmus, haben jedoch kein Problem beim Spielen dieses Spiels. Die Monte-Carlo-Baumsuche basiert auf zufälligen Simulationen von Spielen, um zu bestimmen, wie gut eine Position ist, und kann daher genauer beurteilen, wie gut eine aktuelle Position ist. Daher übertreffen Computerimplementierungen, die diese Algorithmen verwenden, Minimax-Lösungen und können menschliche Gegner konsequent schlagen.

Weblinks

Commons: Ultimate Tic Tac Toe – Sammlung von Bildern

• Monte Carlo tree-search implementation
• Open Source Monte Carlo tree search implementation in C and Swift
• Ultimate Tic-Tac-Toe game where artificial intelligences confront each other

Einzelnachweise

1. Eytan Lifshitz, David Tsurel: AI Approaches to Ultimate Tic-Tac-Toe. In: The Rachel and Selim Benin School of Computer Science and Engineering. 26. Dezember 2016; abgerufen im 1. Januar 1. 
2. Ben Orlin: Ultimate Tic-Tac-Toe. In: Math with Bad Drawings. 16. Juni 2013, abgerufen am 18. Oktober 2016. 
3. Max Leibert, Fabian Müller - Spielentwickler, 28. September 2023
4. Ofek Gila: What is the Monte Carlo tree search? In: We Blog. 27. Juni 2016, abgerufen am 18. Oktober 2016.