AlphaGo ist ein Computerprogramm, das das Brettspiel Go spielt und von DeepMind entwickelt wurde. Es ist auch unter den Pseudonymen Master(P) und Magister(P) bekannt^[1]. AlphaGo kombiniert Techniken des maschinellen Lernens und der Traversierung.

Im Januar 2016 wurde bekannt, dass AlphaGo bereits im Oktober 2015 den mehrfachen Europameister Fan Hui (2. Dan) besiegt hatte. Damit ist es das erste Programm, das unter Turnierbedingungen ohne Vorgabe (Handicap) auf einem 19×19-Brett einen professionellen Go-Spieler schlagen konnte.^[2] Im März 2016 schlug AlphaGo den Südkoreaner Lee Sedol, der als einer der weltbesten Profispieler angesehen wird (AlphaGo gegen Lee Sedol).^[3]

Hintergrund

Nachdem das IBM-Programm Deep Blue im Mai 1997 den damaligen Schachweltmeister Garri Kasparow in einem Wettkampf unter Turnierbedingungen mit 3,5:2,5 Punkten geschlagen hatte, galt Go als nächste große Herausforderung für die Entwickler von Systemen künstlicher Intelligenz. Wegen der größeren Komplexität von Go gegenüber Schach, die sich aus dem größeren Brett (19×19) und der ungleich größeren Anzahl möglicher Züge ergibt, ist Go mit traditionellen Brute-Force-Algorithmen (Alpha-Beta-Suche), d. h. durch Durchprobieren aller möglichen Züge, praktisch nicht bezwingbar. Ein weiteres Problem bestand darin, dass es – im Gegensatz zu Schach – für Go keine zweckmäßigen heuristischen Methoden gab, um eine gegebene Spielstellung zu bewerten.

Existierende Go-Programme hatten Ende der 1990er Jahre eine Spielstärke, die kaum über die von ambitionierten menschlichen Anfängern hinausging.

Mit der Anwendung von sogenannten Monte-Carlo-Algorithmen einer Baumsuche gelang ab 2006 ein Durchbruch, der dazu führte, dass Programme wie Crazy Stone oder Zen die Stärke von sehr guten Amateuren erreichten. Auf einem kleinen Brett (9×9) oder mit vier Steinen Vorgabe auf dem Standardbrett konnten auch Erfolge gegen Profispieler erzielt werden.^[4] Monte-Carlo-Programme benutzen statistische Methoden, um Zugkandidaten zu finden. Der Zug wird bewertet, indem von der Spielbrettposition ausgehend mit Zufallszügen bis zum Ende gespielt wird.

AlphaGo markiert einen erheblichen Entwicklungssprung gegenüber früheren Programmen. In 500 Spielen gegen andere Programme, darunter Crazy Stone und Zen, gewann AlphaGo alle bis auf eines. Im Oktober 2015 kam es zu einem Vergleichskampf mit dem amtierenden Europameister und professionellen Go-Spieler Fan Hui, der den 2. Profi-Dan innehat. AlphaGo entschied die Partien mit 5:0 für sich.^[5]

Architektur

AlphaGo verwendet zusätzlich zu Monte-Carlo-Methoden Lernmethoden für tiefe neuronale Netzwerke. Dabei werden zwei Kategorien von neuronalen Netzen und eine Baumsuche eingesetzt:

• Das policy network („Regelnetzwerk“) wird zur Bestimmung von Zugkandidaten mit großen Mengen von Partien sowohl durch überwachtes Lernen (engl. supervised learning) konditioniert als auch durch bestärkendes Lernen (engl. reinforcement learning) trainiert
• Das value network („Bewertungsnetzwerk“) dient der Bewertung von Positionen und wird durch bestärkendes Lernen eingestellt.
• Die Monte-Carlo-Baumsuche rechnet die Varianten durch. Alle drei Komponenten werden in dieser Baumsuche kombiniert.^[6]

Der Ansatz unterscheidet sich schon insofern von aktuellen Programmen, als er zumindest grundsätzlich auch auf andere Anwendungsgebiete übertragbar ist. Zunächst lernt das Programm durch Analyse einer Datenbank von 30 Millionen Zügen, den Zug eines Menschen „vorherzusagen“. Das gelingt zu 56 %. Bei der Bewertung des Zuges ist es im Gegensatz zu Monte-Carlo-Programmen nicht notwendig, die Partie bis zum Ende durchzuspielen. Mit diesem Ansatz allein gelingt es AlphaGo schon, traditionelle Programme zu besiegen. In der Praxis werden allerdings für die stärkste Version von AlphaGo zusätzlich auch noch Bewertungen nach dem Monte-Carlo-Verfahren vorgenommen.

Bei den Partien gegen Fan Hui lief die verteilte Variante von AlphaGo auf einem Rechnerverbund mit insgesamt 1202 CPUs und 178 GPUs und nutzte 40 Such-Threads (search threads).^[6] Bei den späteren Matches gegen Lee Sedol wurden 1920 CPUs und 280 GPUs verwendet.^[7] Um die während der Lernphase benötigte massive Rechenleistung bereitzustellen, wurden die Google Cloud Platform und TensorFlow Processing Units (ASICs für die Software-Sammlung TensorFlow) eingesetzt.^[8][9]

Berühmte Partien

AlphaGo gegen Fan Hui

AlphaGo (schwarz) vs. Fan Hui (weiß). Das 4. Spiel vom 8. Oktober 2015, AlphaGo gewann durch Aufgabe von Weiß.^[6]

Die ersten 99 Züge (Zug 96 auf Zug 10)

Züge 100–165

AlphaGo gegen Lee Sedol

Ab dem 9. März 2016 trat AlphaGo gegen den südkoreanischen Profi Lee Sedol, 9. Dan, an. Lee gilt als einer der derzeit besten Spieler der Welt. Gespielt wurde nach Chinesischer Wertung mit einem Komi von 7,5. AlphaGo gewann das über fünf Partien ausgetragene Match mit 4:1. Lee konnte lediglich die vierte Partie (mit Weiß) gewinnen, so dass AlphaGo bereits nach dem dritten Sieg in der dritten Partie als Gewinner feststand. Alle fünf Partien endeten durch Aufgabe.^[10] Damit ist AlphaGo das erste Computer-Programm, das einen professionellen Spieler dieser Spielstärke – sogar mehrfach – ohne Handicap bezwingen konnte. Lee hatte im Februar vor dem Event erklärt, er werde „haushoch“ gewinnen.^[11] Nach der dritten verlorenen Partie erklärte er, er sei geschockt vom Spiel des Computers und dass er sich nach den ersten beiden verlorenen Spielen stark unter Druck gesetzt fühlte. Er erklärte, es sei eine persönliche Niederlage, aber keine für die Menschheit.^[11][12]

Das Turnier wurde im südkoreanischen Seoul ausgetragen und fand international große mediale Beachtung. Unter anderem wurden die Partien live über YouTube gestreamt und von dem amerikanischen 9.-Dan-Spieler Michael Redmond in englischer Sprache kommentiert. Der Gewinner erhielt eine Million Dollar.^[13][14] AlphaGos Siegprämie soll wohltätigen Zwecken zugeführt werden.^[15] Nach dem Ende des Wettkampfs verlieh der südkoreanische Go-Verband Hanguk Kiwon AlphaGo den höchsten Rang 9p eines 9. professionellen Dan.^[16]

AlphaGo gegen Ke Jie

AlphaGo gegen Ke Jie war ein Go-Match auf dem Wuzhen Future of Go Summit 2017 vom 23.–27. Mai 2017 in Wuzhen, China. Der Weltranglistenerste Ke Jie musste sich dabei dreimal AlphaGo geschlagen geben.^[17] Im gleichen Zeitraum trat AlphaGo gegen ein Team von fünf Top-Spielern zusammen an, die jeden ihrer Züge gemeinsam planen konnten. AlphaGo gewann auch dieses Match.^[18]

AlphaGo Zero

Im Oktober 2017 publizierten die Entwickler von AlphaGo die Ergebnisse der jüngsten Entwicklungsstufe von AlphaGo. Das AlphaGo Zero genannte Programm wurde mit veränderter Software- und reduzierter Hardware-Architektur mit keinerlei Vorwissen über das Spiel, sondern ausschließlich mit den Spielregeln ausgestattet und durch Spiele gegen sich selbst trainiert. Als Hardware wurden beim Inferencing lediglich vier Tensor Processing Units eingesetzt. AlphaGo Zero wurde ebenfalls mit Hilfe von TensorFlow entwickelt. Es war schon nach 3 Tagen stärker als die AlphaGo-Version, die Lee Sedol besiegen konnte, und besiegte diese 100:0. Nach 40 Tagen Training schlug es auch die jüngste und vormals stärkste Ausbaustufe des Programms, AlphaGo Master.^[19][20][21]

AlphaZero

Im Dezember 2017 stellte die Google-Firma DeepMind die KI AlphaZero vor. Diese erlernte innerhalb weniger Stunden nacheinander die Spiele Schach, Go und Shogi und war dann besser als jede Software, die bislang entwickelt wurde und damit weit übermenschlich. AlphaZero wird nur trainiert durch das Einprogrammieren der Spielregeln. Daraufhin trainiert AlphaZero gegen sich selbst einige Stunden. Menschliche Spielstrategien werden der KI nicht gezeigt. Die KI entwickelt alle Spielstrategien eigenständig. Die Schach-Website chess24 kommentierte dies mit: die Zeit der ausgefeilten Schachprogramme sei wohl vorüber.^[22][23][24] Der ehemalige Schachweltmeister Garri Kasparow meinte, er sei erstaunt darüber „was man von AlphaZero und grundsätzlich von KI-Programmen lernen kann, die Regeln und Wege erkennen können, die Menschen bisher verborgen geblieben sind.“ und „Die Auswirkungen sind offenbar wunderbar und weit jenseits von Schach und anderen Spielen. Die Fähigkeit einer Maschine menschliches Wissen aus Jahrhunderten in einem komplexen, geschlossenen System zu kopieren und zu überflügeln, ist ein Werkzeug, das die Welt verändern wird.“^[25]

Weblinks

• AlphaGo – DeepMind. In: deepmind.com. 28. Januar 2016, abgerufen am 12. November 2018.

Presseberichte

• Tobias Berben: Master(P) alias AlphaGo spielt 60:0 – Go-Baduk-Weiqi.de. In: go-baduk-weiqi.de. 4. Januar 2017, abgerufen am 8. Januar 2017.
• Harald Bögeholz: Wie Google-KI den Menschen im Go schlagen will – c’t Magazin. In: heise.de. 26. Februar 2016, abgerufen am 8. März 2016.
• Jo Bager: Googles KI AlphaGo gewinnt und gewinnt – heise online. In: heise.de. 5. Januar 2017, abgerufen am 5. Januar 2017.
• Oliver Fritsch: AlphaGo: „Ich kann nicht mehr erkennen, wer Mensch und wer Maschine ist“. In: zeit.de. 9. März 2016, abgerufen am 9. März 2016.

Programme

• Minigo auf GitHub – An open-source implementation of the AlphaGoZero algorithm
• AlphaGo Teach. In: alphagoteach.deepmind.com. Abgerufen am 12. November 2018. – AlphaGo-Datenbank