Unter Sogo verstehen wir die 4x4x4 große 3dimensionale Variante des Tictactoe mit Gravity. Es wird abwechselnd mit W und S auf eine der maximal 16 freien Positionen gesetzt. Wer 4 Steine in seiner Farbe in einer Reihe placiert, gewinnt. Es gibt ein ähnliches Spiel namens Qubic, das sich insofern unterscheidet, daß alle unbesetzten Positionen sofort belegt werden können. Qubic ist ein Gewinn für den Beginner W (Patashnik 1980, Allis Schoo 1992). Ein Programm, das die von Patashnik entwickelte Strategie umsetzt, ist unter dem Namen qubist auf Sourceforge zu finden-https://sourceforge.net/projects/qubic/files/qubist/

Erfahrungsgemäß liegen beim Sogo die Probleme vor allem in der dritten Ebene. Ein Remis habe ich noch nicht erlebt, jedoch vermute ich, daß W keine Gewinnstrategie hat, und beide Teilnehmer bei optimalem Spiel ein Remis erzwingen können.

Sogo hat wesentlich weniger Symmetrien als Qubic, nämlich nur diejenigen, die die untere Ebene fix lassen. Trotzdem ist die volle Symmetriegruppe vom Qubic interessant.

Gewinnstellungen sind zunächst die 16 kantenparallelen Geraden zu jeder der 3 Richtungen im Raum, dann die beiden Diagonalen in jeder der 12 Flächen und die 4 Raumdiagonalen, insgesamt 76. Die erste Klasse der Gewinnstellungen zerfällt in 2 Unterklassen von je 24, je nachdem ob starke Punkte (s.u.) beteiligt sind oder nicht.

Die Positionen sind zerfallen in 2 Klassen, die sich in der Anzahl der möglichen Gewinnstellungen unterscheiden. Die 8 Ecken sowie die 8 Punkte im Inneren des Würfels liegen auf den 4 Raumdiagonalen, alle anderen nicht. Sie sind also 16 starke Punkte mit 7 möglichen Gewinnstellungen. 48 schwache Punkte sind an jeweils 4 Gewinnstellungen beteiligt.

Alle Symmetrien müssen so beschaffen sein, daß sie alle Punkt- und Gewinnklassen fix lassen.

Die Symmetriegruppe wird von folgenden Transformationen erzeugt:

• Spiegelung an einer vertikalen Fläche (Ordnung 2)
• Drehung um 90 Grad um eine vertikale Achse (Ordnung 4)
• Punktspiegelung um die Mitte (Inversion) (Ordnung 2)
• Drehung um 120 Grad an eine Raumdiagonalen (Ordnung 3)
• Tausch der schwachen Punkte innerhalb Kante und Fläche (Scramble, Ordnung 2)
• Tausch der inneren starken Punkte mit den äußeren (Evisceration, Ordnung 2)

Die ersten 4 sind bereits durch ihre Aktion auf den 8 Ecken vollständig bestimmt. Nur die ersten beiden erzeugen die Symmetriegruppe für das Sogospiel.

Zunächst ist nicht bekannt, ob es Remis-Stellungen gibt. Die Menge der Remis-Stellungen ist jedenfalls fix unter den Aktionen der Qubic-Symmetriegruppe, und außerdem dem Tausch zwischen W und S. Mit einem Programm wurde eine gefunden. In Hex-Schreibweise 0x31cddc2282577da5ULL.

Die 384 Abbilder unter den o.g. Symmetrien sind alle verschieden.

Es stellt sich die Frage, ob es noch mehr Remis-Stellungen gibt. Dazu wurde zunächst die Frage geprüft, wieviel starke Punkte enthalten sind. Im konkreten Fall sind es 9, somit bei den Komplementen 7. Es ist zu vermuten, daß es auch Remis-Stellungen mit 8 starken Punkten gibt.

Ein strategischer Gewinn (dh einer, der nicht auf einem Versehen des Gegners beruht) ist bei Qubic nur möglich, wenn ein Doppelzwingi erzeugt wird, dh. eine unbesetzte Kreuzung zweier mit jeweils nur zwei eigenen Steinen besetzter Gewinnstellungen. Bei Sogo besteht die zusätzliche Möglichkeit, den Gegner zum Besetzen einer vergifteten Position zu zwingen, ggfs. durch Zugzwang.

Bei Qubic ist es entscheidend, den Zeitpunkt zu erkennen, an dem ein Doppelzwingi erstmals möglich ist, andernfalls könnte Sw bis dahin Spiegelstrategie wählen und als erster den Angriff starten. Dementsprechend erwarten wir die kürzete Entscheidung, indem Sw den Spiegelzug als ersten probiert. Für Ws einfach immer nur den Zug mit den starken Punkten zu wählen, bis keine mehr da sind, führt aber zu Remis, verschenkt also den möglichen Sieg.

Durch dir Patashnik-Publikation ist bekannt, daß Ws die Entschiedung in maximal 40 Zügen erreichen kann, somit kann jeder Spielverlauf mit größerer Tiefe als remis gewertet werden, ohne das Ergebnis zu beeinflussen.

Eine interessante Unterfrage ist, ob evtl. das Auftreten einer Vergiftung bereits ein Indiz eines Spielfehlers ist. Das läßt sich im Programm prüfen, indem mit Flag -g bereits eine Vergiftung als verloren gewertet wird. Erhält man beim Lauf wieder Remis als Ergebnis, weiß man einerseits, daß keiner eine Vergiftung erzwingen kann, andererseits brauchen die Zweige mit Vergiftung auch nicht mehr untersucht zu werden. Könnte man eine Vergiftung erzwingen, wäre der Handlungsspielraum eines Spielers dadurch stark eingeschränkt, daß er entweder eine Entgiftung erreichen muß oder in Abhängigkeit von der Horizontallage, in der die Vergiftung liegt, am Ende durch Zugzwang zu Gewinner oder Verlierer würde.

Zunächst werden die heuristisch stärksten Züge beider Parteien ausprobiert, bis eine Remisstellung gefunden wurde. Die Stärke bemißt sich aus der Summe der besetzten eigenen und vereitelten gegnerischen Gewinnstellungen, mit Gewicht 3 bei Erstbesetzung, zwei bei Zweitbesetzung. Eine Drittbesetzung erhält nur einfaches Gewicht, außer sie wird in 2 Stellungen zugleich erreicht (Zwicksituation) (oder – ist aber momentan nicht implementiert – sie vergiftet eine Position, dh. der Platz unter der freien Stelle ist unbesetzt, so daß der Gegner dort nicht hinsetzen kann).

Bis eine Remisstellung erreicht wird, werden Züge nach ihrer Stärke ausgewählt. Von dieser Zugfolge ausgehend wird dann rekursiv rückwärts geprüft, ob eine Partei nicht vielleicht doch einen nicht direkt erkennbar stärkeren Zug gehabt hätte. Alle ausgewerteten Stellungen bis zur Tiefe 56 (= 8 Züge vor Vollbesetzung) werden zwischengespeichert, um gegebenenfalls eine Neuberechnung zu vermeiden. Dabei werden zwei Optimierungen ausgeführt. Alle Stellungen werden normalisiert, indem die 8 Symmetrien angewandt werden, und davon die numerisch minimale ausgewählt wird. Für tote Gewinnstellungen ist nicht relevant, welche der möglichen Besetzungen den Tod verursacht haben, somit können Postionen, die nur in toten Gewinnstellungen liegen, auf einen festen Wert (schwarz) gesetzt werden.

Zunächst habe ich die Anzahl der abzuspeichernden Stellungen stark unterschätzt. Infolgedessen versuchte ich, die Daten zwecks schnellerer Findung in einm AVL-Tree zu speichen. Das ist speicherverbrauchs-ineffizient, da neben den Daten für jeden Eintrag 3 Pointer zusätzlich zu den eigentlichen Daten benötigt werden. Auf einem 64-bit-Rechner ist das eine Vervierfachung der zu speichernden Daten, wenn man nur einen 62-Bit-Hash (die beiden anderen Bits braucht man für den Spielwert) speichert. Ohne Hash liegt die Ineffizienz immer noch bei 5:2 64-Bit-Worte.

Eine weitere Optimierung erwies sich als notwendig, nämlich ein Bloomfilter, das Stellungen, die nicht gespeichert sind, schnell und sicher erkennt. Mit Bloomfilter ist es möglich, einfach linear zu suchen, solange weniger als 1000 Stellungen gespeichert gepeichert sind. Gelegentlich sortiert man dann die Stellungen und sucht im sortierten Teil binär.

Das Spiel Sogo ist gelöst: Remis bei fehlerfreiem Spiel.

C++-Programm

Auf einem AMD PRO A10-9700 mit 32 GB Hauptspeicher wurden ca. 2 Stunden benötigt.

Wenn das o.a. Programm mit der Option -q gestartet wird,berechnet es den Spielausgang nach Qubic-Regeln. Auf meinem Rechner wird eine knappe Minute dafür benötigt. Da das Ergebnis aber schon bekannt war, diente dieser Teil nur als Gegenprobe für die Programmlogik. Der Umstand, daß nach dem Fund einer Gewinnstrategie der Spielbaum entscheidend verkleinert werden kann, führt zu einer wesentlichen Beschleunigung.