Künstliche Intelligenz schlägt Profi im Go
Die Go-Welt ist wie vom Blitz getroffen: Ein Computer hat einen Profi geschlagen, und zwar in einem ernsthaften Match auf dem großen Brett, ohne Handicap, fünfmal hintereinander. Dazu muss man wissen, dass das asiatische Strategiespiel unter Anfängern und Computern auch auf kleineren Brettern (weniger als die üblichen 19 × 19 Linien) und mit Handicap (der schwächere Spieler bekommt bis zu neun Steine Vorsprung) gespielt wird und sich bisher kein professioneller Go-Spieler auch nur herabgelassen hätte, mit weniger als vier Steinen Handicap ernsthaft gegen ein Computerprogramm zu spielen.
Doch dann kam das Google-Start-up DeepMind. Deren künstliche Intelligenz AlphaGo hat still und heimlich alle anderen Computer-Go-Programme deklassiert und im Oktober 2015 in einem Fünf-Partien-Match hinter verschlossenen Türen Fan Hui (2p) besiegt, einen in China ausgebildeten Profi-Go-Spieler, der jetzt in Europa lebt und dreifacher Europameister ist.
Wie AlphaGo funktioniert, haben die Wissenschaftler am 28. Januar im renommierten Wissenschaftsmagazin Nature veröffentlicht (siehe c’t-Link unten). Kaum auszumalen, wie schwer es dem DeepMind-Team gefallen sein muss, so lange dichtzuhalten, denn erst im November hatte Facebook mit einem Go spielenden neuronalen Netz von sich reden gemacht. Es war als mysteriöser Spieler darkforest auf dem Go-Server KGS aufgetaucht und spielte dort aus dem Stand auf Amateur-Dan-Niveau – durchaus noch schlechter als die stärksten bisherigen Go-Programme, aber auf einem erkennbar guten Weg.
Auch bei AlphaGo sind es neuronale Netze, die den Durchbruch gebracht haben, und zwar gleich mehrere davon. Ähnlich wie Facebook begann DeepMind zunächst damit, ein neuronales Netz auf die Vorhersage guter Züge zu trainieren, und zwar auf der Grundlage von 30 Millionen Stellungen von KGS. Dieses sogenannte Policy Network soll dabei helfen, Raum für die Suche nach einem guten Zug einzugrenzen, denn ohne solche Vorkehrungen wäre der Suchbaum von Go unbeherrschbar groß: Im Mittel 200 Möglichkeiten gibt es für jeden Zug und eine Partie hat über 200 Züge – das sind ausmultipliziert ungefähr unendlich viele Möglichkeiten.
Diese erste, durch „supervised learning“ entstandene Version des Policy Network ließ das DeepMind-Team dann gegen sich selbst spielen und daraus durch sogenanntes Reinforcement Learning weiter lernen, um es aufs Gewinnen zu optimieren.
Auch eine zweite wichtige Komponente von AlphaGo ist ein neuronales Netz, das sogenannte Value Network. Hier geht es darum, den Wert einer Stellung zu ermitteln, also die Frage zu beantworten, mit welcher Wahrscheinlichkeit ein Spieler aus dieser Stellung heraus gewinnen kann. Als bisher bestes Verfahren für eine solche Bewertung galt MCTS, Monte-Carlo Tree Search, bei dem man eine Stellung sehr oft mit zufälligen Zügen bis zu Ende spielt und schaut, wer häufiger gewinnt.
Das Value Network trainierten die Forscher nun, indem sie das Policy Network gegen sich selbst spielen ließen. Sie gewannen so eine Bewertungsfunktion mit gleicher Güte wie sie Monte-Carlo-Simulationen erreichten, aber mit um den Faktor 15 000 geringerem Rechenaufwand.
AlphaGo kombiniert nun zwei neuronale Netze mit einem MCTS-Verfahren. Die Monte-Carlo-Suche orientiert sich bei der Zugwahl an den vom Policy Network vorgegebenen Wahrscheinlichkeiten für gute Züge. Für die Bewertung von Stellungen kommt das Value Network zum Einsatz.
Das resultierende AlphaGo war in den Tests der Forscher erheblich stärker als die bisher stärksten Go-Programme: Noch mit vier Handicap-Steinen gewann es 77 Prozent der Partien gegen den Champion Crazy Stone. Es wurde also Zeit für den finalen Test, ein Match gegen einen menschlichen Profi. Die verteilte Version von AlphaGo nutzte dafür die geballte Rechenpower von 1202 CPUs und 176 GPUs – und putzte Fan Hui 5:0 weg.
Deswegen greift Google jetzt nach den Sternen und hat den weltstärksten Go-Spieler herausgefordert, den Koreaner Lee Sedol. Er hat angenommen und wird im März gegen AlphaGo spielen – um eine Million US-Dollar, damit sich nachher keiner rausreden kann, das Ganze wäre nur ein Spaß. (bo@ct.de)
Hintergrund, Videos: ct.de/yz7c