Direkt zum Inhalt

KI-Meilenstein: Das Go-Spiel ist geknackt

Das Brettspiel Go galt als letzte Bastion menschlicher Überlegenheit. Doch nun feiert ein Google-Team den Durchbruch: "AlphaGo" ließ erstmals einen Top-Spieler schlecht aussehen.
Das Spiel Go

Am Ende ging es dann doch viel schneller als gedacht. "In zehn Jahren", antworteten Experten bislang, wenn man fragte, wann ein Computer in der Lage sein würde, menschliche Spitzenspieler im Go zu bezwingen. Das aus Ostasien stammende Brettspiel ist berüchtigt wegen seiner Komplexität – seit Langem gilt es darum als wichtiges Etappenziel bei der Weiterentwicklung der künstlichen Intelligenz (KI). Und nun ist es passiert: Ein Team des Google-Forschungslabors "DeepMind" in London berichtet, dass ihr System den amtierenden Europameister Fan Hui mit 5 zu 0 Spielen – man möchte hinzufügen: vernichtend – geschlagen hat.

Anders als Schach, bei dem heute selbst Großmeister keine Chance gegen die Computer haben, widersetzte sich Go bislang der künstlichen Intelligenz und galt darum als eine der letzten Bastionen menschlicher Überlegenheit im Spiel. Was den KI-Forschern vor allem fehlte, war ein raffinierter Lösungsansatz – und den fand das Team um Demis Hassabis nun in der Technik des so genannten Deep Learning. Ein Verfahren, das derzeit ein KI-Problem nach dem anderen knackt.

"AlphaGo", wie Hassabis und Kollegen ihre Software tauften, habe wie ein Mensch gespielt, lobt Toby Manning von der Britischen Go-Vereinigung, der die Partie gegen Hui beaufsichtigte: "Man konnte während des Spiels nicht sagen, wer wer ist." KI-Forscher Jonathan erwartet, dass der Erfolg in Forscherkreisen für Begeisterung sorgen wird: "Einen solchen Sprung nach vorne hat niemand erwartet", erklärt er im "New Scientist".

Beim Go setzen Spieler nacheinander Steine ihrer Farbe (Schwarz oder Weiß) auf ein 19 mal 19 Felder großes Brett. Dabei gilt es, gegnerische Steine zu umzingeln und dadurch für sich zu erobern. Es gewinnt, wer mehr als die Hälfte des Bretts kontrolliert. Bei derartigen Spielen, in denen der Zufall keine Rolle spielt, bietet es sich an, den Computer alle möglichen künftigen Züge im Voraus berechnen zu lassen – und zwar bis zum Ende der Partie. Das Ergebnis ähnelt einem Baum, der sich pro Zug um die Anzahl aller jeweils gültigen Folgezüge verästelt.

Warum Schach so schwer ist – und Go noch schwerer

Lässt sich ein solcher Baum aufstellen, muss der Computer einfach nur solche Züge auswählen, die zu einem Gewinn der Partie führen. Leider ist es beim Schach nicht und erst recht nicht bei Go möglich, sämtliche Verästelungen dieses Suchbaums zu verfolgen. Ihre Anzahl übersteigt rasch die Grenzen jedweder Handhabbarkeit. Doch das Ganze lässt sich auch viel einfacher lösen, sofern man nur diejenigen Pfade betrachtet, die besonders lohnend sind, und diese zweitens nur so lange Zug um Zug in die Zukunft verfolgt, bis man sicher genug weiß, ob sich die Partie in eine günstige Richtung entwickelt. Unnötige und aussichtslose Pfade sortiert man einfach aus. Die Schwierigkeit dabei ist nur: Woher weiß man, dass man Halt machen sollte? Und wie findet man überhaupt die lohnenden Züge?

Ein Spiel um Dominanz | AlphaGo habe sehr zurückhaltend gespielt, sagen Experten, die die Partie beobachteten. Ziel ist es, mehr als die Hälfte des Bretts mit seinen Steinen zu kontrollieren. Die Zahl möglicher Partien lässt sich auf 10 hoch 171 abschätzen – was die Anzahl der Atome im Universum übertrifft.

Das Schachspiel liefert hier dank unterschiedlich gewichteter Figuren und einem kleineren Spielfeld mehr Anhaltspunkte, was es dann letztendlich im Jahr 1997 einem IBM-Team erlaubte, mit ihrem Programm "Deep Blue" den Schachgroßmeister Garri Kasparow zu besiegen. Go hingegen macht es einer KI besonders schwer. Zwischen den Steinen gibt es keine formalen Unterschiede, und ob es nützlich war, einen davon auf ein bestimmtes Feld zu platzieren, stellt sich oftmals erst viel später in der Partie heraus. Der "Wert" einer gegebenen Stellung lässt sich darum nur schwer ermitteln.

Und genau hier kommt das Deep Learning zum Zuge. Das Verfahren baut auf so genannten künstlichen neuronalen Netzen auf, die sich beispielsweise darauf trainieren lassen, unterschiedliche Fotos ein und derselben Person zuzuordnen oder handschriftliche Kritzeleien einem Buchstaben des Alphabets. Diese Fähigkeit der Mustererkennung machte sich das Team um Hassabis zu Nutze. Die Forscher verwendeten zwei separate Deep-Learning-Netze: eines, um in jeder Stellung die besonders lohnenden Züge herauszufiltern, und ein anderes, um den Wert einer Stellung zu bestimmen.

Zig Millionen Übungspartien

So gewappnet können sie den Suchbaum auf ein vertretbares Maß zurückstutzen: AlphaGo evaluierte sogar 1000-mal weniger Spielpositionen als seinerzeit DeepBlue im Match gegen Kasparow.

Beide Netze mussten jedoch zunächst lernen, ihrer Aufgabe nachzukommen. Das "Spielpolitik"-Netz (policy network), das nach den jeweils lohnenden Zügen sucht, trainierten sie anhand von 30 Millionen Spielzügen aus einer Datenbank von Partien fortgeschrittener Spieler. Ihr System lernte dabei vorherzusagen, welche Spielzüge angesichts einer gegebenen Stellung am wahrscheinlichsten durchgeführt werden. Mit Hilfe dieses Netzes entwickelten sie anschließend eine rudimentäre Go-KI, die sie in leicht unterschiedlichen Versionen gegen sich selbst antreten ließen. Das Netz verfeinerte dadurch seine Vorhersagen über die Wahrscheinlichkeit von Zügen, indem es berücksichtigte, ob seine Vorhersagen zum Spielgewinn führten oder nicht. Bei diesem "reinforcement learning" genannten Lernverfahren werden Entscheidungen nachträglich belohnt, wenn sie sich als günstig herausstellen. Das "Werte"-Netzwerk (value network) trainierten sie ebenfalls anhand von 30 Millionen Partien darauf, für eine gegebene Stellung vorherzusagen, ob eher Weiß oder Schwarz gewinnt.

Die Kombination macht den Unterschied

Doch Hassabis und Kollegen waren nun immer noch nicht am Ziel. Der letzte und vermutlich entscheidende Schritt bestand darin, diese beiden neuen Werkzeuge mit einer Methode zu kombinieren, die bereits zum Knacken von Spielen wie Backgammon oder Scrabble beigetragen hat: die so genannte Monte-Carlo-Baumsuche. Bei diesem Verfahren erfolgt der Blick in die Zukunft einer Partie durch Simulation. Statt komplett alle denkbaren Zugkombinationen zu evaluieren, simuliert das Verfahren wahrscheinliche Verläufe. Die Informationen aus dem "Spielpolitik"-Netz half den Google-Forschern diese Simulationen exakter zu gestalten; die Ergebnisse der Monte-Carlo-Suche verrechnete das Team dann fortlaufend mit den Vorhersagen des "Werte"-Netzes, um einen möglichst idealen Zug herauszupicken. Die Auswertung konnten die Entwickler parallelisieren, so dass sie auf mehr als 1000 Prozessoren verteilt werden konnte. Diese zusätzliche Rechenpower verbesserte noch einmal die spielerischen Fähigkeiten AlphaGos.

© Nature Video
Hassabis und Kollege David Silver erklären ihr Progamm (englisch)
Erstautor der Studie David Silver, ebenfalls von Google, und sein Chef Hassabis erzählen, wie es dazu kam, dass sie sich Go als Ziel heraussuchten.

Besonders viel versprechend an diesem System ist die Tatsache, dass keines seiner Bestandteile spezifisch für Go ist. Während Schachcomputer explizit darauf programmiert werden, bestimmte Schwachstellen des Spiels auszunutzen, deutet vieles darauf hin, dass sich die Architektur von AlphaGo auch für Aufgaben in anderen Bereichen heranziehen lässt. Überall dort, wo man es mit komplexen Entscheidungen zu tun habe, deren Lösung man nicht durch stupides Suchen finden könne, erklärt Hassabis. Als Beispiel nennt er die Analyse medizinischer Daten zur Krankheitsdiagnose oder Auswahl von Medikamenten und die Verbesserung von Klimamodellen.

Auch Facebook scheint auf einen solchen Zusatznutzen der Go-KI zu hoffen, denn seine Forschungsabteilung tüftelt ebenfalls an einem eigenen System. Medienberichten zufolge spielen sie damit allerdings noch in der Nachwuchsklasse.

Und natürlich ließen Hassabis und Kollegen ihre Software auch gegen andere KIs antreten. Die Ergebnisse waren eindeutig. Selbst wenn sie dem Gegner einen Vorsprung gewährten, kassierten diese Niederlage um Niederlage. Im Endergebnis verzeichneten sie ein 494 zu 1. Die auf mehrere Computer verteilte Variante erwies sich gar als gänzlich unschlagbar. Jetzt gilt es, sich neue Herausforderungen zu setzen. Im März 2016 ist das maßgebliche Event geplant, bei dem AlphaGo beweisen muss, ob es bereits übermenschliche Fähigkeiten besitzt. Dann nämlich geht es gegen den aktuell weltbesten Spieler, den Südkoreaner Lee Sedol. Das Preisgeld für die Partie beläuft sich auf eine Million Dollar, die Google im Falle eines Gewinns spenden will.

Ist AlphaGo schon bereit für einen Meister des Go? "Ich würde mein Geld noch auf Lee Sedol setzen", sagt Toby Manning, "aber lieber nur einen ganz kleinen Betrag."

Schreiben Sie uns!

3 Beiträge anzeigen

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.