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. 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. Im März 2016 schlug AlphaGo den Südkoreaner Lee Sedol, der als einer der weltbesten Profispieler angesehen wird (AlphaGo gegen Lee Sedol).
Hintergrund Bearbeiten
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. 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.
Architektur Bearbeiten
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.
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). Bei den späteren Matches gegen Lee Sedol wurden 1920 CPUs und 280 GPUs verwendet. Um die während der Lernphase benötigte massive Rechenleistung bereitzustellen, wurden die Google Cloud Platform und Tensor Processing Units (ASICs für die Software-Sammlung TensorFlow) eingesetzt.
Berühmte Partien Bearbeiten
AlphaGo gegen Fan Hui Bearbeiten
AlphaGo (schwarz) vs. Fan Hui (weiß). Das 4. Spiel vom 8. Oktober 2015, AlphaGo gewann durch Aufgabe von Weiß.
| | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Die ersten 99 Züge (Zug 96 auf Zug 10) |
| | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Züge 100–165 |