Eine große Frage beim Brettspiel „Othello¹“ ist: " Kann Weiß immer gewinnen?".
Wahrscheinlich ist die Antwort NEIN.
Es gibt einen Algorithmus der diese Frage beantworten kann.
Der Bestimmtheitssatz von Zermelos legt fest. Das ein Spiel immer
mit Sieg, Remis, oder Niederlage endet. Der Algorithmus der Hier erläutert werden soll betrachtet zusätzlich das Remis als Niederlage für Weiß.
Wenn der Algorithmus beim Beginn des Spiels anfängt dauert die Ausführung allerdings zu lange, als das man dann das Ende der Abarbeitung des Algorithmus erleben würde.
Wenn der Algorithmus jedoch bei einer bestimmten Spielsituation startet bei der nur noch
wenige Felder Leer sind - z.B. 20 leere Felder - kann er die Antwort, in einer Zeit, liefern, die für uns ausreichend ist.
Der Algorithmus ist möglichst einfach und verständlich.
Er nutzt die Rückwärtsinduktion.
Deshalb sucht der Algorithmus nicht die beste Lösung für Weiß oder Schwarz.
Er durchläuft nicht jede Variante des Spielbaums, ab der bereits vorliegenden Situation, sondern nur einige Varianten.
Er sucht nur solange, bis die Frage für den weiteren Bereich des Spielbaums hinreichend bzw. alternativlos beantwortet ist. Dann kann die Rückwärtsinduktion einsetzen.
Was sind die hinreichenden Ergebnisse nach denen der Algorithmus schaut?
Für die Frage ob Weiß immer gewinnen kann, ist es für Weiß hinreichend, wenn es am Ende mehr Steine auf dem Feld hat, als Schwarz.
Wenn Weiß und Schwarz gleich viele Steine haben ist dies für Weiß kein hinreichendes Ergebnis.
Situationen bei denen Schwarz und Weiß gleich viele Steine haben, und bei denen Schwarz mehr Steine hat, beantworten die Frage damit eindeutig mit Nein.
Hinreichend ist die Antwort auch immer nur dann wenn die jeweils andere Farbe „Alles versucht hat“, um Ihr Ziel zu erreichen.
Der Algorithmus durchläuft also jeweils nur EINEN hinreichenden Verlauf weiter abwärts im Spielbaum.
Der Algorithmus sagt nichts über die Gesamtzahl der hinreichenden Verläufe oder über die absolute Zahl der jeweiligen Steine oder ihrer Positionen.
Die Beschreibung für einen Algorithmus der die Frage beantworten kann.
Es ist leichter die Wirkungsweise des Algorithmus zu verstehen, wenn wir uns einen realen Spielablauf vorstellen. Bei dem
der Algorithums dann jeweils die Rolle des einen oder anderen Spielers einnimmt.
Nacheinander hat er dann dann also die Rolle „Weiß“, oder die Rolle „Schwarz“.
Es wird immer wieder nur dieselbe Frage gestellt: „Kann Weiß immer gewinnen?“
Und auf eine Antwort vom möglichen Spielbaum abwärts gewartet.
Die Rollen bekommen dann immer eine Antwort. Und sie wissen das die Antwort objektiv richtig ist.
Ihr eigenes Verhalten und ihre eigene Antwort richtet sich nach ihrer Rolle. Und sie halten sich immer an das vorgeschriebene Verhalten für die Antwort.
Damit ein Ergebnis beurteilt werden kann muss der Ablauf bis ans Ende untersucht werden.
Aber nicht jede Variante des Ablaufs.
Der Start
Der Algorithmus beginnt also mit einer beliebigen aber erlaubten Abfolge von Zügen, bis zum Ende.
Ohne Logik dazu ob es ein guter oder schlechter Zug sei.
Das Ende einer Zugabfolge ist immer erreichbar. Entweder weil keine Felder mehr frei sind oder
weil Weiß und Schwarz keinen erlaubten Zug machen können. (Das Ende kommt unweigerlich)
Ist das Ende erreicht wird eine Auswertung vorgenommen.
Die Auswertung
Weiß hat mehr Steine? Dann und nur dann lautet die Antwort auf die Frage ob Weiß gewinnt "JA".
Ansonsten lautet die Antwort der Auswertung "NEIN".
Diese Antwort bei der Auswertung wird direkt an den vorherigen Zug gegeben.
Der letzte Zug
Der Letzte Zug ist ein Sonderfall. Nach Ihm wird ein Spielende festgestellt und
er bekommt seine Antwort von der Auswertung. Das Ergebniss der Auswertung gib er einfach als Antwort weiter zurück. Denn die Antwort von der Auswertung ist für den letzen Zug "alternativlos", "wahr" und vollständig.
Spielzüge vor dem letzten Zug
Der Algorithmus muss wissen wer den Zug gemacht hat, der jetzt nicht ein letzter Zug ist.
Der Algorithmus muss auch wissen welche Züge noch in der jeweiligen Situation möglich wären.
Der Algorithmus muss auch die Regeln des Spiels kennen und fehlerfrei anwenden, um diese möglichen Situtation zu errechnen.
Dieses Wissen über die möglichen Züge muss der Algorithmus jedoch erst dann errechnen wenn es benötigt wird.
Denn das ist beim Ablauf des Algorithmus der zeitlich und logisch aufwändigste Teil.
Die Frage „Kann Weiß immer gewinnen?“ wurde also rekursiv von der Startsituation an jeden weiteren Zug weitergegeben, dessen Ausführung erfolgt.
Ein Spielzug erwartet vom nächsten Spielzug oder am Spielende von einer Auswertung eine Antwort.
Wer den nächsten Zug macht, oder machen muss, ist für das eigene Verhalten, in Bezug auf die Rückgabe der Antwort, nicht von Bedeutung, sondern nur die Antwort die ein Zug bekommen hat, und die eigene Rolle.
Der vorletzte Zug, der ersten beliebigen Abfolge, bekommt also als erster eine Antwort von einem nachfolgendem Zug.
Wann und wie antworten Spielzüge die nicht der letzte Zug sind?
Auswertung und Verhalten für einen Spielzug der Rolle Weiß:
Weiß fragt also zu seinem Zug, „Kann Weiß immer gewinnen?“. Der nächste Zug antwortet immer mit der Wahrheit.
Bekommt Weiß die Antwort "JA" meldet Weiß diese Antwort sofort zurück, an den vorherigen Zug.
Weiß muss, bei Antwort "JA", nicht wissen welche Antworten von anderen möglichen Zügen kommen würden.
Bekommt Weiß aber die Antwort NEIN, versucht Weiß einen anderen Zug auszuführen.
Hat Weiß bei keinem seiner möglichen Züge die Antwort "JA" erhalten, dann meldet Weiß: "NEIN", an den vorherigen Zug.
Bei der Implementierung des Algorithmus sollte man darauf verzichten feststellen zu wollen welcher nächste Versuch ein vermeintlich "guter Zug" wäre, oder welches der beste Zug wäre. Weil es ja wirklich „nur“ um die Antwort auf die Frage geht.
Auswertung und Verhalten für einen Spielzug der Rolle Schwarz:
Ein Spielzug in der Rolle Schwarz geht ähnlich vor.
Er versucht jedoch die Antwort "NEIN" zu erhalten.
Sobald Schwarz die Antwort "NEIN" bekommt meldet er diese, an den vorherigen Zug, zurück.
Denn dann war diese Zugmöglichkeit für ihn erfolgreich und er muss nicht weiter nach einem möglichen Erfolg suchen.
Bekommt Schwarz die Antwort "JA", versucht Schwarz also einen anderen Zug auszuführen.
Konnte Schwarz bei keinem seiner möglichen Züge die Antwort "NEIN" erhalten meldet er "JA", an den vorherigen Zug, zurück.
Die Antwort des Algorithmus
So bewegt sich der Algorithmus aufwärts und abwärts durch den Verlaufsbaum bis er wieder am Ausgangspunkt zurück kommt. Die Rückwärtsinduktion ist dann abgeschlossen.
Dort gibt der Algorithmus auf die gestellte Frage einfach "JA" oder "NEIN" zurück.
Für die vor dem Start des Algorithmus vorhandene Spielsituation ist jetzt die Frage beantwortet.
Was würde der Algorithmus am Anfang des Spiels als Antwort geben?
Wahrscheinlich ist die Antwort "NEIN".
(Denn es wird in anderen Quellen ein mögliches Remis vermutet)
Aber Das kann man nur sagen wenn man den Algorithmus vom Beginn des Spiels an starten würde.
Selbst der stark reduzierte hinreichende Verlaufsbaum ist wohl bei derzeitigen Rechenkapazitäten
noch zu umfangreich als das man dann das Ende der Abarbeitung des Algorithmus erleben würde.