Eine KI auf Basis von DeepMinds AlphaZero hat Algorithmen entwickelt, die, wenn man sie in die Standardprogrammiersprache C++ übersetzt, lange Listen von Daten bis zu dreimal schneller sortieren können als von Menschen erstellte Sortierverfahren.

»Es hat uns regelrecht schockiert«, sagt Daniel Mankowitz, ein Informatiker bei der Google-Tochter DeepMind, unter dessen Federführung die Arbeit entstand. »Zu Anfang konnten wir es selbst kaum glauben.«

Seit Jahrzehnten feilt die Informatik daran, die Datenverarbeitung von Computern zu optimieren, um entscheidende Millisekunden bei der Rückgabe von Suchergebnissen oder beim Ordnen von Kontaktlisten einzusparen. Jetzt hat die Londoner KI-Schmiede DeepMind mit Hilfe der Technologie hinter AlphaZero – ihrem KI-System für Brettspiele wie Schach, Go und Shogi – das Tempo der Datensortierung erheblich gesteigert. »Das ist ein spannendes Ergebnis«, bemerkt Emma Brunskill, Informatikerin an der Stanford University in Kalifornien.

Das System, AlphaDev genannt, wird in einer Arbeit im Fachmagazin »Nature« beschrieben. Dort schildert das Team, wie die KI schnellere Algorithmen entwickelt hat, die bereits in zwei Standard-C++-Bibliotheken integriert wurden und daher täglich billionenfach von Programmen auf der ganzen Welt genutzt werden.

Die Forscher gaben AlphaDev zunächst die Aufgabe, Zahlen nach Größe zu sortieren. Sie fingen klein an, mit Algorithmen, wie sie auch für lange Listen verwendet werden, aber ließen sie nur drei, vier oder fünf Zahlen auf einmal sortierten. AlphaDev arbeitete auf der Ebene von Assembler-Befehlen: Darunter versteht man jene basale Programmiersprache, in die jedes vom Menschen geschriebene Programm automatisiert übersetzt wird, bevor es in die Einsen und Nullen des Maschinencodes umgewandelt wird.

AlphaDev arbeitet ähnlich wie sein Vorgänger AlphaZero. Dieses System nutzt die KI-Variante von menschlicher Intuition und menschlichem Nachdenken, um Spielzüge in einem Brettspiel zu wählen. AlphaDev verschiebt allerdings keine Steine, sondern fügt Anweisungen zu einem Prozess hinzu. DeepMind nennt es das »AssemblyGame«.

Sortieren wird zum Spiel für die KI

AlphaZero »überlegt«, indem es an jedem Entscheidungspunkt all seine möglichen Züge sowie die möglichen Folgezüge und so weiter betrachtet. Innerhalb dieses Verzweigungsbaums berechnet es dann, welche Spielzüge mit höchster Wahrscheinlichkeit zum Gewinn führen. Aber alle möglichen Verzweigungen zu betrachten, würde länger dauern, als das Universum alt ist. Daher greift es auf eine Art von Intuition zurück, um die Suche zu verfeinern.

Bei jedem Schritt speist das Computerprogramm den aktuellen Spielstand in neuronale Netze ein. Diese lernfähigen Systeme heben dann die erfolgversprechendsten Züge hervor. Was Erfolg verspricht, haben sie während der vorhergehenden Trainingsphase gelernt, indem sie kontinuierlich auf Basis der Spielausgänge aktualisiert wurden. AlphaZero geht dabei auch ungewöhnliche Wege, indem es beispielsweise nicht immer den aktuell am besten bewerteten Zug auswählt, sondern auch andere Optionen in Betracht zieht.

AlphaDev kann eine von vier Aktionsarten durchführen, die es ihm erlauben, Werte zu vergleichen oder zu verschieben und zu einer anderen Stelle im Programm zu springen. Nach jedem Durchlauf versucht es eine Reihe von Listen zu sortieren und erhält eine umso höhere Belohnung, je mehr Elemente in den Listen es korrekt sortiert hat. Es spielt so lange, bis alle Listen perfekt sind oder eine Programmlängenbegrenzung erreicht wird. Dann beginnt es von Neuem, ein Programm zu entwickeln.

Die neuronalen Netzwerke prüften und belohnten die Programme nicht nur mit Blick auf die Richtigkeit, sondern auch auf die Geschwindigkeit. Mankowitz und sein Team brachten dem System bei, abzuschätzen, wie schnell das neu entwickelte Programm ist – entweder anhand der Zahl an Anweisungen oder anhand der Zeit, die es zur Verarbeitung brauchte. Abhängig vom verwendeten Prozessor und von der Menge der zu sortierenden Daten arbeiteten die besten Algorithmen von AlphaDev zwischen 4 Prozent und 71 Prozent schneller als ihre von Menschen geschaffenen Pendants. Wenn allerdings die Algorithmen mehrmals hintereinander Listen mit einer Viertelmillion Werten sortieren sollten, verringerte sich die gesamte eingesparte Zeit auf nur ein bis zwei Prozent. Dies lag daran, dass das System nicht alle Teile des Codes optimiert hatte.

Das Team von DeepMind hat AlphaDev auch auf Algorithmen angewendet, bei denen es nicht um Sortierung geht, zum Beispiel auf einen Algorithmus, der Daten, die in einem bestimmten Format gespeichert sind, in Bytes verwandelt. Die AlphaDev-Variante benötigte 67 Prozent weniger Zeit als eine Standardversion. Und AlphaDevs Hashing-Algorithmus, der beim Speichern und Abrufen von Daten wichtig ist, brauchte 30 Prozent weniger Zeit als ein Standardalgorithmus.

Zwei überraschende Moves bescheren einen Zeitvorteil

Um herauszufinden, wo AlphaDev seinen Zeitgewinn erzielte, nahm das Team die Algorithmen genauer in Augenschein. Beim Sortieren fanden sie zwei neue Taktiken, die sie als AlphaDev Swap-Move und AlphaDev Copy-Move bezeichneten. Mankowitz vergleicht sie mit »Move 37«, einem überraschenden Zug, den AlphaZeros Vorgänger AlphaGo im Jahr 2016 nutzte. Damals besiegte die KI ihren menschlichen Gegner, den Go-Champion Lee Sedol, in einem Schaukampf in Seoul. »Der Move 37«, erklärt Mankowitz, »hat sich rückblickend tatsächlich als grundlegend für den Spielgewinn erwiesen, aber auch für die Art und Weise, wie wir über Strategien nachdenken.«

Ob aus wissenschaftlicher Sicht besonders viel Tiefe in der neuen Studie stecke, wisse er nicht, sagt Michael Littman, Informatiker an der Brown University in Providence im US-Bundesstaat Rhode Island. AlphaZero existiere immerhin bereits seit sechs Jahren. »Aber die technische Umsetzung, die Anwendung, ist phänomenal«, fügt er hinzu. Die Menschen hinter DeepMind seien gut darin, ihre Methode an neue Probleme anzupassen. Im Jahr 2022 hat DeepMind auch AlphaZero modifiziert, um AlphaTensor zu erschaffen, das Wege fand, mathematische Tensoren schneller zu multiplizieren, als es bislang technisch möglich war.

In Zukunft möchte das Team von DeepMind AlphaZero-ähnliche Algorithmen auf noch mehr Arten von Problemen anwenden – und sogar auf das Design von Hardwarekomponenten selbst, sagt Mankowitz. »Unser Ziel ist, das komplette Paket in Angriff zu nehmen.«