AlphaGo

Was AlphaGo ist und warum Go schwierig ist

AlphaGo ist ein von DeepMind entwickeltes Computerprogramm für das Brettspiel Go. Es konnte auch professionelle Spieler besiegen. Dafür verbindet es maschinelles Lernen mit der Traversierung, also dem systematischen Durchsuchen, von Spielvarianten.

Go galt nach dem Sieg von IBMs Deep Blue gegen Garri Kasparow im Mai 1997 als nächste große Herausforderung der künstlichen Intelligenz. Auf dem 19×19-Brett gibt es sehr viel mehr mögliche Züge als im Schach. Deshalb ist die reine Brute-Force-Suche mit Alpha-Beta-Suche, bei der mögliche Züge umfassend ausprobiert werden, praktisch nicht ausreichend. Außerdem gab es für Go lange keine zweckmäßigen heuristischen Methoden: Das sind vereinfachte Regeln, mit denen eine Stellung bewertet werden kann.

Ende der 1990er Jahre waren Go-Programme kaum stärker als ambitionierte menschliche Anfänger. Ab 2006 verbesserten Monte-Carlo-Algorithmen die Programme deutlich. Sie bewerten Zugkandidaten statistisch, indem sie von einer Stellung aus mit Zufallszügen bis zum Spielende weiterspielen. Programme wie Crazy Stone und Zen erreichten dadurch das Niveau sehr guter Amateure; auf 9×9-Brettern oder mit vier Steinen Vorgabe gelangen auch Siege gegen Profis. AlphaGo gewann von 500 Spielen gegen andere Programme, darunter Crazy Stone und Zen, alle bis auf eines.

Lernnetze und Baumsuche

AlphaGo kombiniert drei Bausteine in einer Monte-Carlo-Baumsuche:

• Das policy network („Regelnetzwerk“) wählt aussichtsreiche Zugkandidaten. Es wird zunächst mit vielen Partien durch überwachtes Lernen und anschließend durch bestärkendes Lernen trainiert.
• Das value network („Bewertungsnetzwerk“) schätzt, wie gut eine Spielposition ist. Es wird durch bestärkendes Lernen eingestellt.
• Die Monte-Carlo-Baumsuche berechnet mögliche Varianten und verbindet dabei die Ergebnisse beider Netze.

Zuerst analysierte AlphaGo eine Datenbank von 30 Millionen Zügen und lernte, menschliche Züge vorherzusagen. Dies gelang zu 56 %. Anders als bei reinen Monte-Carlo-Programmen muss AlphaGo zur Positionsbewertung nicht jede Partie vollständig bis zum Ende simulieren. Bereits dieser Lernansatz konnte traditionelle Programme besiegen; für die stärkste Version wurden zusätzlich Monte-Carlo-Bewertungen genutzt.

Der Ansatz ist grundsätzlich auch auf andere Anwendungsgebiete übertragbar. Beim Match gegen Fan Hui nutzte die verteilte Version einen Rechnerverbund mit 1202 CPUs, 178 GPUs und 40 Such-Threads. Gegen Lee Sedol wurden 1920 CPUs und 280 GPUs eingesetzt. Für das Training standen Google Cloud Platform und Tensor Processing Units zur Verfügung, also ASICs für die Software-Sammlung TensorFlow.

Siege gegen professionelle Go-Spieler

Im Oktober 2015 besiegte AlphaGo den mehrfachen Europameister Fan Hui, 2. Profi-Dan, mit 5:0. Es war damit das erste Programm, das unter Turnierbedingungen ohne Vorgabe auf einem 19×19-Brett einen professionellen Go-Spieler schlagen konnte. Im vierten Spiel am 8. Oktober 2015 spielte AlphaGo Schwarz und gewann, weil Fan Hui mit Weiß aufgab.

Ab dem 9. März 2016 spielte AlphaGo in Seoul gegen den südkoreanischen Profi Lee Sedol, 9. Dan, der zu den besten Spielern der Welt gerechnet wurde. Gespielt wurde nach chinesischer Wertung mit einem Komi von 7,5. AlphaGo gewann das Match über fünf Partien mit 4:1; Lee Sedol gewann nur die vierte Partie mit Weiß. Da AlphaGo die ersten drei Partien gewann, stand es bereits nach der dritten Partie als Matchgewinner fest. Alle fünf Partien endeten durch Aufgabe. AlphaGo war damit das erste Computerprogramm, das einen professionellen Spieler dieser Spielstärke mehrfach und ohne Handicap schlug. Der südkoreanische Go-Verband Hanguk Kiwon verlieh AlphaGo danach den höchsten Rang 9p eines 9. professionellen Dan.

Match gegen Ke Jie

Beim Wuzhen Future of Go Summit 2017 in Wuzhen, China, spielte AlphaGo vom 23.–27. Mai 2017 gegen den Weltranglistenersten Ke Jie. Ke Jie verlor alle drei Partien gegen AlphaGo. Im selben Zeitraum spielte AlphaGo außerdem gegen ein Team aus fünf Top-Spielern, die jeden Zug gemeinsam planen durften. Auch dieses Match gewann AlphaGo.

AlphaGo Zero und AlphaZero

AlphaGo Zero wurde im Oktober 2017 als jüngste Entwicklungsstufe vorgestellt. Es erhielt keinerlei Vorwissen über Go, sondern nur die Spielregeln und trainierte ausschließlich durch Partien gegen sich selbst. Seine Software- und Hardware-Architektur waren verändert und reduziert; beim Inferencing genügten vier Tensor Processing Units. AlphaGo Zero wurde ebenfalls mit TensorFlow entwickelt.

Schon nach 3 Tagen war AlphaGo Zero stärker als die Version, die Lee Sedol besiegt hatte, und gewann gegen sie 100:0. Nach 40 Tagen Training schlug es auch AlphaGo Master, die zuvor stärkste Ausbaustufe.

Im Dezember 2017 stellte DeepMind AlphaZero vor. Diese KI lernte nacheinander Schach, Go und Shogi innerhalb weniger Stunden und war danach besser als jede zuvor entwickelte Software. Auch AlphaZero wird nur mit den Spielregeln programmiert und trainiert dann einige Stunden gegen sich selbst. Menschliche Spielstrategien werden ihr nicht gezeigt; die KI entwickelt ihre Strategien eigenständig.