Warum spielen Computer so gut Schach, aber so schlecht Go?#
Ernst Buchberger
Zwei Brettspiele haben durch Jahrtausende hindurch die klügsten Köpfe der Menschheit angezogen: Schach und Go, Letzteres vor allem in Japan, China und Korea. Während aber gute Schachprogramme mittlerweile Meisterniveau und mehr erreichen, werden die besten Go-Programme noch immer bereits von mäßigen Klubspielern geschlagen. Warum?
Das von Spielcomputern angewendete Verfahren ist im Prinzip einfach: Man betrachtet für jeden Zug alle möglichen Folgezüge und so weiter, bis ein Endzustand, also Gewinn oder Niederlage, erreicht ist. Die graphische Notation dieser Analyse wird als Spielbaum bezeichnet. Dabei bilden die möglichen Züge die Äste des Baumes, der sich immer weiter verzweigt. Durch Rückverfolgung, ausgehend vom Endzustand, kann der jeweils optimale Zug herausgefunden werden – es ist der, der bei jedem möglichen Zug des Gegners wieder zu einer Gewinnsituation führt.
Für nicht-triviale Spiele ist aber dieser Spielbaum zu groß. Bei einem Spiel, bei dem in jedem Moment 10 Züge möglich sind und das im Schnitt 30 (Halb-)Züge dauert, bräuchte selbst ein superschneller Computer, der eine Milliarde Züge in einer Sekunde berechnen könnte, für die Berechnung des Spielbaumes mehr als 10 hoch 21 Sekunden, also mehr als eine Billion Jahre. Man beschneidet daher den Spielbaum („pruning“) derart, dass schlecht erscheinende Züge nicht weiter verfolgt werden. Ein Zug gilt dabei als schlecht, wenn er zu einer für den Spieler als ungünstig erachteten Spielsituation führt, beim Schachspiel also z. B. Figurenverlust ohne entsprechende Kompensation wie drohendes Matt etc. Diese Einschätzung wird von einer Bewertungsfunktion durchgeführt.
Beim Schach gibt es in einer typischen Stellung 36 mögliche Züge zur Auswahl, im Go sind es im Durchschnitt 250 Züge. Selbst wenn man Symmetrien berücksichtigt, ist daher der Spielbaum weit größer als beim Schachspiel, nicht nur die Zugmöglichkeiten, sondern auch die Zuganzahl betreffend (viele Schachpartien sind schon nach 40 oder 50 Zügen beendet, Go-Spiele dauern oft 200 und mehr Züge).
Vor allem ist es aber im Go-Spiel wesentlich schwieriger, gute Bewertungsfunktionen zu finden, da sich lokale Veränderungen oft in weit entfernten Teilen des Brettes auswirken und es keine exakte Theorie dazu gibt. Das Schachspiel ist offensichtlich für den Computer geeigneter, da er im Wesentlichen mit intensiver Suche, gestützt durch einfache Bewertungen, erfolgreich ist – fehlendes Verständnis wird durch Rechenleistung kompensiert.
Beim Go-Spiel, das mehr auf der Erkennung von Mustern basiert, führt ausgedehnte Suche allein nicht zum Erfolg. Ist Go daher das intelligentere Spiel? Zumindest sind wir noch nicht in der Lage, die Überlegungen menschlicher Go-Spieler auf dem Computer erfolgreich zu simulieren, und anders ist das Spiel im Gegensatz zu Schach auch für den Computer nicht zu gewinnen.
Dieser Essay stammt mit freundlicher Genehmigung des Verlags aus dem Buch:
Verlagsgruppe Styria GmbH & Co KG, Wien