Google-KI schlägt menschlichen Profi-Spieler im Go
Das asiatische Brettspiel Go galt als die letzte Bastion des Menschen: Trotz großer Fortschritte waren Computer menschlichen Spitzenspielern ein gutes Stück unterlegen. Jetzt ist es passiert: Ein Programm schlägt erstmals einen Go-Profi ohne Handicap.
(Bild: Google DeepMind)
"Game over" schreibt Rémi Coulom, der Entwickler eines der bisher stärksten Go-Programme, auf der Mailingliste computer-go: Eine künstliche Intelligenz von Google namens AlphaGo hat Fan Hui geschlagen, den Profi-Spieler (2p) und dreifachen europäischen Go-Meister. Die Go-Szene reibt sich zuerst die Augen und ist dann vom Donner gerührt: Ohne Handicap? Ja, gleichauf, und nicht nur einmal, sondern in fünf Spielen hintereinander, die bereits im Oktober 2015 stattfanden. Und nicht nur das: Der als weltstärkster Spieler geltende Koreaner Lee Sedol hat die Herausforderung angenommen, im März in Seoul gegen AlphaGo zu spielen.
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.
Wie das gelungen ist, veröffentlichen David Silver und Aja Huang in der am 28. 1. erscheinenden Ausgabe 529 von Nature: Mastering the game of Go with deep neural networks and tree search. Es ist, wie schon der Titel sagt, eine Kombination von neuronalen Netzen und Baumsuche.
Unendliche Bäume
Baumsuche allein ist bei Go ein aussichtsloses Unterfangen: Der Spielbaum ist viel zu breit und viel zu tief. Bei jedem Zug gibt es im Mittel vielleicht 200 Möglichkeiten und eine Partie dauert mindestens 200 Züge, da kommen ganz andere Zahlen zusammen als etwa bei Schach, dessen Spielbaum sich mit jedem (Halb-)Zug "nur" ungefähr 20-fach verzweigt. (Allein die Anzahl legaler Positionen auf dem Go-Brett, ungefähr 2,08 × 10170, hat vor ein paar Tagen übrigens John Tromp (mit Helfern) bis auf die letzte Ziffer ausgerechnet.)
Einen großen Durchbruch erlebte das Computer-Go mit der Erfindung des Monte-Carlo Tree Search (MCTS). Vereinfacht ausgedrückt spielt der Computer dabei aus einer Stellung heraus möglichst viele Partien mit Zufallszügen zu Ende – die Farbe, die häufiger gewinnt, hatte wohl die bessere Stellung. Das ermöglichte überhaupt erst, den Wert einer Stellung halbwegs zu bewerten und damit eine sinnvolle Baumsuche. MCTS-Programme haben in den letzten Jahren in Kombination mit klassischen Techniken (Eröffnungsbibliotheken, Musterdatenbanken etc.) die Spielstärke starker menschlicher Amateure erreicht – aber eben noch lange nicht die von hauptberuflichen Profi-Spielern. Einzelne Showkämpfe zwischen Profis und Supercomputern wurden mit vier Steinen Handicap ausgetragen und ein Sieg mit einem solch großen Handicap galt für die Computer als Achtungserfolg.
Tja, Facebook ...
Einige Beachtung in der Computer-Go-Szene fand dann die KI-Abteilung von Facebook, die es geschafft hatte, allein mit einem neuronalen Netz aus dem Stand in die Region menschlicher Amateur-Dan-Spieler vorzustoßen – und kurz darauf durch das Hinzufügen von MCTS noch ein bisschen besser zu werden. Gerade noch (er hat die Google-Veröffentlichung wohl kommen sehen) freute sich Marc Zuckerberg auf Facebook über die neusten Go-Fortschritte seiner KI-Abteilung, veröffentlicht in "Better Computer Go Player with Neural Network and Long-term Prediction ". Deren neuronales Netz spielt auf dem Go-Server KGS unter dem Usernamen darkfores2 als 3-Dan, in Kombination mit MCTS angeblich als 5-Dan. Das ist die Spielstärkeregion der bisher stärksten Programme ohne neuronale Netze – aber eben deutlich unter Profi-Niveau.
Die Kraft der zwei Netze
Die von Google übernommene Firma DeepMind hat nun AlphaGo als Kombination aus zwei neuronalen Netzen geschaffen. Das "policy network" macht Vorschläge für sinnvolle nächste Züge und hilft so, den Spielbaum schmal zu halten: Statt hunderter möglicher Züge braucht man nur noch eine Handvoll vermutlich guter Züge zu betrachten. Das "value network" ist darauf spezialisiert, die Gewinnaussichten einer Stellung zu bewerten; das Ganze kombinieren die Macher dann noch mit MCTS.
Das Policy Network wurde zunächst mit 30 Millionen Zügen von menschlichen Experten trainiert. Dann spielte es gegen sich selbst und lernte daraus weiter (reinforcement learning). Das Ganze führte dann – ebenfalls per reinforcement learning – zu einer immer weiteren Verbesserung der Value Networks zur Stellungsbewertung.
Das vollständige Paper von Silver, Huang et al. steht auch kostenlos zum Download bereit. (bo)
