Tic Tac Toe - Hilfe

Was soll das Spiel?

Für alle, die noch nichts von Tic Tac Toe gehört haben: Die Wikipedia enthält ein hübsche Kurzeinführung.

Wie man spielt

Vorbereitung

Es geht los mit der Eröffnung eines neuen Spiels oder der Teilnahme an einem bestehenden Spiel.

Um ein neues Spiel zu eröffnen, trägt man einfach oben im Namensfeld von Spieler Gelb oder Blau seinen Namen ein und klickt auf "anmelden". Ist vorher niemand angemeldet gewesen, ist man automatisch Spielleiter.

Um bei einem anderen Spiel teilzunnehmen, klickt man auf den Link "Einem anderen Spiel beitreten" und wählt in der dort erscheinenden Liste das Spiel aus. Bei jedem Spiel in der Liste stehen die Namen der dort angemeldeten Spieler. Anschließend kann man sich selbst bei diesem Spiel anmelden, falls noch ein Platz frei ist. Man kann natürlich auch einfach einem Spiel zugucken.

Man kann festlegen, ob man als Mensch selber denken will oder dies einer künstlichen Intelligenz (KI) überlassen will. Das stellt man neben dem Namen ein. Momentan ist da "Zufall" und "Pauschal" als KI auswählbar. "Zufall" bedeutet pur zufälliges Setzen und ist für Anfänger gedacht oder zum Testen von richtiger KI. "Pauschal" ist eine "richtige" KI. Die KI's werden ein Stückchen weiter unten erklärt.

Der Spielleiter legt fest, wie groß das Spielfeld sein soll und welche Bedingung für Sieg gilt (wieviele Plätze nebeneinander man für einen Sieg belegen muß). Die einstellbaren Siegesbedingungen sind eingeschränkt in Abhängigkeit von der eingestellten Spielfeldgröße, weil sie nur in einem gewissen Bereich einen Sinn ergeben.
Man kann zudem einstellen, daß den Spielern eine Spielfeldbewertung eingeblendet wird, um ihnen eine Entscheidungsunterstützung zu geben (oder auch eine KI zu debuggen).

Der Spielleiter kann einen Mitspieler, der ihm nicht gefällt, wieder rausschmeißen. Außerdem kann jeder sich selbst natürlich auch wieder rausschmeißen oder seine eigenen Spielereinstellungen ändern (Namen tauschen oder KI einstellen). Das gilt auch während eines Spieles noch (man kann eine Stellung also von jemand anderem übernehmen lassen).

Schließlich startet der Spielleiter das Spiel. Um ein Spiel starten zu können, müssen 2 Spieler angemeldet sein. Nach dem Start kann die Spielfeldgröße und die Gewinnbedingung nicht mehr geändert werden, bis das Spiel entweder abgeschlossen oder zurückgesetzt wurde.

Wenn man Lust hat, kann man mehrere Spiele gleichzeitig nebeneinander führen oder beobachten. Dazu macht man ein "neues Spielfeld" auf.

Man kann als Spielleiter ein Spiel komplett schreddern, indem man auf "neues Spiel" klickt. Macht man das als Mitspieler, wird man aus dem betreffenden Spiel abgemeldet und bekommt ein neues eigenes vor die Nase gesetzt.

Speichern / Laden

Man kann jederzeit - bei der Anmeldung oder mitten im Spiel - den Spielstand speichern. Das funktioniert durch das Anlegen eines Lesezeichens (Bookmark) über das Lesezeichen-Symbol ganz oben links.

"Spiel laden" funktioniert mit Klick auf das Lesezeichen. Es ist gleichbedeutend mit "neuem Spiel": Man wird automatisch Spielleiter des Spiels.
Wenn ein Spiel geladen wird, können die eingestellten Spieler sofort weitermachen, wenn sie immer noch mit derselben Browsersitzung teilnehmen.

Was eine "Browsersitzung" ist, möchte ich an dieser Stelle nicht bis zum Abwinken erläutern. Nur soviel: Es hängt mit den Cookies zusammen. Wenn die verschwinden (was man bei Browsern nach persönlichem Geschmack konfigurieren kann), ist die Sitzung beendet. Üblicherweise stellt man seinen Browser so ein, daß der Cookies beim Beenden des Programms löscht.

Falls man seine "Browsersitzung" "verloren" hatte, kann der Spielleiter einfach den betreffenden Spieler ab- und wieder neu anmelden (lassen). Der Spielstand wird dadurch nicht beeinflußt.

Seiten-Aktualisierung ohne Javscript

Das Spiel funktioniert ohne Javascript. Ich will ja meine Besucher nicht zu suizidösem Verhalten im Internet erziehen. Damit ein Multi-User-Spiel ohne Javascript funktioniert, muß mit einem sogenannten "Auto-Refresh" gearbeitet werden. Das führt dazu, daß das Bild hin und wieder (beim Aktualisieren) kurz blinkt.

Damit dieses Blinken nicht auf die Nerven geht und man einen Namen halbwegs ungestört eintippen kann, erfolgt die Aktualisierung in der Vorbereitungsphase sehr selten (alle 15 Sekunden). Falls jemand nicht solange warten will, kann er durch Klick auf "aktualisieren" die Sache früher anfordern (um zu sehen, ob jemand anderes schon beigetreten ist).
In der Spielphase erfolgt die Aktualisierung alle 3 Sekunden.

Spielverlauf

Das Spiel wird gespielt, indem die menschlichen Spieler, wenn sie dran sind, im Spielfeld ihr Zeichen in eines der Kästchen kritzeln. Dazu wird einfach geklickt.

Anleitungen zum Spielen finden sich im Web (vor allem in Arbeiten von Mathematikern zu diesem Spieltyp, die ich aber erst weiter unten bei den Computer-Gegnern verlinkt habe):
Eine kurze, vollständige Anleitung zur analytischen Lösung (ohne Spielzugsimulation, polynomiale Ordnung, menschenlesbar) von Eröffnung und Endspiel für die systematischen Varianten ohne extra Malus des Vorderhand-Spielers findet sich im Quellcode der Pauschal-KI (wird eventuell noch hierher übernommen).

Sobald keiner mehr gewinnen kann, ist das Spiel "remis".
Hat einer gewonnen, bekommt er einen Punkt in der Wertung gutgeschrieben, die ganz oben rechts neben den Spielernamen steht.

Wettkampf

Mit jedem Klick auf "starten" wird der Spielstart zwischen den Spielern getauscht. Wer das gerade nicht mag: Einfach zweimal hintereinander starten! Jeder Sieg bringt einen Punkt in der Spielerwertung ganz rechts oben neben den Spielereinstellungen.

Zu den Computer-Gegnern

Bei der Anmeldung kann man einstellen, daß man gegen einen Computergegner spielen will (oder auch zwei Computergegner gegeneinander spielen lassen möchte). Da gibt es momentan drei Auswahlmöglichkeiten:

KI Zufall

Der "Zufall"s-Gegner dient im wesentlichen zum Gegentest von anderen künstlichen Intelligenzen (KI) bzw. zum reinspielen für jemanden, der das Spiel noch nicht kennt. In ausführliche Analysen wird in der Wikipedia eingeführt. In der Regel sollte die Zufall-KI immer verlieren oder bestenfalls Remis spielen.

KI Pauschal

Der "Pauschal"-Gegner ist eine kleine Studie zur Lösung in einem "stellungsorientierten" Stil anstatt in einem "zugorientierten" Stil. Der "zugorientierte" Stil ist der einfachere, gern auch als "Brute Force" titulierte, bei dem in einer Tiefensuche alle möglichen Spielzüge der Spielteilnehmer durchsimuliert werden, bis sich eine Lösung oder ein hinreichend starker Hinweis auf Zweckmäßigkeit oder Unzweckmäßigkeit findet.

Die ganz brutal-stumpfsinnige Version besteht darin, immer bis zu einem eindeutigen Sieg oder Verlust zu suchen. Wenn die Spieler dabei nun einen gewissen Freiheitsgrad haben (und das ist ja nunmal bei allem, was sich unter dem Begriff "Spiel" vereinen oder darauf abbilden läßt der Fall), führt dies zu exponentiell mit der Tiefe der Simulation ansteigender Komplexität. Die Basis ist der Freiheitsgrad der Entscheidungen, der Exponent die Anzahl der hintereinander simulierten Spielzüge. Das führt dazu, daß dieses Verfahren von seinem Funktionsprinzip her nur für sehr kleine Problemstellungen zu eindeutigen Entscheidungen führen kann, bei größeren Problemen dagegen auf eine extrem geringe Spielzugtiefe beschränkt ist oder aber unfähig, optimale und eindeutige Ergebnisse zu liefern.

Um dem beizukommen, werden Filter zur Bewertung der zwischendurch entstehenden Stellungen eingesetzt, die so aggressiv wie möglich die möglichen Folgezüge einschränken sollen. Auf diese Weise wird die Basis des Exponentialausdrucks verkleinert, aber letztlich am Fakt des exponentiellen Komplexitätswachstums nichts geändert (-> Wikipedia: Minimax-Algorithmus und -> Wikipedia zu Schachprogrammen).

Eine Alternative zu diesem Ansatz besteht darin, von vornherein gar nicht erst von den MÖGLICHEN ZÜGEN aus loszudenken, sondern von den Wirkungen der Stellung. Und das Ziel nicht vordergründig im Erreichen einer Siegesstellung zu sehen, sondern im Maximieren der eigenen Wirkungsmöglichkeiten und dem Minimieren der gegenerischen Wirkungsmöglichkeiten aus denen der aktuellen Stellung heraus. Meine Vermutung ist, daß natürliche Gehirne eh nur nach diesem Ansatz funktionieren und genau deshalb den bisherigen maschinellen Ansätzen, die im wesentlichen alle auf Zugorientierung hinauslaufen, im allgemeinen überlegen sind.

Die "Pauschal"-KI ist nach dieser Herangehensweise geschrieben: Es wird kein einziger Zug simuliert (es gibt daher auch keine Suchtiefe, mit der man die "Intelligenz" des Algorithmus begrenzen könnte), sondern ausschließlich die eigenen und gegnerischen Wirkungsmöglichkeiten in der aktuellen Stellung bewertet und deren Verhältnis maximiert. Und das Bewerten geschieht eben auch nicht als Simulation von Zügen, sondern im rein pauschalen Bewerten von Potenzen. In DEREN Ermittlung besteht die Kunst dieser Herangehensweise. In diesem Fall wird die Reihenfüllung und Reihenkreuzung betrachtet (Operationen quadratischer Ordnung). Das Ergebnis ist ein Alorithmus, der auf dem kleinen TicTacToe-Feld 100%ig korrekt reagiert.

Das eigentlich interessante daran ist aber, daß dieser Algorithmus nicht exponentiell mit der Problem-(Spielfeld-)größe skalieren würde, sondern nur quadratisch. Ohne das jetzt überzubewerten (es handelt sich um ein extrem einfaches Spiel; und Bewertungen, die vom Grundprinzip der Idee durchaus vergleichbar sind, werden natürlich auch in Filtern der zugorientierten Algorithmen eingesetzt), ist es eine interessante Tatsache, daß man ein System, welches auf den erste Blick aus einer Spielzugfolge besteht, auf eine Weise optimal lösen kann, bei der man komplett auf Verfahren mit Spielzugsimulation und damit exponentiell wachsender Komplexität verzichtet...

Die skalierbare Variante
Inzwischen ist das Spiel aufgebohrt bis zum großen Go-Feld (19 x 19), und es zeigt sich, daß die Pauschal-KI natürlich nicht perfekt ist und umso mehr Schwachstellen zeigt, je größer das Brett und damit die Freiheiten für Finten werden. Da würde dann wieder eine Simulation den Erfolg bringen. Allerdings habe ich das erstmal hintenan gestellt.

Was ich nochmal probiert habe, ist eine Veränderung der KI hin zu besserer Berücksichtigung von Zwickmühlen und gegenseitigen Abhängigkeiten (bei der Pauschal-KI ist das zu einem gewissen Grad Nebenprodukt ihrer Funktionsweise, ohne aber exakt zu sein). Das erwies sich aber auch als sehr aufwendig und ist daher noch nicht fertig und erstmal nur als optionale "Beratung" für den menschlichen Spieler zugänglich.

KI gomokuonline.com

Diese KI unterstützt erstmal nach dem, was unmittelbar aus dem Quellcode herausgelesen werden kann, ein Brett mit 19 x 19 Feldern und 5-in-einer-Reihe. Vage Anhaltspunkte gibt es, daß die Anzahl der Zeilen und Spalten variabel sein könnte.
Wer gegen diese KI spielen möchte, muß momentan zuerst mal die Feldgröße auf 19 und die Gewinnanforderung auf 5 einstellen.

Die KI ist in etwa vergleichbar mit der Pauschal-KI. Es ist ganz lustig zuzugucken, wenn die beiden sich gegenseitig mit ihren typischen Verhaltensweisen beharken. Insbesondere wie recht systematisch die Pauschal-KI den Gegner blockiert und mühsam außen herum Zwickmühlen vorbereitet, diese dann aber immer wieder links liegen und vom Gegner zumüllen läßt, bis sie selbst in eine Falle tappt... :->

KI boulter.com

Unterstützt Felder der Größe 3...7 mit derselben Spanne für Gewinnforderungen. Hat auch ein paar (möglicherweise gezielt eingebaute) Schwächen, die bei dem eigentlich nicht zu verlierenden "4-in-einer-Reihe" auf dem 6er/7er Feld dem Zweitziehenden einen Sieg ermöglichen. Die Pauschal-KI ist dafür leider meist zu kurzsichtig.

Die mathematisch exakte Variante

...Und ganz nebenbei bemerke ich gerade, daß der hier gewählte Ansatz bereits von einem Mathematiker L. Victor Allis im Jahre 1994 ausführlich untersucht und für hilfreich befunden wurde. Er nannte ihn "Threat-Space Search". Ihm ging es darum, Techniken zu untersuchen, wie man ein "klassisch" modelliertes Problem, welches man in seiner klassischen Darstellung nicht effektiv behandelt bekommt, durch Transformation in ein anderes Modell mit anderer Darstellungsweise mitunter stark vereinfachen kann. Er blieb allerdings der grundsätzlichen Herangehensweise treu, ein zug-basiert definiertes System auch zugbasiert lösen zu wollen. Daher lag seine Aufmerksamkeit auf der Optimierung der Zugfolgenauswahl, während die Zustandsmodellierung auf einem bestimmten Punkt des Zugfolgenbaumes nur sekundärer Aspekt war.

Bei der hier bei der "Pauschal-KI" angesetzten Vorgehensweise liegen die Prämissen entgegengesetzt: Mit der Optimierung der Modellierung des Zug-Zustands soll die Notwendigkeit einer Zugsimulation nach Möglichkeit vermieden werden.
Bei größeren Feldern erfordert dies allerdings immer noch eine Ergänzung durch eine klassische Suchstrategie.

Das Spiel ist generalisiert betrachtet ein "n-in-einer-Reihe"-Spiel.
Kurzeinführung bei Wolfram Research...
Alternative Namen für verschiedene Bordgrößen (aber immer dasselbe Spielprinzip):
  • TicTacToe (3 x 3 : 3)
  • Qubic (4 x 4 x 4 : 4) (3D)
  • Gomoku (15 x 15 : 5)
  • Renju (Gomoku mit starken Einschränkungen des Starters)

Ist die Gewinnanforderung hinreichend groß (>7), dann ist immer ein Remis möglich, weil das Spielfeld hinreichend schnell durch Steine von einem Verteidiger zerschnippelt werden kann, wo immer der Angreifer versucht, etwas zusammenzubasteln. Für Gewinngrößen von 8 und mehr ist dies systematisch durch Spiel nach einfachen "Paarungsregeln" möglich.
Beim Typ "5 in einer Reihe" ist selbst für die mit kräftigen Behinderungen für den Erstzieher ausgestattete Version "Renju" inzwischen als erzwingend gewinnbar gelöst worden (PDF).

Ja, es ist schon interessant, was man aus so einem auf den ersten Blick trivial einfachen Spiel alles herausholen oder hineinlegen kann, gell?!

Zur Entstehung

Tic-Tac-Toe ist ein typisches Begleitprojekt in meinen Einsteiger-Lehrgängen für Programmierer. Für jede von mir schon mal längerfristig unterrichtete Programmiersprache liegt ein solches Tic-Tac-Toe vor. Dieses hier ist nun als "Anfütterung" für einen HTML/PHP-Einsteigerkurs entstanden.

Im Kurs werden Grundzüge der Funktion dieses Programms vermittelt und nachgebaut. Nicht alle Details - dazu reicht die Zeit nicht -, aber immerhin soviel, daß die Grundfunktion eines Browser-Server-Gespanns und das Zusammenwirken mehrerer Benutzer in einer Webanwendung rübergerbracht wird.

Das Spiel ist gleichzeitig einfach genug, um von Einsteigern verstanden und nachgebaut werden zu können, aber auch komplex genug, um... Wenn man es drauf anlegt, kann man damit etliche Wochen zubringen.
Als Anregung sollte das dicke hinreichen!

Für an der Programmierung Interessierte hier die Quelltextansichten:

2012-10-18 23:22:27 Angreifbarkeit festgestellt...

Tja, nicht ganz ohne, die Veröffentlichung von Programmcodes, gelle?!

Da Spiel hatte noch mehrere Stellen, wo Parameter nicht gegen Hacking gesichert waren. Unter anderem gab es eine Möglichkeit, den hier liegenden Code als Proxy zu mißbrauchen. Der letze Besucher aus dem Forum www.php.de hatte das in einen POST verpackt, der bisher noch nicht gelogged wurde. Das ändern wir mal auf die Schnelle...

Bitte um Wiederholung des Versuchs...

Mit der nachträglichen Sicherung werden die Spielstände anders verpackt. Alte sind damit nicht mehr gültig (sollte hier aber irrelevant sein).