Einfach erklärt: Wie ein KI-Programm das alte Go-Spiel beherrschte

Bildnachweis

Hier geht es um AlphaGo, Google DeepMinds Go Playing AI, das 2016 die Technologiewelt erschütterte, indem es einen der besten Spieler der Welt, Lee Sedol, besiegte.

Go ist ein uraltes Brettspiel, das bei jedem Schritt so viele mögliche Züge hat, dass zukünftige Positionen schwer vorherzusagen sind - und daher eine starke Intuition und abstraktes Denken erfordert, um zu spielen. Aus diesem Grund glaubte man, dass nur Menschen gut Go spielen könnten. Die meisten Forscher dachten, dass es noch Jahrzehnte dauern würde, eine KI zu bauen, die so denken könnte. Tatsächlich veröffentliche ich diesen Aufsatz heute, weil diese Woche (8. bis 15. März) das zweijährige Jubiläum des Spiels AlphaGo gegen Sedol markiert!

Aber AlphaGo hörte hier nicht auf. 8 Monate später spielte es 60 professionelle Spiele auf einer Go-Website unter dem Deckmantel eines „Meisters“ und gewann jedes einzelne Spiel gegen Dutzende von Weltmeistern, natürlich ohne sich zwischen den Spielen auszuruhen.

Natürlich war dies eine RIESIGE Leistung auf dem Gebiet der KI und löste weltweite Diskussionen darüber aus, ob wir über künstliche Intelligenz aufgeregt oder besorgt sein sollten.

Heute werden wir das von DeepMind im Nature Journal veröffentlichte Original-Forschungspapier nehmen und es mit einfachem Englisch Absatz für Absatz aufschlüsseln.

Nach diesem Aufsatz wissen Sie sehr genau, was AlphaGo ist und wie es funktioniert. Ich hoffe auch, dass Sie nach dem Lesen nicht allen Schlagzeilen von Journalisten glauben, die Sie über KI erschrecken, und sich stattdessen darüber aufregen.

Sie müssen nicht wissen, wie man spielt. Gehen Sie, um dieses Papier zu verstehen. Tatsächlich habe ich selbst nur die ersten drei bis vier Zeilen im ersten Absatz von Wikipedia darüber gelesen. Stattdessen verwende ich überraschenderweise einige Beispiele aus dem Grundschach, um die Algorithmen zu erklären. Sie müssen nur wissen, was ein 2-Spieler-Brettspiel ist, bei dem sich jeder Spieler abwechselt und am Ende ein Gewinner steht. Darüber hinaus müssen Sie keine Physik oder fortgeschrittene Mathematik oder irgendetwas wissen.

Dies macht es für Menschen zugänglicher, die gerade erst angefangen haben, etwas über maschinelles Lernen oder neuronale Netze zu lernen. Und besonders für diejenigen, die nicht Englisch als Muttersprache verwenden (was das Lesen solcher Artikel sehr erschweren kann).

Wenn Sie KEINE Vorkenntnisse in KI und neuronalen Netzen haben, können Sie hier den Abschnitt „Deep Learning“ eines meiner vorherigen Aufsätze lesen. Nachdem Sie das gelesen haben, können Sie diesen Aufsatz durcharbeiten.

Wenn Sie auch ein flaches Verständnis von Reinforcement Learning erhalten möchten (optionales Lesen), finden Sie es hier.

Hier ist das Originalpapier, wenn Sie es lesen möchten:

Was mich betrifft: Hallo, ich bin Aman, ein KI- und autonomer Roboteringenieur. Ich hoffe, dass meine Arbeit Ihnen viel Zeit und Mühe erspart, wenn Sie dies selbst studieren.

Sprichst du Japanisch? Ryohji Ikebe hat freundlicherweise ein kurzes Memo über diesen Aufsatz auf Japanisch in einer Reihe von Tweets geschrieben.

Lass uns anfangen!

Abstrakt

Wie Sie wissen, war das Ziel dieser Forschung, ein KI-Programm zu trainieren, um Go auf dem Niveau von professionellen menschlichen Spielern von Weltklasse zu spielen.

Um diese Herausforderung zu verstehen, lassen Sie mich zunächst über etwas Ähnliches sprechen, das für Schach getan wurde. In den frühen neunziger Jahren brachte IBM den Deep Blue-Computer heraus, der den großen Champion Garry Kasparov im Schach besiegte. (Er ist auch ein sehr cooler Typ, lesen Sie später mehr über ihn!) Wie hat Deep Blue gespielt?

Nun, es wurde eine sehr Brute-Force-Methode angewendet. Bei jedem Schritt des Spiels wurden alle möglichen legalen Züge untersucht, die gespielt werden konnten, und jeder einzelne Zug wurde untersucht, um zu sehen, was passieren würde. Und es würde eine Weile lang Bewegung nach Bewegung erforschen und eine Art RIESIGEN Entscheidungsbaum aus Tausenden von Zügen bilden. Und dann würde es entlang dieses Baumes zurückkommen und beobachten, welche Bewegungen am wahrscheinlichsten ein gutes Ergebnis bringen würden. Aber was verstehen wir unter „gutem Ergebnis“? Nun, Deep Blue hatte viele sorgfältig entworfene Schachstrategien von erfahrenen Schachspielern eingebaut, um bessere Entscheidungen zu treffen - zum Beispiel, wie man entscheidet, ob man den König beschützt oder woanders Vorteile erzielt? Zu diesem Zweck haben sie einen speziellen „Bewertungsalgorithmus“ entwickelt, um zu vergleichen, wie vorteilhaft oder nachteilig verschiedene Boardpositionen sind (IBM-hartcodierte Expertenschachstrategien in dieser Bewertungsfunktion). Und schließlich wählt es einen sorgfältig kalkulierten Zug. In der nächsten Runde geht es im Grunde das Ganze noch einmal durch.

Wie Sie sehen können, bedeutet dies, dass Deep Blue vor jedem Zug über Millionen theoretischer Positionen nachgedacht hat. Dies war nicht so beeindruckend in Bezug auf die KI-Software von Deep Blue, sondern in Bezug auf die Hardware - IBM behauptete, es sei einer der leistungsstärksten Computer auf dem Markt zu dieser Zeit. Es könnte sich um 200 Millionen Board-Positionen pro Sekunde handeln.

Jetzt kommen wir zu gehen. Glauben Sie mir einfach, dass dieses Spiel viel offener ist, und wenn Sie die Deep Blue-Strategie auf Go ausprobieren würden, könnten Sie nicht gut spielen. Es würde SO VIELE Positionen geben, die bei jedem Schritt zu betrachten wären, dass es für einen Computer einfach unpraktisch wäre, durch diese Hölle zu gehen. Zum Beispiel gibt es beim Eröffnungszug im Schach 20 mögliche Züge. In Go hat der erste Spieler 361 mögliche Züge, und diese Auswahlmöglichkeiten bleiben während des gesamten Spiels groß.

Das ist es, was sie unter "enormem Suchraum" verstehen. Darüber hinaus ist es in Go nicht so einfach zu beurteilen, wie vorteilhaft oder nachteilig eine bestimmte Brettposition an einem bestimmten Punkt im Spiel ist - Sie müssen das ganze Spiel eine Weile spielen, bevor Sie feststellen können, wer gewinnt. Aber nehmen wir an, Sie hatten auf magische Weise die Möglichkeit, beides zu tun. Und hier kommt tiefes Lernen ins Spiel!

In dieser Untersuchung verwendete DeepMind neuronale Netze, um diese beiden Aufgaben zu erledigen (wenn Sie noch nie etwas über neuronale Netze gelesen haben, finden Sie hier den Link erneut). Sie trainierten ein „Policy Neural Network“, um zu entscheiden, welche Bewegungen in einer bestimmten Board-Position am sinnvollsten sind (es ist also so, als würde man einer intuitiven Strategie folgen, um Bewegungen aus einer beliebigen Position auszuwählen). Und sie trainierten ein „Value Neural Network“, um abzuschätzen, wie vorteilhaft eine bestimmte Brettanordnung für den Spieler ist (oder mit anderen Worten, wie wahrscheinlich es ist, dass Sie das Spiel von dieser Position aus gewinnen). Sie trainierten diese neuronalen Netze zuerst mit menschlichen Spielbeispielen (Ihrem guten alten gewöhnlichen überwachten Lernen). Danach konnte die KI das menschliche Spielen bis zu einem gewissen Grad nachahmen, so dass sie sich wie ein schwacher menschlicher Spieler verhielt. Und um die Netzwerke noch weiter zu trainieren, haben sie die KI millionenfach gegen sich selbst spielen lassen (dies ist der Teil „Verstärkungslernen“). Damit wurde die KI besser, weil sie mehr Übung hatte.

Allein mit diesen beiden Netzwerken konnte DeepMinds KI gut gegen hochmoderne Go-Spielprogramme spielen, die andere Forscher zuvor entwickelt hatten. Diese anderen Programme hatten einen bereits populären, bereits existierenden Spielalgorithmus verwendet, der als "Monte Carlo Tree Search" (MCTS) bezeichnet wurde. Dazu später mehr.

Aber raten Sie mal, wir haben immer noch nicht über das eigentliche Geschäft gesprochen. Bei DeepMinds KI geht es nicht nur um Richtlinien- und Wertschöpfungsnetzwerke. Diese beiden Netzwerke werden nicht als Ersatz für die Monte-Carlo-Baumsuche verwendet. Stattdessen werden die neuronalen Netze verwendet, damit der MCTS-Algorithmus besser funktioniert… und er wurde so viel besser, dass er übermenschliche Ebenen erreichte. Diese verbesserte Variante von MCTS ist „AlphaGo“, die KI, die Lee Sedol besiegte und als einer der größten Durchbrüche aller Zeiten in die KI-Geschichte einging. AlphaGo ist also im Wesentlichen einfach eine verbesserte Implementierung eines sehr gewöhnlichen Informatik-Algorithmus. Verstehst du jetzt, warum KI in ihrer jetzigen Form absolut nichts ist, vor dem man Angst haben muss?

Wow, wir haben viel Zeit alleine mit dem Abstract verbracht.

Okay - um das Papier von diesem Punkt an zu verstehen, werden wir zuerst über eine Spielstrategie sprechen, die als Monte-Carlo-Baumsuchalgorithmus bezeichnet wird. Im Moment werde ich diesen Algorithmus nur ausführlich genug erklären, um diesen Aufsatz zu verstehen. Aber wenn Sie mehr darüber erfahren möchten, haben einige kluge Köpfe auch hervorragende Videos und Blog-Beiträge dazu verfasst:

1. Eine kurze Videoserie von Udacity 2. Jeff Bradberrys Erklärung von MCTS 3. Ein MCTS-Tutorial der Fullstack Academy

Der folgende Abschnitt ist lang, aber leicht zu verstehen (ich werde mein Bestes geben) und SEHR wichtig, also bleib bei mir! Der Rest des Aufsatzes wird viel schneller gehen.

Lassen Sie uns über den ersten Absatz des obigen Aufsatzes sprechen. Erinnerst du dich, was ich über Deep Blue gesagt habe, das bei jedem Schritt des Spiels einen riesigen Baum aus Millionen von Brettpositionen und Bewegungen erstellt hat? Sie mussten Simulationen durchführen und jede mögliche Bewegung betrachten und vergleichen. Wie ich bereits sagte, war dies ein einfacher und sehr unkomplizierter Ansatz. Wenn ein durchschnittlicher Softwareentwickler ein Spiel mit KI entwerfen müsste und über die stärksten Computer der Welt verfügen würde, würde er oder sie wahrscheinlich eine ähnliche Lösung entwerfen.

Aber lassen Sie uns darüber nachdenken, wie Menschen selbst Schach spielen. Angenommen, Sie befinden sich mitten im Spiel an einer bestimmten Brettposition. Nach den Spielregeln kannst du ein Dutzend verschiedene Dinge tun - diesen Bauern hierher bewegen, die Königin zwei Felder hierher oder drei Felder dorthin bewegen und so weiter. Aber machen Sie wirklich eine Liste aller möglichen Züge, die Sie mit all Ihren Stücken machen können, und wählen Sie dann einen Zug aus dieser langen Liste aus? Nein - Sie beschränken sich „intuitiv“ auf einige wichtige Züge (sagen wir, Sie haben drei sinnvolle Züge), die Sie für sinnvoll halten, und fragen sich dann, was im Spiel passieren wird, wenn Sie einen dieser drei Züge wählen. Sie können 15 bis 20 Sekunden damit verbringen, jeden dieser drei Züge und ihre Zukunft zu betrachten - und beachten Sie, dass Sie während dieser 15 Sekunden die Zukunft jedes Zuges nicht sorgfältig planen müssen. Sie können einfach ein paar mentale Bewegungen „ausrollen“, die von Ihrer Intuition geleitet werden, ohne zu viel darüber nachzudenken (ein guter Spieler würde weiter und tiefer denken als ein durchschnittlicher Spieler). Dies liegt daran, dass Sie nur eine begrenzte Zeit haben und nicht genau vorhersagen können, was Ihr Gegner bei jedem Schritt in dieser schönen Zukunft tun wird, die Sie in Ihrem Gehirn kochen. Sie müssen sich also nur von Ihrem Bauchgefühl leiten lassen. Ich werde diesen Teil des Denkprozesses als „Rollout“ bezeichnen, nehmen Sie es also zur Kenntnis! Nachdem Sie Ihre wenigen vernünftigen Züge „ausgerollt“ haben, sagen Sie schließlich, schrauben Sie es und spielen Sie einfach den Zug, den Sie am besten finden.

Dann macht der Gegner einen Zug. Es könnte ein Schritt sein, den Sie bereits gut erwartet hatten, was bedeutet, dass Sie jetzt ziemlich sicher sind, was Sie als nächstes tun müssen. Sie müssen nicht zu viel Zeit für die Rollouts aufwenden. ODER es könnte sein, dass dein Gegner dich mit einem ziemlich coolen Zug schlägt, den du nicht erwartet hast, also musst du bei deinem nächsten Zug noch vorsichtiger sein. So geht das Spiel weiter und je näher es dem Endpunkt kommt, desto einfacher wird es für Sie, das Ergebnis Ihrer Züge vorherzusagen - daher dauern Ihre Rollouts nicht so lange.

Der Zweck dieser langen Geschichte ist es, zu beschreiben, was der MCTS-Algorithmus auf oberflächlicher Ebene tut - er ahmt den obigen Denkprozess nach, indem er jedes Mal einen „Suchbaum“ aus Bewegungen und Positionen erstellt. Weitere Informationen finden Sie unter den zuvor erwähnten Links. Die Neuerung dabei ist, dass anstatt alle möglichen Bewegungen an jeder Position durchzugehen (wie es Deep Blue getan hat), stattdessen intelligent eine kleine Menge sinnvoller Bewegungen ausgewählt und diese stattdessen untersucht werden. Um sie zu erkunden, wird die Zukunft jeder dieser Bewegungen „ausgerollt“ und anhand ihrer imaginären Ergebnisse verglichen. (Im Ernst - das ist alles, was ich denke, um diesen Aufsatz zu verstehen.)

Nun - zurück zum Screenshot aus dem Papier. Go ist ein „perfektes Informationsspiel“ (bitte lesen Sie die Definition im Link, keine Sorge, es ist nicht beängstigend). Und theoretisch ist es bei solchen Spielen möglich, dass Sie unabhängig davon, an welcher Position Sie sich im Spiel befinden (selbst wenn Sie gerade 1–2 Züge gespielt haben), richtig erraten können, wer gewinnt oder verliert (vorausgesetzt, beide Spieler spielen "Perfekt" von diesem Punkt an). Ich habe keine Ahnung, wer auf diese Theorie gekommen ist, aber sie ist eine grundlegende Annahme in diesem Forschungsprojekt und funktioniert.

Das heißt, wenn ein Zustand des Spiels gegeben ist, gibt es eine Funktion v * (s), die das Ergebnis vorhersagen kann, sagen wir, die Wahrscheinlichkeit, dass Sie dieses Spiel gewinnen, von 0 bis 1. Sie nennen es die "optimale Wertfunktion". . Da einige Board-Positionen mit größerer Wahrscheinlichkeit zu einem Gewinn führen als andere Board-Positionen, können sie als „wertvoller“ angesehen werden als die anderen. Lassen Sie es mich noch einmal sagen: Wert = Wahrscheinlichkeit zwischen 0 und 1 von Ihnen, die das Spiel gewinnen.

Aber warten Sie - sagen Sie, neben Ihnen saß ein Mädchen namens Foma, während Sie Schach spielen, und sie sagt Ihnen bei jedem Schritt, ob Sie gewinnen oder verlieren. "Du gewinnst ... du verlierst ... Nein, du verlierst immer noch ..." Ich denke, es würde dir nicht viel helfen, zu entscheiden, welchen Schritt du machen musst. Sie wäre auch ziemlich nervig. Was Ihnen stattdessen helfen würde, wäre, wenn Sie den gesamten Baum aller möglichen Züge zeichnen würden, die Sie ausführen können, und die Zustände, zu denen diese Züge führen würden - und dann würde Foma Ihnen für den gesamten Baum sagen, welche Zustände Gewinnzustände sind und welche Zustände Staaten verlieren. Dann können Sie Züge auswählen, die Sie immer wieder zu gewinnenden Staaten führen. Plötzlich ist Foma Ihr Partner in Sachen Kriminalität, kein nerviger Freund. Hier verhält sich Foma wie Ihre optimale Wertfunktion v * (s). Früher wurde angenommen, dass es nicht möglich ist, eine genaue Wertefunktion wie Foma für das Go-Spiel zu haben, da die Spiele so viel Unsicherheit hatten.

ABER - selbst wenn Sie die wunderbare Foma hatten, wird diese Wunderlandstrategie, alle möglichen Positionen für die Bewertung der Foma herauszuarbeiten, in der realen Welt nicht sehr gut funktionieren. Wenn Sie in einem Spiel wie Chess or Go, wie bereits erwähnt, versuchen, sich 7 bis 8 Züge in die Zukunft vorzustellen, kann es so viele mögliche Positionen geben, dass Sie nicht genug Zeit haben, um alle mit Foma zu überprüfen.

Foma ist also nicht genug. Sie müssen die Liste der Züge auf einige sinnvolle Züge eingrenzen, die Sie in die Zukunft einführen können. Wie wird Ihr Programm das machen? Lusha betreten. Lusha ist eine erfahrene Schachspielerin und Enthusiastin, die jahrzehntelang Großmeister dabei beobachtet hat, wie sie Schach gegeneinander spielt. Sie kann sich Ihre Brettposition ansehen, schnell alle verfügbaren Züge ansehen, die Sie machen können, und Ihnen sagen, wie wahrscheinlich es ist, dass ein Schachexperte einen dieser Züge macht, wenn er an Ihrem Tisch sitzt. Wenn Sie also 50 mögliche Züge an einem Punkt haben, teilt Ihnen Lusha die Wahrscheinlichkeit mit, dass jeder Zug von einem Experten ausgewählt wird. Natürlich haben einige vernünftige Bewegungen eine viel höhere Wahrscheinlichkeit und andere sinnlose Bewegungen eine sehr geringe Wahrscheinlichkeit. Beispiel: Wenn Sie im Schach sagen, dass Ihre Königin in einer Ecke des Spiels in Gefahr ist, haben Sie möglicherweise immer noch die Möglichkeit, einen kleinen Bauern in einer anderen Ecke des Spiels zu bewegen. Sie ist Ihre Richtlinienfunktion, p (a \ s) . Für einen bestimmten Zustand kann sie Ihnen Wahrscheinlichkeiten für alle möglichen Schritte geben, die ein Experte ausführen würde.

Wow - Sie können Lushas Hilfe nutzen, um einige sinnvolle Züge auszuwählen, und Foma wird Ihnen die Wahrscheinlichkeit eines Gewinns aus jedem dieser Züge mitteilen. Sie können den Zug wählen, den sowohl Foma als auch Lusha genehmigen. Wenn Sie besonders vorsichtig sein möchten, können Sie die von Lusha ausgewählten Bewegungen ausführen, von Foma bewerten lassen, einige davon auswählen, um sie in Zukunft weiterzuentwickeln, und sich weiterhin von Foma und Lusha dabei helfen lassen, SEHR weit vorauszusagen Die Zukunft des Spiels - viel schneller und effizienter, als alle Schritte bei jedem Schritt in die Zukunft zu durchlaufen. Dies ist das, was sie unter "Reduzierung des Suchraums" verstehen. Verwenden Sie eine Wertefunktion (Foma), um Ergebnisse vorherzusagen, und eine Richtlinienfunktion (Lusha), um Ihnen Großmeisterwahrscheinlichkeiten zu geben, mit denen Sie die von Ihnen ausgeführten Bewegungen eingrenzen können. Diese werden als "Monte-Carlo-Rollouts" bezeichnet. Während Sie von der Zukunft in die Gegenwart zurückkehren, können Sie Durchschnittswerte aller verschiedenen Bewegungen, die Sie ausgeführt haben, ermitteln und die am besten geeignete Aktion auswählen. Bisher hat dies in Go nur auf einer schwachen Amateurebene funktioniert, da die Richtlinien- und Wertefunktionen, mit denen diese Rollouts gesteuert wurden, nicht so gut waren.

Puh.

Die erste Zeile ist selbsterklärend. In MCTS können Sie mit einem ungelernten Foma und einem ungelernten Lusha beginnen. Je mehr Sie spielen, desto besser können sie solide Ergebnisse und Bewegungen vorhersagen. "Die Suche auf einen Strahl von Aktionen mit hoher Wahrscheinlichkeit zu beschränken" ist nur eine raffinierte Art zu sagen: "Lusha hilft Ihnen dabei, die Bewegungen, die Sie ausführen müssen, einzugrenzen, indem Sie ihnen Wahrscheinlichkeiten zuweisen, mit denen ein Experte sie spielen würde." Frühere Arbeiten haben diese Technik verwendet, um starke KI-Spieler auf Amateurebene zu erreichen, selbst mit einfachen (oder „flachen“, wie sie es nennen) Richtlinienfunktionen.

Ja, Faltungs-Neuronale Netze eignen sich hervorragend für die Bildverarbeitung. Und da ein neuronales Netzwerk eine bestimmte Eingabe nimmt und eine Ausgabe gibt, ist es im Wesentlichen eine Funktion, oder? Sie können also ein neuronales Netzwerk verwenden, um eine komplexe Funktion zu werden. Sie können also einfach ein Bild der Platinenposition übergeben und das neuronale Netzwerk selbst herausfinden lassen, was los ist. Dies bedeutet, dass es möglich ist, neuronale Netze zu erstellen, die sich wie SEHR genaue Richtlinien- und Wertefunktionen verhalten. Der Rest ist ziemlich selbsterklärend.

Hier diskutieren wir, wie Foma und Lusha trainiert wurden. Um das Richtliniennetzwerk zu trainieren (Vorhersagen für eine bestimmte Position, die Experten auswählen würden), verwenden Sie einfach Beispiele menschlicher Spiele und verwenden sie als Daten für gutes altes überwachtes Lernen.

Und Sie möchten eine andere, etwas andere Version dieses Richtliniennetzwerks für Rollouts trainieren. Dieser wird kleiner und schneller sein. Sagen wir einfach, da Lusha so erfahren ist, braucht sie einige Zeit, um jede Position zu bearbeiten. Sie ist gut darin, den Eingrenzungsprozess zu beginnen, aber wenn Sie versuchen, sie dazu zu bringen, den Vorgang zu wiederholen, wird sie immer noch etwas zu viel Zeit in Anspruch nehmen. Sie trainieren also ein * schnelleres Richtliniennetzwerk * ​​für den Rollout-Prozess (ich nenne es ... Lushas jüngerer Bruder Jerry? Ich weiß, ich weiß, genug mit diesen Namen). Sobald Sie beide langsamen und schnellen Richtliniennetzwerke ausreichend mit menschlichen Spielerdaten trainiert haben, können Sie versuchen, Lusha einige Tage lang auf einem Go-Board gegen sich selbst spielen zu lassen und mehr Übung zu erhalten. Dies ist der Teil des verstärkenden Lernens - eine bessere Version des Richtliniennetzwerks.

Anschließend trainieren Sie Foma für die Wertvorhersage: Bestimmen der Gewinnwahrscheinlichkeit. Sie lassen die KI üben, indem sie sich in einer simulierten Umgebung immer wieder selbst spielt, beobachten jedes Mal das Endergebnis und lernen aus ihren Fehlern, um immer besser zu werden.

Ich werde nicht näher darauf eingehen, wie diese Netzwerke trainiert werden. Weitere technische Details finden Sie im späteren Abschnitt des Dokuments ('Methoden'), den ich hier nicht behandelt habe. Tatsächlich besteht der eigentliche Zweck dieses speziellen Papiers nicht darin, zu zeigen, wie sie das Verstärkungslernen in diesen neuronalen Netzen eingesetzt haben. In einem früheren Artikel von DeepMind, in dem AI das Spielen von ATARI-Spielen beigebracht wurde, wurden bereits einige Techniken des verstärkenden Lernens eingehend erörtert (und ich habe hier bereits eine Erklärung zu diesem Artikel geschrieben). Für dieses Papier war, wie ich in der Zusammenfassung leicht erwähnt und auch im obigen Screenshot unterstrichen habe, die größte Neuerung die Tatsache, dass sie RL mit neuronalen Netzen zur Verbesserung eines bereits beliebten Spielalgorithmus, MCTS, verwendeten. RL ist ein cooles Tool in einer Toolbox, mit dem die Richtlinien und Wertfunktions-Neuronalen Netze nach dem regelmäßigen überwachten Training verfeinert wurden. In diesem Forschungsbericht geht es darum zu beweisen, wie vielseitig und hervorragend dieses Tool ist, und nicht darum, Ihnen den Umgang damit beizubringen. In der Fernsehsprache war die Atari-Zeitung eine RL-Werbung, und diese AlphaGo-Zeitung ist eine Werbung.

Okay, wir sind endlich mit den Einführungsteilen fertig. Inzwischen haben Sie bereits ein sehr gutes Gefühl dafür, worum es bei AlphaGo ging.

Als nächstes gehen wir etwas tiefer in jede Sache ein, die wir oben besprochen haben. Sie sehen vielleicht einige hässlich und gefährlich aussehende mathematische Gleichungen und Ausdrücke, aber sie sind einfach (ich erkläre sie alle). Entspannen.

Eine kurze Notiz, bevor Sie fortfahren. Möchten Sie mir helfen, weitere solche Aufsätze zu schreiben, in denen coole Forschungsarbeiten erklärt werden? Wenn Sie es ernst meinen, würde ich gerne mit Ihnen zusammenarbeiten. Bitte hinterlassen Sie einen Kommentar und ich werde mich mit Ihnen in Verbindung setzen.

Ein Foto von zwei japanischen Frauen, die Go spielen, hier platziert, falls Sie es schon satt haben, lange Textplatten zu betrachten.

Der erste Schritt besteht also darin, unsere Politik NN (Lusha) zu trainieren, um vorherzusagen, welche Züge wahrscheinlich von einem Experten gespielt werden. Das Ziel dieses NN ist es, der KI zu ermöglichen, ähnlich wie ein erfahrener Mensch zu spielen. Dies ist ein Faltungs-Neuronales Netzwerk (wie ich bereits erwähnt habe, es ist eine spezielle Art von NN, die bei der Bildverarbeitung sehr nützlich ist), das ein vereinfachtes Bild einer Platinenanordnung aufnimmt. "Gleichrichter-Nichtlinearitäten" sind Schichten, die der Netzwerkarchitektur hinzugefügt werden können. Sie geben ihm die Möglichkeit, komplexere Dinge zu lernen. Wenn Sie schon einmal NNs trainiert haben, haben Sie möglicherweise die Ebene „ReLU“ verwendet. Das sind diese.

Die Trainingsdaten hier waren in Form von zufälligen Paaren von Brettpositionen, und die Bezeichnungen waren die Aktionen, die von Menschen ausgewählt wurden, als sie sich in diesen Positionen befanden. Nur regelmäßig überwachtes Lernen.

Hier verwenden sie "stochastischen Gradienten ASCENT". Nun, dies ist ein Algorithmus für die Backpropagation. Hier versuchen Sie, eine Belohnungsfunktion zu maximieren. Und die Belohnungsfunktion ist nur die Wahrscheinlichkeit der von einem menschlichen Experten vorhergesagten Aktion; Sie möchten diese Wahrscheinlichkeit erhöhen. Aber hey - du musst nicht wirklich viel darüber nachdenken. Normalerweise trainieren Sie das Netzwerk so, dass eine Verlustfunktion minimiert wird. Dies ist im Wesentlichen der Fehler / Unterschied zwischen dem vorhergesagten Ergebnis und der tatsächlichen Bezeichnung. Das nennt man Gradientenabstieg. Bei der tatsächlichen Umsetzung dieses Forschungspapiers haben sie tatsächlich den regulären Gradientenabstieg verwendet. Sie können leicht eine Verlustfunktion finden, die sich der Belohnungsfunktion entgegengesetzt verhält, sodass durch Minimieren dieses Verlusts die Belohnung maximiert wird.

Das Richtliniennetzwerk besteht aus 13 Ebenen und wird als "SL-Richtliniennetzwerk" bezeichnet (SL = überwachtes Lernen). Die Daten stammen von einer… Ich sage nur, es ist eine beliebte Website, auf der Millionen von Menschen Go spielen. Wie gut hat dieses SL-Richtliniennetzwerk funktioniert?

Es war genauer als das, was andere Forscher zuvor getan hatten. Der Rest des Absatzes ist ziemlich selbsterklärend. Was die „Rollout-Richtlinie“ betrifft, erinnern Sie sich vor einigen Absätzen daran, wie langsam das SL-Richtliniennetzwerk in Lusha ist, sodass es sich nicht gut in den MCTS-Algorithmus integrieren lässt. Und wir haben eine andere schnellere Version von Lusha trainiert, Jerry, der ihr jüngerer Bruder war? Nun, das bezieht sich hier auf Jerry. Wie Sie sehen können, ist Jerry nur halb so genau wie Lusha, ABER es ist tausendmal schneller! Wenn wir das MCTS anwenden, wird dies wirklich dazu beitragen, die ausgerollten Simulationen der Zukunft schneller zu bewältigen.

In diesem nächsten Abschnitt müssen Sie noch nichts über Reinforcement Learning wissen, aber dann müssen Sie davon ausgehen, dass alles, was ich sage, funktioniert. Wenn Sie sich wirklich mit Details befassen und sich um alles kümmern möchten, sollten Sie zuerst ein wenig über RL lesen.

Sobald Sie das SL-Netzwerk haben, das auf überwachte Weise unter Verwendung menschlicher Spielerbewegungen mit den menschlichen Bewegungsdaten trainiert wurde, müssen Sie, wie ich bereits sagte, sie selbst üben lassen und besser werden. Das machen wir hier. Nehmen Sie einfach das SL-Richtliniennetzwerk, speichern Sie es in einer Datei und erstellen Sie eine weitere Kopie davon.

Dann verwenden Sie das Verstärkungslernen, um es zu optimieren. Hier lässt du das Netzwerk gegen sich selbst spielen und aus den Ergebnissen lernen.

Aber es gibt ein Problem in diesem Trainingsstil.

Wenn Sie nur für immer gegen EINEN Gegner üben und dieser Gegner auch nur ausschließlich mit Ihnen übt, können Sie nicht viel Neues lernen. Sie werden nur trainieren, um zu üben, wie man DIESEN EINEN Spieler schlägt. Dies ist, wie Sie es erraten haben, eine Überanpassung: Ihre Techniken spielen gut gegen einen Gegner, lassen sich aber nicht gut auf andere Gegner übertragen. Wie können Sie das beheben?

Nun, jedes Mal, wenn Sie ein neuronales Netzwerk optimieren, wird es zu einer etwas anderen Art von Player. Sie können diese Version des neuronalen Netzwerks also in einer Liste von „Spielern“ speichern, die sich alle etwas anders verhalten, oder? Großartig - jetzt, während Sie das neuronale Netzwerk trainieren, können Sie es zufällig gegen viele verschiedene ältere und neuere Versionen des Gegners spielen lassen, die aus dieser Liste ausgewählt wurden. Sie sind Versionen desselben Spielers, aber sie spielen alle etwas anders. Und je mehr Sie trainieren, desto MEHR Spieler können Sie noch mehr trainieren! Bingo!

In diesem Training ist das einzige Ziel des Trainingsprozesses das ultimative Ziel, dh Gewinnen oder Verlieren. Sie müssen das Netzwerk nicht speziell trainieren, um beispielsweise mehr Fläche auf dem Brett zu erfassen usw. Sie geben ihm einfach alle möglichen rechtlichen Schritte, aus denen es auswählen kann, und sagen: „Sie müssen gewinnen“. Und deshalb ist RL so vielseitig; Es kann verwendet werden, um Richtlinien oder Wertschöpfungsnetzwerke für jedes Spiel zu trainieren, nicht nur für Go.

Hier testeten sie, wie genau dieses RL-Richtliniennetzwerk für sich allein ohne MCTS-Algorithmus war. Wie Sie sich erinnern würden, kann dieses Netzwerk direkt eine Brettposition einnehmen und entscheiden, wie ein Experte es spielen würde - so können Sie es zum Spielen im Alleingang verwenden. Nun, das Ergebnis war, dass das fein abgestimmte RL-Netzwerk gegen das SL-Netzwerk gewann, das nur für menschliche Bewegungen trainiert wurde. Es gewann auch gegen andere starke Go-Programme.

Hier muss beachtet werden, dass das SL-Richtliniennetzwerk bereits vor dem Training dieses RL-Richtliniennetzwerks besser war als der Stand der Technik - und jetzt hat es sich weiter verbessert! Und wir sind noch nicht einmal zu anderen Teilen des Prozesses wie dem Wertschöpfungsnetzwerk gekommen.

Wussten Sie, dass Pinguinbabys lauter niesen können als ein Hund bellen kann? Eigentlich stimmt das nicht, aber ich dachte, Sie möchten hier einen kleinen Witz, um von den beängstigend aussehenden Gleichungen oben abzulenken. Kommen wir noch einmal zum Aufsatz: Wir sind fertig damit, Lusha hier zu trainieren. Nun zurück zu Foma - erinnern Sie sich an die „Optimalwertfunktion“: v * (s) -> die Ihnen nur sagt, wie wahrscheinlich es ist, dass Sie in Ihrer aktuellen Brettposition gewinnen, wenn beide Spieler von diesem Punkt an perfekt spielen? Um einen NN zu unserer Wertfunktion auszubilden, brauchen wir natürlich einen perfekten Spieler… den wir nicht haben. Wir verwenden also nur unseren stärksten Spieler, der zufällig unser RL-Richtliniennetzwerk ist.

Es nimmt den aktuellen Status des Board-Status an und gibt die Wahrscheinlichkeit aus, dass Sie das Spiel gewinnen werden. Sie spielen ein Spiel und lernen das Ergebnis kennen (Gewinn oder Verlust). Jeder der Spielzustände fungiert als Datenstichprobe, und das Ergebnis dieses Spiels fungiert als Bezeichnung. Wenn Sie also ein Spiel mit 50 Zügen spielen, haben Sie 50 Datenbeispiele für die Wertvorhersage.

Lol Nein. Dieser Ansatz ist naiv. Sie können nicht alle 50 Züge aus dem Spiel verwenden und sie dem Datensatz hinzufügen.

Der Trainingsdatensatz musste sorgfältig ausgewählt werden, um eine Überanpassung zu vermeiden. Jeder Zug im Spiel ist dem nächsten sehr ähnlich, weil Sie sich nur einmal bewegen und das Ihnen eine neue Position gibt, oder? Wenn Sie die Zustände bei allen 50 dieser Züge nehmen und sie mit demselben Etikett zu den Trainingsdaten hinzufügen, haben Sie im Grunde viele "irgendwie doppelte" Daten, und das führt zu einer Überanpassung. Um dies zu verhindern, wählen Sie nur sehr unterschiedlich aussehende Spielzustände. So wählen Sie beispielsweise anstelle aller 50 Züge eines Spiels nur 5 aus und fügen sie dem Trainingssatz hinzu. DeepMind nahm 30 Millionen Positionen aus 30 Millionen verschiedenen Spielen ein, um die Wahrscheinlichkeit von doppelten Daten zu verringern. Und es hat funktioniert!

Nun etwas Konzeptionelles: Es gibt zwei Möglichkeiten, den Wert einer Board-Position zu bewerten. Eine Option ist eine magische Optimalwertfunktion (wie die, die Sie oben trainiert haben). Die andere Möglichkeit besteht darin, einfach mit Ihrer aktuellen Richtlinie (Lusha) in die Zukunft zu rollen und das Endergebnis dieser Einführung zu überprüfen. Offensichtlich würde das echte Spiel selten nach Ihren Plänen verlaufen. DeepMind verglich jedoch, wie diese beiden Optionen funktionieren. Sie können auch eine Mischung dieser beiden Optionen ausführen. Wir werden etwas später etwas über diesen „Mischparameter“ erfahren. Machen Sie sich also eine mentale Notiz über dieses Konzept!

Nun, Ihr einzelnes neuronales Netzwerk, das versucht, die optimale Wertfunktion zu approximieren, ist NOCH BESSER als Tausende von mentalen Simulationen mit einer Rollout-Richtlinie! Foma hat hier wirklich in den Arsch getreten. Als sie die Richtlinie für schnellen Rollout durch die doppelt so genaue (aber langsame) RL-Richtlinie Lusha ersetzten und damit Tausende von Simulationen durchführten, war sie besser als Foma. Aber nur etwas besser und zu langsam. Damit Foma die Gewinnerin dieses Wettbewerbs ist, hat sie bewiesen, dass sie nicht ersetzt werden kann.

Nachdem wir die Richtlinien- und Wertfunktionen geschult haben, können wir sie mit MCTS kombinieren und unseren ehemaligen Weltmeister, den Zerstörer der Großmeister, den Durchbruch einer Generation mit einem Gewicht von zweihundertachtundsechzig Pfund, einem einzigen Alphaaaaa GO, gebären !

In diesem Abschnitt sollten Sie im Idealfall ein etwas tieferes Verständnis der inneren Funktionsweise des MCTS-Algorithmus haben, aber was Sie bisher gelernt haben, sollte ausreichen, um Ihnen ein gutes Gefühl dafür zu geben, was hier vor sich geht. Das einzige, was Sie beachten sollten, ist, wie wir die Richtlinienwahrscheinlichkeiten und Wertschätzungen verwenden. Wir kombinieren sie während des Rollouts, um die Anzahl der Züge, die wir bei jedem Schritt ausführen möchten, einzugrenzen. Q (s, a) repräsentiert die Wertfunktion und u (s, a) ist eine gespeicherte Wahrscheinlichkeit für diese Position. Ich erkläre es.

Denken Sie daran, dass das Richtliniennetzwerk überwachtes Lernen verwendet, um Expertenbewegungen vorherzusagen? Und es gibt Ihnen nicht nur den wahrscheinlichsten Zug, sondern auch Wahrscheinlichkeiten für jeden möglichen Zug, die angeben, wie wahrscheinlich es ist, dass es sich um einen Expertenzug handelt. Diese Wahrscheinlichkeit kann für jede dieser Aktionen gespeichert werden. Hier nennen sie es "vorherige Wahrscheinlichkeit", und sie verwenden es offensichtlich, während sie auswählen, welche Aktionen untersucht werden sollen. Um zu entscheiden, ob Sie einen bestimmten Zug untersuchen oder nicht, müssen Sie zwei Dinge berücksichtigen: Erstens, wie wahrscheinlich ist es, dass Sie gewinnen, wenn Sie diesen Zug spielen? Ja, wir haben bereits unser „Wertschöpfungsnetzwerk“, um diese erste Frage zu beantworten. Und die zweite Frage ist, wie wahrscheinlich ist es, dass ein Experte diesen Schritt wählt? (Wenn es sehr unwahrscheinlich ist, dass ein Umzug von einem Experten ausgewählt wird, warum sollten Sie dann überhaupt Zeit damit verschwenden, dies in Betracht zu ziehen? Dies erhalten wir vom Richtliniennetzwerk.)

Lassen Sie uns dann über den „Mischparameter“ sprechen (siehe darauf zurückkommen!). Wie bereits erwähnt, haben Sie zur Bewertung von Positionen zwei Möglichkeiten: Erstens: Verwenden Sie einfach das Wertnetzwerk, das Sie verwendet haben, um Zustände die ganze Zeit über zu bewerten. Und zweitens können Sie versuchen, mit Ihrer aktuellen Strategie schnell ein Rollout-Spiel zu spielen (vorausgesetzt, der andere Spieler spielt ähnlich) und zu sehen, ob Sie gewinnen oder verlieren. Wir haben gesehen, dass die Wertefunktion besser ist als Rollouts im Allgemeinen. Hier kombinieren sie beide. Sie versuchen, jeder Vorhersage eine Wichtigkeit von 50 bis 50 oder 40 bis 60 oder 0 bis 100 usw. zu geben. Wenn Sie dem ersten einen Prozentsatz von X hinzufügen, müssen Sie dem zweiten 100-X hinzufügen. Das bedeutet dieser Mischparameter. Sie werden diese Treffer- und Versuchsergebnisse später in der Veröffentlichung sehen.

Nach jedem Rollout aktualisieren Sie Ihren Suchbaum mit den Informationen, die Sie während der Simulation erhalten haben, damit Ihre nächste Simulation intelligenter wird. Und am Ende aller Simulationen wählen Sie einfach den besten Zug aus.

Interessante Einblicke hier!

Erinnern Sie sich, wie die von RL fein abgestimmte Richtlinien-NN besser war als nur die von Menschen geschulte SL-Richtlinien-NN? Wenn Sie sie jedoch in den MCTS-Algorithmus von AlphaGo einfügen, erwies sich die Verwendung des vom Menschen trainierten NN als bessere Wahl als das fein abgestimmte NN. Bei der Wertefunktion (an die Sie sich erinnern würden, dass ein starker Spieler einen perfekten Spieler annähert) funktioniert das Training von Foma mithilfe der RL-Richtlinie besser als das Training mit der SL-Richtlinie.

„All diese Auswertungen erfordern viel Rechenleistung. Wir mussten wirklich die großen Waffen herausholen, um diese verdammten Programme ausführen zu können. “

Ein weiteres Foto aus dem ersten Spiel von AlphaGo gegen Lee Sedol.

Selbsterklärend.

"LOL, unser Programm hat buchstäblich die Hosen von jedem anderen Programm, das vor uns kam, umgehauen."

Dies geht wieder auf diesen „Mischparameter“ zurück. Bei der Bewertung von Positionen war es besser, sowohl der Wertefunktion als auch den Rollouts die gleiche Bedeutung zu geben, als nur eine davon zu verwenden. Der Rest ist selbsterklärend und enthüllt einen interessanten Einblick!

Selbsterklärend.

Selbsterklärend. Aber lesen Sie diesen rot unterstrichenen Satz noch einmal. Ich hoffe, Sie können jetzt klar sehen, dass diese Zeile hier so ziemlich die Zusammenfassung dessen ist, worum es bei diesem gesamten Forschungsprojekt ging.

Abschließender Absatz. "Lassen Sie uns hier ein bisschen mehr prahlen, weil wir es verdienen!" :) :)

Oh, und wenn Sie ein Wissenschaftler oder ein Technologieunternehmen sind und Hilfe benötigen, um nicht-technischen Personen Ihre Wissenschaft für Marketing, PR oder Schulung usw. zu erklären, kann ich Ihnen helfen. Schreiben Sie mir eine Nachricht auf Twitter: @mngrwl