Das traditionsreiche Brettspiel Go hat in Japan ungefähr dieselbe Bedeutung wie Schach in Orient und Abendland: als strategisches, vom Zufall nicht beeinflußtes Denkspiel und unerschöpfliche intellektuelle Herausforderung. Im Gegensatz zu Schach hat Go allerdings eine Variante für Kinder mit den gleichen Steinen und dem gleichen Brett. Der besondere Reiz dieses Go-Moku (auch unter den Namen Gobang und Five-in-a-Row bekannt) ist die äußerste Einfachheit seiner Regeln.

Zwei Spieler, Schwarz und Weiß, setzen abwechselnd einen Stein der eigenen Farbe auf eine der Kreuzungen eines Brettes von 15 mal 15 Linien. Schwarz beginnt. Einmal gesetzte Steine werden im Laufe des Spiels weder verschoben noch entfernt. Der erste Spieler, dem es gelingt, eine geschlossene Reihe von fünf Steinen (waagerecht, senkrecht oder diagonal) seiner Farbe zu bilden, gewinnt (a links im Bild auf Seite 26). In der heutigen Version gilt die Zusatzregel, daß eine Reihe von sechs oder mehr Steinen einer Farbe ungültig ist. Die Aufgabe ist also der Aufbau einer Reihe von genau fünf Steinen.

Schwarz hat beim Go-Moku einen so großen Vorteil, daß sich in Japan die Auffassung durchgesetzt hat, ein (erwachsener) Schwarz-Spieler könne stets den Sieg erzwingen. Dies hatte sich aber bisher nicht erhärten lassen, weder durch einen mathematischen Beweis noch durch eine erschöpfende Aufzählung aller denkbaren Spielverläufe. Erst mit Hilfe eines Computerprogramms ist uns das gelungen.

Drohungsketten

Fast jede Go-Moku-Partie läuft darauf hinaus, daß ein Spieler eine Reihe von Drohungen erzeugt, deren jede eine Gegenmaßnahme des Gegners erzwingt (b bis e links im Bild auf Seite 26). Stellt schließlich ein Spieler gleichzeitig zwei Drohungen auf, die nicht beide zugleich abzuwehren sind, hat er mit dem nächsten Zug gewonnen. Rechts im Bild auf Seite 26 ist ein Beispiel eines solchen Spielverlaufs gezeigt.

Starke Go-Moku-Spieler vermögen bis zu 20 Züge lange Drohungsketten, bei denen der Zug des Gegners jeweils durch eine Drohung erzwungen wird, zu entdecken. In jeder Position erforschen sie dabei nur wenige Alternativen und verhindern auf diese Weise, daß die Zahl der zu beurteilenden Stellungen sie überfordert.

Auch die meisten Computerprogramme arbeiten hauptsächlich mit dem Auffinden von Drohungsketten. Oft findet ein Programm sehr schnell eine Gewinnvariante mit einer sehr langen Zugfolge, muß dagegen in anderen Fällen die Suche nach Minuten abbrechen, ohne daß ersichtlich würde, ob es eine Gewinnstrategie gibt. Das liegt daran, daß derartige Programme in jeder Stellung im Prinzip alle möglichen Drohungszüge untersuchen – einschließlich solcher, die ein menschlicher Experte sofort als Sackgassen erkennt und nicht weiterverfolgt. Der Entscheidungsbaum, der einer Suche zugrunde liegt, wird dann extrem buschig (vergleiche "Eine Maschine als Schach-Großmeister" von Feng-Hsiung Hsu, Thomas Anantharaman, Murray Campbell und Andreas Nowatzyk, Spektrum der Wissenschaft, Dezember 1990, Seite 94). In einigermaßen verwickelten Stellungen kann die Anzahl der zu prüfenden Züge auf viele Millionen anwachsen.

Unser Programm "Victoria" verwendet für das Auffinden von Drohungsketten ein neues Verfahren, das wir Drohungsraumsuche (threat space search) nennen. Während die üblichen Algorithmen in jeder Position alle Zugmöglichkeiten durchsuchen, beschränkt sich unserer – nach dem Vorbild des menschlichen Experten – zunächst auf Bedrohungszüge, in denen der bei der letzten Drohung gesetzte Stein wieder Verwendung findet, in zweiter Linie auf solche, die zwei bisher unabhängige Drohungsketten zu einer neuen Drohung kombinieren. Mit diesem Algorithmus kann "Victoria" in durchschnittlich 0,2 Sekunden feststellen, ob in einer Position eine gewinnträchtige Konfiguration dieser Art besteht. Allerdings kann es vorkommen, daß in einzelnen Positionen eine bestehende Drohungskette nicht gefunden wird; diesen Mangel behebt eine ergänzende Suchtechnik.

Die Lösung

In der Spieltheorie gilt eine gegebene Stellung als gelöst, falls erstens für eine Farbe (Schwarz oder Weiß) feststeht, ob sie gewinnt, verliert oder Remis erzielt, und zweitens dieses Ergebnis auch beim besten Gegenspiel erzielbar ist. Unser Hilfsmittel bei der Lösung von Go-Moku ist eine Bewertungsfunktion, mit der das Programm für eine vorgegebene Position sehr schnell eine Teilantwort auf die Frage ermittelt, ob eine Drohungskette existiert: Entweder erklärt diese Funktion die betreffende Stellung für gewinnend, dann haben wir Sicherheit, oder die Situation ist noch offen.

Ansatz bei unserer Lösung von Go-Moku ist die Stellung, bei der Schwarz seinen ersten Stein genau in die Brettmitte setzt. Weiß hat dann die Auswahl unter 224 Gegenzügen, die sich aber wegen der Symmetrie des Brettes auf 35 wesentlich verschiedene zurückführen lassen. (Die absolute Größe des Brettes ist nicht von entscheidender Bedeutung, da es keinen Vorteil bringt, weitab vom bisherigen Geschehen eine neue Front zu eröffnen.) Für jede der sich ergebenden 35 Positionen und für jede spätere Position, in der Schwarz am Zug ist, muß unser Programm nun einen Zug angeben. Dazu wird die jeweilige Stellung von der Bewertungsfunktion untersucht. Falls diese nicht unmittelbar eine schlüssige Antwort in Form einer Drohungskette liefert, wird das Spiel für die zehn reizvollsten Gegenzüge von Schwarz weiterverfolgt.

Für unseren Zweck genügt es, daß nur einer dieser zehn Züge (zum Teil von Menschenhand ausgewählt) den Gewinn sicherstellt. Dies kann man mit einem gleichfalls neuen Suchverfahren namens Beweiszahlsuche ( proof number search ) nachweisen – allerdings mit einem gewissen Zeitaufwand.

Um diesen in Grenzen zu halten, macht man sich bei der Beweiszahlsuche die Tatsache zunutze, daß die Anzahl der sinnvollen Züge bei Go-Moku von Position zu Position stark variiert. Indem der Algorithmus bevorzugt die Äste des Entscheidungsbaums absucht, bei denen der Gegner sehr wenige Züge zur Auswahl hat, muß er möglicherweise nur relativ wenige Alternativen durchspielen, bis er eine Gewinnstrategie gefunden hat.

Folgerichtig ist Go-Moku damit als drittes nichttriviales Spiel mit Hilfe des Computers gelöst. Seine Vorgänger waren Connect-Four ("Vier gewinnt": Die Steine sind durchlöchert, werden auf Stangen gesteckt und fallen bis zur tiefsten noch unbesetzten Position; daraus sind horizontale, vertikale oder diagonale Vierer zu bilden) und Qubic (hier ist das Spielfeld ein dreidimensionales Gitter aus 4x4x4 Kreuzungspunkten, die unabhängig voneinander besetzt werden können; wieder sind Vierer zu bilden).

DerAufwand und seine Früchte

Insgesamt hat "Victoria" etwa 15 Millionen Stellungen durchstöbert, ehe der Beweis erbracht war, daß Schwarz tatsächIich aus der Anfangsposition heraus immer gewinnen kann. Dieser Beweis ist konstruktiv, da im Programm eine vollständige Gewinnstrategie abgespeichert ist. Dazu genügt es, wenn für jede Position, in der Schwarz zieht, die Anweisung für den nächsten Zug abgelegt ist; für Weiß am Zuge müssen dagegen alle erlaubten Züge dokumentiert werden. Es ergibt sich ein Suchbaum von ungefähr 150|||000 Zügen. Jedes Blatt in diesem Baum liefert Schwarz eine gewinnsichere Drohungskette.

Die Rechenarbeit spielte sich ab auf einem Netzverbund von elf Su-Sparc-Workstations an der Vrije Universiteit Amsterdam. Der gesamte Rechenaufwand belief sich auf etwa drei Millionen Rechnersekunden; das wären auf einer einzelnen Maschine ungefähr 35 Tage. Da sich mehrere Rechner die Arbeit teilten, konnte mit der letzten Version von "Victoria" der endgültige Beweis innerhalb einer Woche erbracht werden.

Die längste Variante, die "Victoria" in diesem Baum fand, umfaßt 35 Züge, denen noch eine Drohungsreihe von etlichen Zügen bis zum endgültigen Sieg folgt. Da "Victoria" die Suche abbricht, sobald eine Gewinnstrategie gefunden ist, können wir nicht ausschließen, daß es aus der entsprechenden Position noch kürzere Wege zum Sieg gibt.

"Victoria" im Turnier

Die Turnierversion des Programms besteht im wesentlichen aus einer Tabelle von 150|||000 Zügen und einer Bewertungsfunktion nebst einer Schnittstelle für die graphische Darstellung. Spielt "Victoria" Schwarz, sucht sie in jeder Situation einen dazu passenden Zug in der Tabelle, was nur ungefähr 0,2 Sekunden auf einem einzelnen Rechner dauert. Ist die Suche erfolglos, steht fest, daß eine gewinnende Drohungskette bestehen muß; diese läßt sich innerhalb einer Sekunde finden. "Victoria" kann also mit Schwarz jeden Zug innerhalb von 2 Sekunden spielen und stets gewinnen.

Hat "Victoria" die weiße Farbe, nutzt sie die viel längere normal verfügbare Bedenkzeit, um einen möglichst verwirrenden Zug hervorzubringen. Macht der schwarze Gegner einen Fehler, so hat das Programm Gewinnchancen, obwohl es einem optimal spielenden Gegner selbstverständlich unterliegen würde.

Bei der vierten Computer-Olympiade in London im August 1992 belegte "Victoria" einen ungeteilten ersten Platz. Dabei gewann sie als Schwarz-Spielerin immer; hatte sie dagegen die weißen Steine, war sie immerhin noch in der Hälfte aller Fälle siegreich und überragte damit alle Mitbewerber.

Derartige Bemühungen um ein Kinderspiel sind allerdings weder ein Kinderspiel, noch erschöpft sich ihr Nutzen in dem sportlichen Erfolg: Das übergeordnete Ziel ist, menschliche Denkweisen so weitgehend zu verstehen und zu formalisieren, daß man damit Expertensysteme programmieren kann.

Insbesondere geht es um die Frage, wie ein menschlicher Experte Denkzeit einspart, indem er viele irrelevante Ereignisketten unberücksichtigt läßt. Nach diesem Kriterium war im Falle von Go-Moku das Prinzip eines unbekümmerten Optimismus erstaunlich erfolgreich: Man suche zunächst einen gangbaren Weg zum Sieg und mache sich erst in einem zweiten Schritt Gedanken darüber, ob und wie der Gegner die eigenen Pläne stören kann.

Loek Schoenmakers aus Amsterdam entwarf und programmierte die graphische Schnittstelle unseres Programms; Israef Samuel Herschberg aus Delft gab uns wertvolle Hinweise zu früheren Fassungen dieses Artikels.


Aus: Spektrum der Wissenschaft 4 / 1993, Seite 25
© Spektrum der Wissenschaft Verlagsgesellschaft mbH