Diese Webseite ist ein Tool, um eine spieltheoretische Überlegung zum Brettspiel Othello¹ zu untersuchen. Im eingeloggten Bereich kommt man zu diesem Tool. Es ist nicht dazu gedacht das Spiel in "klassischer Weise" zu spielen.
Othello¹ zählt zu den sogenannten deterministischen Spielen. Was heißt das?
- Es gibt keinen Zufall.
- Es gibt keine versteckten Informationen, die nur ein Spieler hätte.
- Regeln bestimmen welcher "Zug" als nächstes gemacht werden kann bzw. muss.
Die Große Frage
Die große Frage ist: "Kann Weiß immer so setzen, das am Ende mehr weiße Steine auf dem Feld stehen?"
Die bekannten Regeln
- Das Feld besteht aus 8 Reihen und 8 Spalten (Wie das Schachbrett doch ohne Unterscheidung einer Farbe).
- Das Spiel beginnt damit das 2 weiße und 2 schwarze Steine diagonal in der Mitte des Spielfeldes liegen.
- Es beginnt immer Schwarz.
- Es kommen nur Felder für das Setzen infrage bei denen mindestens 1 Stein der anderen Farbe in senkrechter, waagerechter oder in diagonaler Richtung eingeschlossen werden kann.
- Man muss immer setzen, wenn man kann. Es gibt kein freiwilliges Aussetzen.
- Es müssen ALLE neu eingeschlossene Steine in allen Richtungen in die eigene Steinfarbe umgewandelt werden.
- Kann eine Farbe nicht setzen, ist wieder die andere Farbe dran.
- Das Spiel endet wenn alle Felder belegt sind oder wenn keine Farbe mehr setzen kann.
- Man kann das Spiel als beendet ansehen, wenn eine Farbe mehr als 32 Felder hat, die nach den Regeln für das Setzen nicht mehr umgewandelt werden können.
Was man über den Anfang wissen sollte
Das Spielfeld ist quadratisch. Die 4 Felder, die Schwarz als Möglichkeiten hat, sind aufgrund der symmetrischen Anfangssituation für den Verlauf des Spieles völlig gleichwertig. Für die Untersuchung der "Großen Frage" muss man also nur eine dieser vier Setzmöglichkeiten betrachten. Die anderen Setzmöglichkeiten führen zu gedrehten bzw. gespiegelten Verläufen des Spiels. Beim Ziel geht es "nur" um die Anzahl der Steine eigener Farbe und nicht darum, wo diese stehen.
Schwarz "beginnt" also, aber hat nicht wirklich eine Wahl. In Wirklichkeit startet das Spiel also damit das Weiss setzt nachdem das Spielfeld diesem Stand entspricht:
D.h. eigendlich starten alle Othello¹ Spiele genau so. Weiss kann dann eines der grauen Felder besetzen.
Der Grund für die Große Frage
Somit ist also Weiß die Farbe, die als Erstes die Möglichkeit hat, den deterministischen Verlauf in eine bestimmte Richtung zu lenken. Aufgrund dieses Umstandes ergibt sich die Vermutung, das Weiß immer eine Wahl treffen könnte, die dazu führt, dass am Ende mehr weiße Steine auf dem Feld sind.
Für die kleineren Spielvarianten mit 4x4 Positionen und 6x6 Positionen soll bereits bewiesen sein, dass diese Vermutung zutrifft. Bei der 4x4 Variante sind es sogar so wenige, dass man alle diese Verläufe auflisten kann.
Was könnte der Beweis sein?
Selbst wenn die Antwort bekannt wäre und die Vermutung sich als richtig erwiesen hätte, könnte kein Mensch sich all die Verläufe ansehen, bei denen Weiß tatsächlich am Ende mehr Steine auf dem Feld hat. Wenn Weiß sich immer richtig entscheidet, kann Schwarz daraufhin meist aus mehr als 3 Feldern seine Reaktion wählen. Und für jeden von Schwarz gewählten Zug müsste Weiß wiederum die "richtige" Reaktion wählen. Somit ist die geschätzte Zahl der richtigen Wege, auf denen dann Weiß gewinnen würde, etwa 3^30 oder größer. Selbst diese vorsichtige Schätzung ergäbe also etwa 2,058911321×10¹⁴ Verläufe, die bekannt sein müssten, um den Beweis zu erbringen. Selbst wenn man jeden dieser "Richtigen Verläufe" nur eine Zehntel-Sekunde anschaut bräuchte dafür ein einzelner Mensch etwa 650 Tausend Jahre.
Was nun?
Könnte ein nachgewiesener weise fehlerfrei, schnell, arbeitender Algorithmus, der nachgewiesenermaßen nicht manipuliert wurde, die Antwort geben? Aber dann diese Antwort als Beweis zu akzeptieren hängt davon ab, dass der Beweis dafür geliefert wird, dass der Algorithmus wirklich fehlerfrei und ohne Manipulation die Antwort gefunden hat.
Außerdem würde eine Datenbank, die alle erfolgreichen Verläufe speichert, mehr als 2 x 10^14 Datensätze verwalten müssen. Würden wir nur etwa 2 KB für jeden Datensatz veranschlagen, wäre dies ein Speicherbedarf von über 400 Petabyte. Es muss ja in jedem Datensatz zumindest der Verlauf eindeutig beschrieben sein für den er gilt und das Ergebnis dieses Verlaufs.
Schon aufgeben?
Vielleicht muss man nicht alle richtigen Wege speichern bzw. sich wirklich ansehen. Denn im Verlauf eines Spiels entstehen auch sogenannte "Fixe Steine". Das heißt, diese können bei allen weiteren Spielverläufen ihre Farbe nicht mehr ändern. Ist durch die Anzahl der entstandenen "Fixen Steine" vor dem Ende des Spiels (min. 33) klar, dass Weiß bereits das Ziel erreicht hat, könnte dies die zu betrachtenden Verläufe, die bekannt sein müssen, um einige Größenordnungen vermindern.
Die richtigen Verläufe von Weiß sind meistens so, dass Schwarz nur wenige bzw. nur eine Reaktionsmöglichkeit bleibt.
Es bleibt auch noch der nicht gefundene Königsweg, bei dem für bestimmte Situationen mit einer Formel beschrieben wäre, dass Weiß am Ende garantiert mehr Steine haben wird, ohne diese Verläufe jemals ausprobiert zu haben. Auch diese Formeln könnten die Anzahl der Verläufe, die durch "probieren" untersucht werden müssten, um weitere Größenordnungen vermindern. Lassen sich also solche Formeln finden?
Was macht das Tool im "Automatik-Modus"?
Leider befasst sich das Tool nicht mit dem Finden solcher Formeln. Könnte aber später diese verwenden, wenn Sie gefunden werden. Bis jetzt bewertet das Tool die möglichen Setzmöglichkeiten in der gegebenen Situation aufgrund der Position des Feldes. Aus der Position ergibt sich eine wahrscheinliche Anzahl von Umwandlungen bis zum Ende des Spiels.
Bei den Randfeldern schaut die Bewertungslogik auch, welche gesetzten Farbfelder oder Freifelder sich noch auf der gleichen Randlinie befinden. Und bei den 4 Feldern in einer Ecke, wie viele Felder in dieser Ecke noch frei sind. Die verschiedenen Anzahlen von Umwandlungen und Auswertung zu den Randlinien-Situationen werden dann dazu verwendet, die Setzmöglichkeiten in eine priorisierte Reihenfolge einzuordnen. Wobei u. a. Setzmöglichkeiten mit geraden Umwandlungen meist eine höhere Priorität bekommen.
Diese Bewertung der Setzmöglichkeiten erfolgt für beide Farben mit der gleichen Logik. Liefert aber bei Weitem nicht sicher die "allerbeste Reaktion". Dennoch dient Sie dafür sich beim eigentlichen Durchlauf entlang des Verlaufsbaums von Knoten zu Knoten zuerst für einen vermeintlich "Guten Weg" zu entscheiden, sofern noch kein Weg untersucht wurde. Bei Erfolg bleibt der Automatische Ablauf erst mal bei dieser Reaktion.
Ist ein Weg bis zum Ende untersucht, wird das Ergebnis ausgewertet. Und es wird gespeichert wer Erfolg hatte. Diese Speicherung erfolgt nach und nach auch für Knoten, die nicht am Ende des Spiels sind.
Sobald Schwarz an einem Knoten (vor seinem nächsten Zug) erkennt, dass Weiß immer "Erfolg" hat, probiert dann Schwarz eine der jeweils verbleibenden Möglichkeiten, die es noch nicht probiert hat, in der Reihenfolge ihrer Bewertung absteigend. Aber eben erst dann. Schwarz bleibt auf einem Weg, solange nicht ermittelt wurde, dass Weiß immer "Erfolg" hätte. Stellt Schwarz allerdings fest, dass es für einen Weg immer "Erfolg" hat, bleibt es bei der Auswahl dieser Setzmöglichkeit.
Auch Weiß bleibt solange auf dem einmal eingeschlagenen Weg bis deutlich wird, dass es bei einer bestimmten folgenden Entscheidung von Schwarz sein Ziel nicht erreichen kann. Und probiert erst dann eine andere Setzmöglichkeit.
Wenn es keine Möglichkeit mehr gibt, abwärts eines "Knotens" das Ziel zu erreichen, schaut Weiß oder Schwarz beim Vorgängerknoten seiner Farbe danach, welche andere Möglichkeit noch nicht untersucht wurde. Und wird dann diesen Weg auswählen.
Durch diese Vorgehensweise im "Automatik-Modus" werden ein oder mehrere Spielverläufe ausgeführt, deren Ergebnis in der Datenbank jeweils gespeichert wird. Die weiteren automatischen Spielverläufe werden dann meist einen neuen Weg gehen. Manchmal wird ein Spielverlauf mehrmals in gleicher weise ausgeführt. Dann werden aber danach beim Speichern weitere Informationen für vorher liegende Knoten geändert. Durch diese neuen Informationen wird dann bei einem der nächsten Abläufe ein anderer Weg gewählt.
Es ist möglich, die automatischen Verläufe jeweils ab einer bestimmten Spielsituation zu starten, die man zuvor im manuellen Modus erreicht hat.
Ein Film sagt mehr als Tausend Worte
Das Spielfeld Tool näher erkärt
Schau hier: LEGENDE