DIE GO-REGEL, DIE DIE ANTWORT ÄNDERT

Ein Spiel zu lösen heißt, seinen Ausgang zu kennen, wenn beide Seiten perfekt spielen. Auf einem Go-Brett ist dieser Ausgang ein Wert: die Zahl der Punkte, mit der Schwarz bei perfektem Spiel gewinnt – 28 auf einem 4×7-Brett heißt, dass Schwarz alle 28 Schnittpunkte besitzt. Dame wurde 2007 gelöst, ebenso Hex auf kleinen Brettern. Für Go gibt es Computerbeweise für viele Bretter mit bis zu 30 Schnittpunkten, meist von einem Programm namens MIGOS (2003 und 2009).

Es gibt einen Haken. Diese klassischen Ergebnisse verwenden eine vereinfachte Regel für wiederholte Stellungen – eine einfache „Ko“-Regel – man darf einen einzelnen Stein, der gerade einen eigenen Stein geschlagen hat, nicht sofort zurückschlagen, was dieselben zwei Züge endlos wiederholen würde – plus besondere Konventionen: Ein Passen hebt ein Ko-Verbot auf, eine Partie endet bei einer wiederholten Stellung und so weiter. Diese Konventionen sollten sicherstellen, dass der Wert einer Stellung nicht davon abhängt, wie sie erreicht wurde.

Die Regel, nach der tatsächlich gespielt wird

Die chinesischen Regeln, wie sie geschrieben stehen, und das Computer-Go verwenden positionelles Superko: Kein Zug darf irgendeine Gesamtstellung des Bretts wiederherstellen, die in der Partie bereits vorkam. Unter dieser Regel zu lösen ist viel schwieriger, weil die Zulässigkeit eines Zugs nun von der gesamten Geschichte der Partie abhängt. Das macht drei Werkzeuge zunichte, die das Lösen überhaupt möglich machen:

• Ergebnisse wiederverwenden für dieselbe Stellung, die auf einem anderen Weg erreicht wurde – die beiden Wege können unterschiedliche Züge verbieten;
• sichere Gruppen und Gebiete erkennen ohne Suche, was voraussetzt, dass der Besitzer Eindringlinge immer schlagen kann – unter Superko kann ein solches Schlagen verboten sein;
• Züge beschneiden (pruning), die nie helfen, etwa das Füllen eines eigenen Auges – einer der leeren Punkte, die eine Gruppe braucht, um am Leben zu bleiben – unter Superko kann ein solcher Zug entscheidend werden.

Der Preis war enorm: Mit einer Superko-Variante brauchte MIGOS 1,1 Stunden für das 4×4-Brett, gegenüber 3,3 Sekunden unter einfachem Ko. Die erste Superko-Lösung von 5×5 dauerte 2024 5,25 Stunden auf sechs Prozessen. Jenseits von 5×5 war kein Brett mit mindestens zwei Reihen unter Superko gelöst worden.

Eine Abkürzung, die korrekt bleibt

Sami Kharma und Florian Schintke vom Zuse-Institut Berlin bauten Sanko. Sein Kern ist ein einfacher Beweisübertragungssatz (proof-transfer theorem): Ein gespeicherter Beweis, dass ein Spieler gewinnt, bleibt auf einem neuen Weg gültig, es sei denn, eine Stellung, die der Gewinner herstellen muss, ist bereits vorgekommen. Nur die Stellungen des Gewinners zählen – kann der Verlierer eine Stellung nicht mehr wiederherstellen, verliert er nur eine Option. Die Prüfung dauert proportional zur Länge des Wegs, nicht zur Größe des Beweises. Auf dem 3×7-Brett senkt diese Abkürzung allein den Aufwand von 664 Milliarden Schritten auf 112 Millionen.

Sie passten außerdem die klassische Erkennung sicherer Gruppen so an, dass sie unter Superko korrekt bleibt, und beschnitten nur die Züge der Seite, deren Sieg sie zu beweisen versuchten, sodass eine gescheiterte Suche als unbekannt gemeldet wird, nie als Sieg der anderen Seite.

Neue Werte

• 5×5 in 15,7 Minuten auf sechs Threads – etwa 20-mal schneller als zuvor, teils dank besserer Hardware; auf einem einzigen Thread wird 4×4 58-mal schneller gelöst. Auf einer Maschine mit 192 Threads dauert 5×5 etwa anderthalb Minuten.
• Die ersten Superko-Werte von 23 weiteren Brettern; 11 davon waren unter keinen Regeln je gelöst worden. 3×10 ist für Schwarz 8 Punkte wert – MIGOS hatte nur mindestens 6 bewiesen, und zwei Monate Suche hatten keine obere Schranke gefunden.
• Auf einreihigen Brettern wiederholen sich die Werte von 1×9 bis 1×15 als 0, 1, 2, 2 – aber 1×16 bricht das Muster und ist 1 statt 2 wert.

Die 4×7-Überraschung

Nach den alten Regeln ist 4×7 ein Sieg über das ganze Brett: Schwarz schlägt alles, 28–0. Unter Superko ist es 12 wert. Die Autoren spielten die für MIGOS veröffentlichte optimale Variante mit 31 Zügen nach: Jeder Zug ist erlaubt, und Schwarz nimmt trotzdem das ganze Brett. Indem sie die Variante rückwärts lösten, fanden sie den Bruch direkt nach Zug 25: In der Stellung nach Zug 25, gespielt von Schwarz, sollte Weiß G2 (oder C1) statt A2 spielen.

Was folgt, ist ein seltsames Ko. Weiß schlägt; das Zurückschlagen von Schwarz würde eine frühere Stellung wiederherstellen – verboten. Jeder andere schwarze Zug bringt die eigene Gruppe in Gefahr. Schwarz muss passen, Weiß passt, und die Partie endet mit lebender weißer Gruppe: was die MIGOS-Autoren bereits „Mondschein-Leben“ (moonshine life) genannt hatten. Nach den alten Regeln würde das Passen das Verbot aufheben, und Schwarz würde zurückschlagen und alles gewinnen. Unter Superko ist das Beste für Schwarz in dieser Variante ein gemeinsames Leben (Seki), das nur 3 Punkte wert ist; perfektes Spiel verlässt die veröffentlichte Variante daher früher – und das Beste, was Schwarz vom leeren Brett aus sichern kann, sind 12.

Keine der beiden Suchen war falsch. Der Unterschied kommt von Regeln, die erst ganz am Ende einer Partie eine Rolle spielen. Der Rat der Autoren: Werte, die unter Konventionen berechnet wurden, die Wiederholungen harmlos machen, sollten nicht ungeprüft als Werte von Superko-Go zitiert werden.

Von jedem überprüfbar

Jeder Wert beruht auf zwei unabhängigen Beweisen, und der Löser bestand Zehntausende Gegenproben ohne eine einzige Abweichung. Anders als bei früheren Lösungen leerer Go-Bretter sind der Quellcode des Lösers und der genaue Befehl hinter jedem Ergebnis öffentlich; die 4×7-Beweiskette lässt sich in weniger als zwanzig Sekunden nachspielen. Die Beweise sind noch keine Zertifikate, die ein Außenstehender unabhängig prüfen kann, und 6×6 bleibt außer Reichweite – nach der Hochrechnung der Autoren etwa 50 Tage auf einer ihrer Maschinen, oder mehr.