211service.com
Deep-Learning-Maschine bringt sich Schach in 72 Stunden bei und spielt auf internationalem Meisterniveau
Es ist fast 20 Jahre her, seit IBMs Supercomputer Deep Blue den amtierenden Schachweltmeister Garry Kasparov zum ersten Mal nach den Standardturnierregeln besiegte. Seitdem sind schachspielende Computer deutlich stärker geworden und lassen den besten Menschen selbst gegen eine moderne Schachengine, die auf einem Smartphone läuft, kaum eine Chance.
Aber während Computer schneller geworden sind, hat sich die Funktionsweise von Schachengines nicht geändert. Ihre Macht beruht auf roher Gewalt, dem Prozess, alle möglichen zukünftigen Züge zu durchsuchen, um den besten nächsten zu finden.
Natürlich kann kein Mensch damit mithalten oder auch nur annähernd herankommen. Während Deep Blue etwa 200 Millionen Positionen pro Sekunde durchsuchte, suchte Kasparov wahrscheinlich nicht mehr als fünf pro Sekunde. Und doch spielte er im Wesentlichen auf dem gleichen Niveau. Menschen haben eindeutig einen Trick im Ärmel, den Computer noch beherrschen müssen.
Dieser Trick besteht darin, Schachstellungen zu bewerten und die profitabelsten Suchwege einzugrenzen. Das vereinfacht die Rechenaufgabe dramatisch, weil es den Baum aller möglichen Züge auf nur wenige Äste reduziert.
Computer waren darin noch nie gut, aber heute ändert sich das dank der Arbeit von Matthew Lai am Imperial College London. Lai hat eine Maschine mit künstlicher Intelligenz namens Giraffe geschaffen, die sich selbst das Schachspielen beigebracht hat, indem sie Stellungen viel ähnlicher wie Menschen und auf eine völlig andere Weise als herkömmliche Schachmaschinen bewertet.
Direkt nach dem Auspacken spielt die neue Maschine auf dem gleichen Niveau wie die besten konventionellen Schachengines, von denen viele über viele Jahre verfeinert wurden. Auf menschlicher Ebene entspricht es dem Status eines internationalen FIDE-Meisters und platziert es unter den besten 2,2 Prozent der Turnierschachspieler.
Die Technologie hinter Lais neuer Maschine ist ein neuronales Netzwerk. Dies ist eine vom menschlichen Gehirn inspirierte Art der Verarbeitung von Informationen. Es besteht aus mehreren Schichten von Knoten, die so verbunden sind, dass sie sich ändern, wenn das System trainiert wird. Dieser Trainingsprozess verwendet viele Beispiele, um die Verbindungen zu verfeinern, sodass das Netzwerk bei einer bestimmten Eingabe eine bestimmte Ausgabe erzeugt, um beispielsweise das Vorhandensein eines Gesichts auf einem Bild zu erkennen.
In den letzten Jahren sind neuronale Netze dank zweier Fortschritte enorm leistungsfähig geworden. Das erste ist ein besseres Verständnis dafür, wie diese Netzwerke beim Lernen fein abgestimmt werden können, teilweise dank viel schnellerer Computer. Die zweite ist die Verfügbarkeit massiver annotierter Datensätze zum Trainieren der Netzwerke.
Das hat es Informatikern ermöglicht, viel größere Netzwerke zu trainieren, die in vielen Schichten organisiert sind. Diese sogenannten tiefen neuronalen Netze sind enorm leistungsfähig geworden und übertreffen Menschen nun routinemäßig bei Mustererkennungsaufgaben wie Gesichtserkennung und Handschrifterkennung.
Es überrascht also nicht, dass tiefe neuronale Netze in der Lage sein sollten, Muster im Schach zu erkennen, und genau diesen Ansatz verfolgt Lai. Sein Netzwerk besteht aus vier Ebenen, die zusammen jede Position auf dem Brett auf drei verschiedene Arten untersuchen.
Die erste befasst sich mit dem globalen Zustand des Spiels, wie z. B. Anzahl und Art der Figuren auf jeder Seite, welche Seite am Zug ist, Rochaderechte und so weiter. Der zweite befasst sich mit figurzentrierten Merkmalen wie der Position jeder Figur auf jeder Seite, während der letzte Aspekt darin besteht, die Felder abzubilden, die jede Figur angreift und verteidigt.
Lai trainiert sein Netzwerk mit einem sorgfältig generierten Datensatz aus echten Schachpartien. Dieser Datensatz muss die richtige Positionsverteilung aufweisen. Zum Beispiel macht es keinen Sinn, das System auf Stellungen mit drei Damen pro Seite zu trainieren, weil diese Stellungen praktisch nie in echten Spielen vorkommen, sagt er.
Es muss auch eine große Vielfalt an ungleichen Stellungen haben, die über die hinausgehen, die normalerweise in Schachpartien auf höchstem Niveau vorkommen. Denn ungleiche Stellungen treten zwar selten in realen Schachpartien auf, aber bei den Suchen, die der Computer intern durchführt, tauchen sie immer wieder auf.
Und dieser Datensatz muss riesig sein. Die enorme Anzahl von Verbindungen innerhalb eines neuronalen Netzwerks muss während des Trainings fein abgestimmt werden, und dies kann nur mit einem riesigen Datensatz erfolgen. Verwenden Sie einen zu kleinen Datensatz, kann sich das Netzwerk in einen Zustand versetzen, der die Vielzahl von Mustern, die in der realen Welt auftreten, nicht erkennt.
Lai generierte seinen Datensatz, indem er zufällig fünf Millionen Stellungen aus einer Datenbank mit Computerschachpartien auswählte. Anschließend schuf er eine größere Vielfalt, indem er jeder Position einen zufälligen legalen Zug hinzufügte, bevor er sie für das Training verwendete. Insgesamt generierte er auf diese Weise 175 Millionen Positionen.
Die übliche Art, diese Maschinen zu trainieren, besteht darin, jede Position manuell zu bewerten und diese Informationen zu verwenden, um der Maschine beizubringen, die starken und die schwachen zu erkennen.
Aber das ist eine gewaltige Aufgabe für 175 Millionen Stellen. Es könnte von einer anderen Schachengine erledigt werden, aber Lais Ziel war ehrgeiziger. Er wollte, dass die Maschine sich selbst lernt.
Stattdessen verwendete er eine Bootstrapping-Technik, bei der Giraffe gegen sich selbst spielte, mit dem Ziel, ihre Vorhersage der eigenen Einschätzung einer zukünftigen Position zu verbessern. Das funktioniert, weil es feste Bezugspunkte gibt, die letztlich über den Wert einer Position entscheiden – ob das Spiel später gewonnen, verloren oder unentschieden gespielt wird.
Auf diese Weise lernt der Computer, welche Positionen stark und welche schwach sind.
Nachdem Sie Giraffe trainiert haben, besteht der letzte Schritt darin, sie zu testen, und hier sorgen die Ergebnisse für eine interessante Lektüre. Lai testete seine Maschine auf einer Standarddatenbank namens Strategic Test Suite, die aus 1.500 Positionen besteht, die ausgewählt werden, um die Fähigkeit einer Engine zu testen, verschiedene strategische Ideen zu erkennen. Zum Beispiel testet ein Thema das Verständnis der Kontrolle über offene Dateien, ein anderes testet das Verständnis dafür, wie sich die Werte von Läufer und Springer in verschiedenen Situationen relativ zueinander ändern, und wieder ein anderes testet das Verständnis der Zentrumskontrolle, sagt er.
Die Ergebnisse dieses Tests werden von 15.000 Punkten bewertet.
Lai nutzt dies, um die Maschine während ihrer Ausbildung in verschiedenen Stadien zu testen. Zu Beginn des Bootstrapping-Prozesses erreicht Giraffe schnell eine Punktzahl von 6.000 und erreicht schließlich nach nur 72 Stunden einen Höchststand von 9.700. Lai sagt, das passt zu den besten Schachengines der Welt.
[Das] ist bemerkenswert, weil ihre Bewertungsfunktionen alle sorgfältig von Hand entworfene Giganten mit Hunderten von Parametern sind, die über mehrere Jahre sowohl manuell als auch automatisch abgestimmt wurden, und viele von ihnen wurden von menschlichen Großmeistern bearbeitet, fügt er hinzu.
Lai fährt fort, den gleichen Ansatz des maschinellen Lernens zu verwenden, um die Wahrscheinlichkeit zu bestimmen, dass es sich lohnt, einen bestimmten Schritt zu verfolgen. Das ist wichtig, weil es unnötige Suchen in unrentablen Zweigen des Baums verhindert und die Recheneffizienz dramatisch verbessert.
Laut Lai sagt dieser probabilistische Ansatz in 46 Prozent der Fälle den besten Zug voraus und platziert den besten Zug in 70 Prozent der Fälle in seiner Top-3-Rangliste. Der Computer muss sich also nicht um die anderen Züge kümmern.
Das ist eine interessante Arbeit, die eine große Veränderung in der Funktionsweise von Schachengines darstellt. Es ist natürlich nicht perfekt. Ein Nachteil von Giraffe ist, dass neuronale Netze viel langsamer sind als andere Arten der Datenverarbeitung. Laut Lai braucht Giraffe etwa zehnmal länger als eine herkömmliche Schachengine, um die gleiche Anzahl von Stellungen zu suchen.
Aber auch mit diesem Nachteil ist es konkurrenzfähig. Giraffe ist in der Lage, auf einem modernen Mainstream-PC auf dem Niveau eines internationalen FIDE-Meisters zu spielen, sagt Lai. Im Vergleich dazu spielen die Top-Engines auf Super-Grandmaster-Niveau.
Das ist immer noch beeindruckend. Im Gegensatz zu den meisten heute existierenden Schach-Engines bezieht Giraffe ihre Spielstärke nicht aus der Fähigkeit, sehr weit nach vorne zu sehen, sondern aus der Fähigkeit, knifflige Stellungen genau zu bewerten und komplizierte Stellungskonzepte zu verstehen, die für Menschen intuitiv, aber für Schach schwer fassbar sind Motoren für eine lange Zeit, sagt Lai. Dies ist besonders wichtig in der Eröffnungs- und Endspielphase, wo es sich außergewöhnlich gut spielt.
Und das ist nur der Anfang. Lai sagt, es sollte einfach sein, den gleichen Ansatz auf andere Spiele anzuwenden. Eines, das auffällt, ist das traditionelle chinesische Go-Spiel, bei dem Menschen immer noch einen beeindruckenden Vorteil gegenüber ihren Silizium-Konkurrenten haben. Vielleicht könnte Lai das als nächstes ausprobieren.
Ref: arxiv.org/abs/1509.01549 : Giraffe: Mit Deep Reinforcement Learning Schach spielen