Zahlen, bitte! Die (fast) unendliche Tiefe des Go-Spiels
Wie viele legale Stellungen gibt es eigentlich auf einem 19×19-Go-Brett? Die Antwort kennt man schon länger "genau genug", nämlich ungefähr eine 2 mit 170 Nullen dran, aber erst seit Januar 2016 bis auf die letzte Stelle genau.
Es ist wie mit der Suche nach immer größeren Primzahlen oder immer noch mehr Nachkommastellen von Pi: Beides hat wenig praktische Bedeutung, aber trotzdem tun Menschen es. So ist denn auch die Berechnung der Anzahl legaler Stellungen auf einem Go-Brett zu wenig nütze, jedenfalls hilft einem die Kenntnis dieser Zahl überhaupt nicht dabei, das Spiel besser zu spielen. John Tromp und Helfer haben sie trotzdem ausgerechnet – weil sie es konnten.
Und hier ist sie:
L19 = 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
oder etwas kompakter umbrochen
2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935
Go – Komplexes Strategiespiel mit einfachen Regeln
Das Strategiespiel Go zeichnet sich durch einfache Regeln aus, aus denen irrwitzige Komplexität entsteht. Am morgigen Mittwoch wird eine künstliche Intelligenz von Google gegen einen Spitzenspieler antreten, den Koreaner Lee Sedol; wir berichten live ab 5 Uhr morgens. Hintergründe und die Go-Regeln finden Sie im Artikel "Mysteriöse Tiefe – Wie Google-KI den Menschen im Go schlagen will" bei c't online. Um das Spiel soll es hier aber gar nicht gehen, sondern nur um die viel einfacher zu formulierende Frage, wie viele legale Stellungen es auf dem Go-Brett gibt.
Dazu muss man nur wissen, dass jeder Punkt auf dem Brett entweder leer oder von einem schwarzen oder weißen Stein besetzt sein kann. Jede zusammenhängende Kette von Steinen einer Farbe muss mindestens einen angrenzenden freien Punkt besitzen, eine sogenannte Freiheit. Das Go-Brett hat normalerweise 19×19 = 361 Punkte, aber natürlich ist die Fragestellung auch auf jede andere Brettgröße übertragbar.
Mini-Brettchen
Auf dem 2×2-Brett ist die Anzahl der Möglichkeiten noch im Kopf nachvollziehbar. Drei Möglichkeiten (schwarz, weiß, leer) gibt es für jeden Punkt, also höchstens 34 = 81 Kombinationen für das ganze Brettchen. Es darf nicht ganz voll sein, weil jede Kette Freiheiten braucht, damit scheiden die 24 = 16 Möglichkeiten aus, alle Felder mit schwarzen oder weißen Steinen zu besetzen. Zwei oder weniger Steine gehen auf jeden Fall, denn dann hat jeder Stein mindestens eine Freiheit. Von den Kombinationen mit drei Steinen sind diejenigen illegal, die einen Stein einer Farbe in einer Ecke zwischen zwei Steinen der anderen Farbe einpferchen: 4 Ecken mal 2 Möglichkeiten für die Farben ergibt 8 illegale Stellungen mit drei Steinen. Also gibt es 81–16–8 = 57 legale Stellungen auf dem 2×2-Brett – das war ja einfach ;-).
Kombinatorische Explosion
(Bild: John Tromp)
Aber bei größeren Brettern explodiert das Problem. Die 3361 (= 1,7·10172) Möglichkeiten, das 19×19-Brett zu besetzen, der Reihe nach auf Legalität zu testen, ist illusorisch. John Tromp und Gunnar Farnebäck entwickelten in ihrem Aufsatz "Combinatorics of Go" daher eine Methode, die Aufgabe effizienter anzugehen. Die Kernidee dabei ist es, das Brett dafür an einem Punkt durchzusägen und das Teilbrett oberhalb und links vom gewählten Punkt zu betrachten. Für die Frage, ob sich die Stellung auf diesem Teilbrett zu einer legalen Stellung fortsetzen lässt, ist nur eine kleine Menge an Informationen erforderlich, die sich auf die Schnittkante reduzieren lässt, ein "Border State". Eine legale Stellung ergibt sich nun als ein Pfad durch den Graphen der Border States, angefangen vom leeren Brett bis zu einem Zustand ganz rechts ohne freiheitslose Steine. Die Anzahl dieser Pfade durch den Graphen führt der Algorithmus zurück auf die 361. Potenz einer sehr dünn besetzten Matrix mit 363 Milliarden Zeilen und Spalten.
Ein Job für dicke Server
Trotz des raffinierten Algorithmus ist die Berechnung von L19 – Anzahl der legalen Stellungen auf dem 19×19-Brett – kein Pappenstiel. Die Software ist Open Source und Tromp ermutigt andere, sein Ergebnis nachzuvollziehen, und zwar mit anderen Moduli. Die Berechnung erfolgte nämlich mit modularer Arithmetik: Statt einer Berechnung mit riesigen Zahlen führt man dabei mehrere Berechnungen parallel durch, jeweils modulo einer großen Primzahl. Der chinesische Restsatz liefert einem dann daraus am Ende das vollständige Ergebnis. Falls Sie einen dicken Server übrig haben: 15 Terabyte schneller Plattenspeicher, 8 bis 16 Kerne und 192 GByte RAM werden empfohlen; die Laufzeit beträgt dann einige Monate.
Anzahl möglicher Go-Partien
Die ganze Diskussion oben bezieht sich nur auf die Anzahl legaler Stellungen, aber wie sieht es mit der Anzahl möglicher Go-Partien aus? Die ist noch viel, viel größer: Tromp und Farnebäck geben in ihrem Paper an, dass sie für das 19×19-Brett zwischen einer Eins mit 1048 Nullen und einer Eins mit 10170 Nullen liegt.
Selbst auf dem 2×2-Brett mit seinen 57 legalen Stellungen ist die Zahl möglicher Partien – zyklenfreie Wege durch den Stellungsgraphen, die mit dem leeren Brett beginnen – größer, als die meisten Menschen denken würden: Nicht Tausende, nicht Hunderttausende, nein, 386.356.909.593 sind es.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes Video (Kaltura Inc.) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Kaltura Inc.) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Seine schiere Größe ist nur einer der Gründe, warum das Go-Spiel für Computer so schwierig ist. Für Menschen ist es leicht zu lernen, aber gar nicht leicht zu gewinnen – probieren Sie es mal aus! Zum Beispiel mit einer App auf Ihrem Smartphone oder Tablet: Ein paar Tipps liefert der Artikel "Mensch gegen Smartphone: Apps für das Strategiespiel Go". (bo)
