AlphaGo

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Logo des Computerprogramms AlphaGo

AlphaGo ist ein Computerprogramm, das das Brettspiel Go spielt und von DeepMind entwickelt wurde und sich auch gegen professionelle Spieler durchsetzen konnte. AlphaGo kombiniert Techniken des maschinellen Lernens und der Traversierung.

Hintergrund

[Bearbeiten | Quelltext 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.[1] 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. Es wurde auch unter den Pseudonymen Master(P) und Magister(P) bekannt.[2] 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.[3]

Architektur

[Bearbeiten | Quelltext 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.[4]

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).[4] Bei den späteren Matches gegen Lee Sedol wurden 1920 CPUs und 280 GPUs verwendet.[5] 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.[6][7]

Berühmte Partien

[Bearbeiten | Quelltext bearbeiten]

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

AlphaGo gegen Fan Hui

[Bearbeiten | Quelltext bearbeiten]

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

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

AlphaGo gegen Lee Sedol

[Bearbeiten | Quelltext bearbeiten]

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 sollte 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

[Bearbeiten | Quelltext bearbeiten]

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

[Bearbeiten | Quelltext bearbeiten]

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

[Bearbeiten | Quelltext bearbeiten]

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]

[Bearbeiten | Quelltext bearbeiten]

Presseberichte

[Bearbeiten | Quelltext bearbeiten]

Programme

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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ Zen computer Go program beats Takemiya Masaki with just 4 stones! In: gogameguru.com. Go Game Guru, archiviert vom Original (nicht mehr online verfügbar) am 1. Februar 2016; abgerufen am 11. März 2016 (amerikanisches Englisch).
  2. ↑ Elizabeth Gibney: Google reveals secret test of AI bot to beat top Go players. In: nature. Springer Nature Limited, 12. Januar 2017, abgerufen am 30. April 2020.
  3. ↑ Google-Software besiegt Go-Genie auch im letzten Match. FAZ, 15. März 2016, abgerufen am 13. September 2017.
  4. ↑ a b c David Silver, Aja Huang u. a.: Mastering the game of Go with deep neural networks and tree search. (Memento vom 28. Januar 2016 im Internet Archive) In: Nature. 529, 2016, S. 484, doi:10.1038/nature16961.
  5. ↑ Showdown. In: The Economist. 12. März 2016, abgerufen am 10. März 2016.
  6. ↑ AlphaGo: using machine learning to master the ancient game of Go. In: Official Google Blog. Abgerufen am 10. März 2016 (amerikanisches Englisch).
  7. ↑ Christof Windeck: Google I/O 2016: "Tensor-Prozessoren" halfen beim Go-Sieg – heise online. In: heise.de. 19. Mai 2016, abgerufen am 23. November 2016.
  8. ↑ AlphaGo: Mastering the ancient game of Go with Machine Learning. In: blogspot.com. Abgerufen am 11. März 2016.
  9. ↑ Go-Duell Mensch vs. Software: Technisches K.o. bei Spiegel Online, 12. März 2016 (abgerufen am 12. März 2016).
  10. ↑ Match 2 – Google DeepMind Challenge Match: Lee Sedol vs AlphaGo auf YouTube
  11. ↑ a b „Er ist eben nur ein Mensch“. In: Tagesschau online, 12. März 2016, abgerufen am 13. März 2016.
  12. ↑ Chen Xieyuan: Lee Sedol Says Not Defeat of Humans after Historic Go Match with AlphaGo. China Radio International, 13. März 2016, archiviert vom Original (nicht mehr online verfügbar) am 13. März 2016; abgerufen am 13. März 2016 (englisch): „Although losing for a third time, the 33-year-old grandmaster still thinks it is „not a defeat for humans“. „AlphaGo shows the part of its weaknesses, so I doubt whether it has skills that can actually deliver a message to humans. Therefore, I think Lee Sedol is the one who lost today, not humanity.““
  13. ↑ dpa/AFP: Google-Software besiegt Go-Weltmeister. In: FAZ.net. 9. März 2016, abgerufen am 9. März 2016.
  14. ↑ bähr/dpa: Go-Genie verliert gegen den Computer. In: FAZ.net. 10. März 2016, abgerufen am 10. März 2016.
  15. ↑ dpa: Go-Weltmeister gegen Computer – Niederlage eingestanden. In: FAZ.net. 12. März 2016, abgerufen am 12. März 2016.
  16. ↑ Google's AlphaGo gets 'divine' Go ranking. In: The Straits Times.com. 15. März 2016. (englisch)
  17. ↑ Harald Bögeholz: Künstliche Intelligenz: AlphaGo besiegt Ke Jie zum dritten Mal – heise online. In: heise.de. 27. Mai 2017, abgerufen am 28. Mai 2017.
  18. ↑ Harald Bögeholz: Künstliche Intelligenz: Fünf Profis sind nicht genug gegen AlphaGo. In: Heise online. 26. Mai 2017.
  19. ↑ Mastering the game of Go without human knowledge. Nature, 19. Oktober 2017, abgerufen am 19. Oktober 2017 (englisch).
  20. ↑ Es gibt nur noch einen Gegner für Googles KI AlphaGo. In: Wired. (wired.de [abgerufen am 11. November 2017]).
  21. ↑ Michael Nielsen: Alpha Go – Computer lernen Intuition. In: Spektrum der Wissenschaft. Nr. 1, Januar 2018, S. 22–27 (spektrum.de). Darin: Kevin Hartnett: Durch eigenständiges Lernen zur Meisterschaft, S. 26–27. Beide Beiträge sind Übersetzungen aus dem Englischen: Is AlphaGo Really Such a Big Deal?, Artificial Intelligence Learns to Learn Entirely on Its Own.
  22. ↑ Künstliche Intelligenz: AlphaZero meistert Schach, Shogi und Go, heise.de vom 7. Dezember 2017
  23. ↑ Schlauer Computer spielt Weltklasse-Schach – nach nur vier Stunden, faz.net vom 8. Dezember 2017
  24. ↑ Nach nur vier Stunden üben: Künstliche Intelligenz schlägt besten Schachcomputer der Welt, spektrum.de vom 6. Dezember 2017
  25. ↑ Künstliche Intelligenz beendet menschliche Dominanz, welt.de vom 13. Dezember 2017
Abgerufen von „https://de.wikipedia.org/w/index.php?title=AlphaGo&oldid=249432323“