Читать книгу Deep Learning illustriert - Jon Krohn - Страница 61

Das vor einigen Tausend Jahren in China erfundene Go (dargestellt in Abbildung 4–5) ist ein einzigartiges Strategiespiel für zwei Personen. Das Spiel hat einfache Regeln, die sich darum drehen, die Spielsteine des Gegners einzufangen, indem man sie mit seinen eigenen Steinen einkreist.¹³ Diese unkomplizierte Grundannahme täuscht jedoch darüber hinweg, dass das Spiel in der Praxis ausgesprochen raffiniert ist. Durch das größere Spielbrett und die größere Anzahl möglicher Bewegungen pro Zug ist das Spiel viel komplexer als etwa Schach, für das es bereits seit zwei Jahrzehnten Algorithmen gibt, die die besten menschlichen Spieler besiegen können.¹⁴ Es gibt etwas mehr als 2 × 10¹⁷⁰ mögliche zulässige Brettpositionen in Go, was deutlich mehr ist als die Anzahl der Atome im Universum¹⁵ und ungefähr ein Googol (10¹⁰⁰) komplexer als Schach.

Abb. 4–5Das Brettspiel Go. Ein Spieler benutzt die weißen Steine, während der andere mit den schwarzen Steinen spielt. Ziel ist es, die gegnerischen Steine einzukreisen und sie damit zu fangen.

Abb. 4–6Die normalisierten Leistungsmaße des DQN von Mnih und seinen Kollegen (2015) im Vergleich zu einem professionellen Spieletester: 0% bedeutet zufälliges Spielen, 100% ist die beste Leistung des Profispielers. Die horizontale Linie repräsentiert die durch die Autoren definierte Schwelle für das Spielen auf »menschlichem Niveau«: das 75. Perzentil der Ergebnisse des Profis.

Man kann einen Algorithmus namens Monte Carlo Tree Search (MCTS) verwenden, um kompetent unkomplizierte Spiele zu spielen. In seiner reinsten Form werden beim MCTS bis zum Ende des Spiels zufällige Züge ausgewählt.¹⁶ Indem dies viele Male wiederholt wird, können Züge, die zu siegreichen Spielergebnissen führen, als bevorzugte Optionen eingestuft (gewichtet) werden. Aufgrund der außergewöhnlichen Komplexität und schieren Anzahl an Möglichkeiten in raffinierten Spielen wie Go erweist sich der reine MCTS-Ansatz als nicht besonders praktikabel: Es müssten einfach zu viele Möglichkeiten durchsucht und ausgewertet werden. Statt des reinen MCTS wendet ein alternatives Vorgehen MCTS auf eine eher begrenzte Teilmenge an Aktionen an, die zum Beispiel durch ein etabliertes Regelwerk für optimales Spielen kuratiert wurden. Dieser kuratierte Ansatz reicht aus, um Go-Amateure zu besiegen, kommt aber nicht gegen Profispieler an. Um die Lücke zwischen dem Amateur- und dem Profiniveau zu überbrücken, entwickelten David Silver (Abbildung 4–7) und seine Kollegen bei Google DeepMind ein Programm namens AlphaGo, das MCTS mit überwachtem Lernen und Deep Reinforcement Learning kombiniert.¹⁷

Silver et al. nutzten überwachtes Lernen auf einer historischen Datenbank mit von menschlichen Experten ausgeführten Go-Zügen, um ein sogenanntes Policy Network (Regelnetzwerk) aufzustellen, das eine Auswahlliste mit möglichen Zügen für eine bestimmte Situation anbietet. Dieses Regelnetzwerk wurde anschließend durch Deep Reinforcement Learning verfeinert, wobei das System gegen sich selbst spielte. Das heißt, beide Gegner sind Go spielende Agenten mit vergleichbarem Können. Durch dieses Gegen-sich-selbst-Spielen verbessert sich der Agent schrittweise und wird nach einer Verbesserung immer wieder gegen sein verbessertes Selbst ins Rennen geschickt, sodass eine positive Feedback-Schleife der ständigen Verbesserung entsteht. Das Sahnehäubchen auf dem AlphaGo-Algorithmus ist schließlich das sogenannte Value Network (Bewertungsnetzwerk), das den Gewinner der gegen sich selbst gespielten Spiele vorhersagt. Dabei bewertet es Spielpositionen und lernt, starke Spielzüge zu identifizieren. Die Kombination aus Regel- und Bewertungsnetzwerk (mehr dazu folgt in Kapitel 13) reduziert die Breite des Suchraums für das MCTS.

Abb. 4–7David Silver ist ein in Cambridge und Alberta ausgebildeter Forscher bei Google DeepMind. Er war wesentlich an der Kombination der Deep-Learning- und Reinforcement-Learning-Paradigmen beteiligt.

AlphaGo war in der Lage, die große Mehrheit der Spiele zu gewinnen, die es gegen andere computerbasierte Go-Programme spielte. Was aber vielleicht noch faszinierender war: AlphaGo besiegte auch Fan Hui, den damals amtierenden Go-Europameister mit 5:0. Dies war das erste Mal, dass ein Computer gegen einen menschlichen Profispieler in einer kompletten Partie dieses Spiels gewann. Wie die Elo-Bewertungen¹⁸ in Abbildung 4–8 zeigen, operierte AlphaGo auf dem Niveau der besten Spieler der Welt oder sogar darüber.

Nach diesem Erfolg trat AlphaGo im März 2016 im südkoreanischen Seoul gegen Lee Sedol an. Sedol besitzt 18 internationale Titel und gilt als einer der besten Go-Spieler aller Zeiten. Das aus fünf Spielen bestehende Match wurde live übertragen und von 200 Millionen Menschen angeschaut. AlphaGo gewann das Match mit 4:1 und brachte damit DeepMind, Go und die Zukunft der künstlichen Intelligenz in das Bewusstsein der Öffentlichkeit.¹⁹