Schachmatt durch „CrazyAra“

19.02.2019

Schachmatt durch „CrazyAra“

Künstliche Intelligenz schlägt mehrfachen Weltmeister im Einsetzschach

Der von den TU-Studierenden Johannes Czech, Moritz Willig und Alena Beyer entwickelte Bot „CrazyAra“ hat den Schachprofi Justin Tan in einem Online-Match der Schach-Variante „Crazyhouse“ mit 4:1 geschlagen. Gelernt hat der Bot mittels künstlicher neuronaler Netze, was ihm erlaubt, vorausschauend Entscheidungen zu treffen. Das Besondere: Die Studierenden konnten damit einen Erfolg auf einem Feld feiern, das sonst von Giganten wie Google dominiert wird.

4:1 schlug der von TU-Studierenden entwickelte Bot „CrazyAra“ den Schachprofi Justin Tan in einem Online-Match. Bild: Patrick Bal
4:1 schlug der von TU-Studierenden entwickelte Bot „CrazyAra“ den Schachprofi Justin Tan in einem Online-Match. Bild: Patrick Bal

Kristian Kersting, Professor für Maschinelles Lernen an der TU Darmstadt und einer der Leiter des studentischen Semesterprojekts, ordnet die Leistung der Studierenden im Interview ein:

Was unterscheidet den Bot „CrazyAra“ von einem „herkömmlichen“ Schachcomputer?

Professor Kristian Kersting: Im Gegensatz zu herkömmlichen Schachprogrammen lernt CrazyAra Schach zu spielen. Genauer gesagt, das Programm lernt die Schachvariante Crazyhouse: Schlägt ein Spieler die Figur seines Gegners, wird ihm die entsprechende Figur in seiner eigenen Farbe ausgehändigt, die er nach den gleichen Regeln wie beim Tandemschach einsetzen darf. Dazu folgten Johannes Czech, Moritz Willig und Alena Beyer dem Beispiel von DeepMinds AlphaGo, das 2016 Furore machte, weil es den Südkoreaner Lee Sedol im Brettspiel Go schlug, der als einer der weltbesten Profispieler angesehen wird.

CrazyAra erhielt circa 570.000 heruntergeladene Crazyhouse-Partien und versuchte damit, das demonstrierte Verhalten zu imitieren – daher auch der Name: Die Aras, eine Papageienart, sind für ihre Imitationsgabe bekannt. Der Anspruch des Trios lag aber nicht nur darin, ein Programm zu entwickeln, das das menschliche Spielverhalten imitiert, es sollte auch außerhalb des Trainingsbereichs funktionieren und vorausschauend Entscheidungen treffen können. Dazu lernt CrazyAra eine Nutzenfunktion, die beschreibt, welche Aussicht auf den Sieg eine Spielsituation oder ein Schachzug hat.

Leider gibt es beim Schach wahrscheinlich mehr Möglichkeiten für Spielzüge als es Atome im Weltall gibt. Daher greift CrazyAra auf die bei AlphaGo schon bewährten „Tricks“ der klassischen KI und des Maschinellen Lernens zurück: die Monte-Carlo-Baumsuche (engl. Monte Carlo Tree Search, MCTS) und das Tiefe Lernen (engl. Deep Learning). MCTS ist ein heuristischer Suchalgorithmus zum Finden der vielversprechendsten nächsten Züge. Es simuliert Einsetzschachpartien. In jeder Simulation wird das Spiel bis zum Ende gespielt, indem Züge und das Einsetzen von geschlagenen Figuren nach dem Zufallsprinzip ausgewählt werden. Das Endergebnis jeder Simulation wird dann verwendet, um die Knoten im Spielbaum so zu gewichten, dass in zukünftigen Simulationen eher bessere Knoten gewählt werden. Motiviert durch das menschliche Gehirn benutzt CrazyAra zur Bewertung künstliche neuronale Netzwerke mit mehreren Schichten. Die Schichten sind nacheinander so verschaltet und initialisiert, dass sie immer komplexere, höhere Merkmale (implizite Regelmäßigkeiten) der Bewertungsdaten automatisch lernen und erfassen. Daher kann das „tiefe“ Lernen auf viel komplexere Weise lernen, als es mit sogenannten „flachen“ Lernern möglich ist, die keine höheren Merkmale ableiten.

In ersten Versuchen mit dem Originaldesign von AlphaGo beobachteten die Studierenden, dass AlphaGo nicht in der Lage war, alle möglichen Spielzüge von Crazyhouse ausreichend abzubilden. Daher modifizierte das Trio das Originaldesign von AlphaGo im Rahmen eines Semesterprojekts für den Kurs „Deep Learning: Architectures & Methods“. Mittels so genannten „sequeeze-and-excitation“-Einheiten kann sich das Netzwerk zum Beispiel jetzt besser auf bestimmte Spielfelder je nach Spielsituation „konzentrieren“. Die MCTS beruft sich stärker auf die Bewertungsfunktion und auf bereits bewährte Züge. Dadurch konnte die Zahl der zu bewertenden Züge und damit der Rechenaufwand um eine Größenordnung reduziert werden.

Man kann einfach nur stolz auf die Leistung des studentischen Trios sein. Das Erlernen von Schach und seinen Varianten wird als Lackmustest der KI gesehen. Und den haben Johannes Czech, Moritz Willig und Alena Beyer auf einem Standardrechner mit einer GPU-Einheit (GeForce GTX 1080 Ti/PCIe/SSE2) bestanden. Eine deutsche Universität kann nicht einfach mal 1920 CPUs und 280 GPUs zur Verfügung stellen, so wie DeepMind für AlphaGo in seinen Go-Partien gegen Lee Sedol. Hut ab!

Prof. Dr. Kristian Kersting. Bild: Katrin Binner
Prof. Dr. Kristian Kersting. Bild: Katrin Binner

Warum ist Schach ein gutes Entwicklungsfeld für Künstliche Intelligenz?

Es gibt unzählige Brettspiele wie z.B. Schach, die vermeintlich simpel erscheinen, da sie meist aus einfachen Spielbrettern und einer überschaubaren Menge an Spielsteinen bestehen. Man merkt allerdings schnell, dass es doch deutlich schwieriger ist, diese Spiele zu meistern. Schach zum Beispiel hat geschätzt mehr als 1046 verschiedene Positionen, in denen die Figuren angeordnet sein können. Wer Schach spielen kann, muss also intelligent sein.

Das haben auch die Gründungsväter der KI so gesehen. Der Traum, dass der Mensch eine Maschine konstruieren und bauen könnte, die auf irgendeine Art und Weise intelligentes Verhalten zeigt, ist alt. Allerdings ist die Frage immer die gleiche: Was ist die Messlatte für Intelligenz, ob nun menschliche oder maschinelle Intelligenz? Eine der Antworten: Schach.

Allerdings hat sich mit AlphaGo und seinem Nachfolger AlphaZero die Fragestellung verändert. Es geht nicht mehr darum, ob Maschinen Schach auf Weltmeister-Niveau spielen können. Heutzutage hat kaum ein Mensch eine Chance gegen Schachprogramme wie z.B. Stockfish 8. Bisher verließen sich Schachcomputer auf menschliche Spielstrategien. Aber muss das so sein? Oder können Maschinen sich selbst beibringen, Schach auf Weltmeister-Niveau zu spielen?

AlphaZero hat genau das gezeigt. Es braucht keine menschlichen Spielstrategien und kommt dennoch zu erstaunlichen Ergebnissen. Die KI hat sich das Spiel in nur vier Stunden angeeignet. Dazu bekam AlphaZero die Schachregeln vorgegeben und spielte dann immer wieder gegen sich selbst.

Wichtiger ist, dass das nicht nur für Schach funktioniert. Im japanischen Spiel Shogi hat AlphaZero nach zwei Stunden Lernzeit 90 von 100 Spielen gegen das Weltmeisterprogramm Elmo gewonnen, in Go erreichte die KI nach acht Stunden ein Niveau, das ihr erlaubte, 60 von 100 Spielen gegen ihren auf Go spezialisierten Vorgänger AlphaGo zu gewinnen.

Das ist bemerkenswert, denn wir Menschen können ja auch nicht nur ein einzelnes Spiel erlernen. AlphaZero ist ein starker Hinweis, dass auch Maschinen mit einem einzelnen Algorithmus flexibel unterschiedliche Aufgabe erlernen können. Ob das wirklich so ist, bleibt aber noch eine offene Forschungsfrage. Daher ist der Erfolg von CrazyAra so wichtig für die KI-Forschung. Es zeigt, dass eine KI auch die zusätzliche Komplexität meistern kann, wenn geschlagene Spielfiguren beim Schach ins Spiel zurückkehren können. Das hilft uns die Grenzen von AlphaGo, AlphaZero und KI besser zu verstehen.

Was war die größte Herausforderung an dem Projekt?

Fragt man die Studierenden, dann war die größte Herausforderung das erfolgreiche Training des tiefen Netzwerkes auf den Daten ohne numerische Instabilitäten und „Explosion“ der Gradienten-Updates. Denn je größer das Netzwerk, desto besser die Adaption auf Einzelschach, so hofft man, aber desto größer auch der Rechenaufwand. Es kommt zur Explosion der Berechnungen, insbesondere wenn man nicht die Infrastruktur wie das Projekt DeepMind hat. Anfangs hatte das Trio ein kleineres Netzwerk benutzt. Das verhielt sich numerisch zwar stabiler, hat aber nicht so gut Einsetzschach gelernt. Eine weitere Schwierigkeit bestand darin, die 570.000 heruntergeladenen Crazyhouse-Partien in eine maschinenlesbare Form zu bringen. Hierfür wurde Parallelisierung verwendet sowie eine effiziente Komprimierung, der Matrix-Repräsentation der Schachbrettstellungen.

JannLee im Schachduell mit dem TU-Bot CrazyAra. Bild: lichess.org
JannLee im Schachduell mit dem TU-Bot CrazyAra. Bild: lichess.org

Waren die Studierenden beim Beobachten der Partien aufgeregt oder wussten sie sehr schnell, dass „CrazyAra“ gewinnen wird?“

Naja, sicher waren die Studierenden angespannt. Lampenfieber gehört dazu. Aber sie waren auch gut vorbereitet. CrazyAra war getestet worden, um sicherzustellen, dass es nicht zu Abstürzen oder Ähnlichem kommt.

Johannes Czech sagte mir, dass das Team wusste, dass beide Seiten Chancen hätten. Sie wollten vor allem vermeiden, JannLee bloßzustellen oder dass die Partien zu einseitig würden – vor allem, da große Teile der Trainingsdaten von JannLee stammen und er auch eine Inspiration für das Projekt war. Die Studierenden haben sich gefreut, dass der Champion die Match-Einladung angenommen hat.

Der Spieler erklärte nach den Partien, er habe das Gefühl gehabt, gegen einen Menschen und nicht gegen eine Maschine angetreten zu sein. Wie schätzen Sie das ein? Sprechen wir hier schon über eine allgemeine künstliche Intelligenz?

Intelligenz hat viele Qualitäten. Es ist es schwierig, sie zu messen. Technologisch sollte man CrazyAra als ein KI-System und in dem Sinne als eine KI sehen. Aber man sollte CrazyAra kein menschliches Denkvermögen unterstellen. AlphaGo, AlphaZero und CrazyAra zeigen aber eindrucksvoll, dass Maschinen komplizierte, der Intelligenz zugeschriebene Aufgaben erlernen können. Das ist eine wichtige Voraussetzung für eine allgemeine, künstliche Intelligenz.

Das Projekt ist ein Beispiel dafür, dass KI auch in der Lehre an der TU eine große Rolle spielt. Wo steht die Forschung an der TU? Was sind Ihre aktuellen Forschungsfragen?

Der Fachbereich Informatik der TU Darmstadt deckt den Bereich der KI so umfassend ab wie kaum eine andere Universität in Deutschland. Dazu gehören: Machine Learning, Computer Vision, Data Mining, Deep Learning, Natural Language Processing und Robotics. Diese breite KI-Expertise wird auch international als exzellent anerkannt und in Netzwerken wirkungsvoll verankert. In den KI-Themen Maschinelles Lernen, Robotik, Computersehen und Verarbeiten von natürlicher Sprache ist die TU Darmstadt, gemessen an Publikations-Rankings, die Nummer 1 in Deutschland und die Nummer 2 in Europa. In der internationalen und deutschen Forschungslandschaft ist die TU Darmstadt auf dem Gebiet der KI führend.

Die Aufgabe: Künstliche Intelligenz muss zu einem coadaptiven Prozess werden, in dem der Nutzer das Verhalten der KI beeinflusst, der Nutzer sich aber auch auf die KI einstellen kann, um sie effektiver zu nutzen. Fragestellungen ändern sich mit der Zeit, sie passen sich ihren Überlegungen und Ergebnissen an. Neue Fragestellungen entstehen. Alte Fragestellungen werden verworfen. Da muss die KI mithalten können. Es ist auch essentiell, dass Vorhersagen und Entscheidungen durch Menschen nachvollziehbar sind. Um KI erfolgreich gestalten zu können, müssen aber auch viele praxisrelevante Forschungsfragen der Cybersicherheit und des Schutzes der Privatsphäre behandelt werden.

Die breite KI-Expertise in Darmstadt ist einfach toll und führt automatisch zu Gesprächen und Diskussion über die einzelnen Fachgebiete und -bereiche und Grenzen von Institutionen hinweg. Das bekommen auch die Studierenden mit. Die Ausbildung wird breiter, Querbezüge werden klar, Synergien entstehen. Das ist wichtig, denn KI braucht viele Qualitäten: Sie ist ein Team-Sport.

Die Fragen stellten Bettina Bastian und Silke Paradowski

zur Liste