Kult-Würfel als Intelligenztest: Forscher haben eine künstliche Intelligenz entwickelt, die den Zauberwürfel in Sekundenbruchteilen lösen kann – effektiver als jeder andere Computer zuvor. Das KI-System fand zudem in 60 Prozent der Fälle den Weg mit den wenigsten Zügen. Interessant ist diese Leistung vor allem deshalb, weil Puzzles wie der Zauberwürfel Milliarden von Zuständen und Lösungswegen haben können.
Der Zauberwürfel – erfunden 1974 von dem ungarischen Architekten Erno Rubik – ist ein dreidimensionales Farbpuzzle. Im Prinzip geht es darum, die 26 willkürlich durcheinandergemischten Farbflächen des Würfels durch Rotation so zu ordnen, dass sich ein Würfel mit einfarbigen Seiten ergibt. In den 1980er Jahren war dieser Würfel Kult und bis heute versuchen sich Enthusiasten im immer schnelleren Lösen des Zauberwürfels zu überbieten. Computer schaffen dies mittlerweile in weniger als einer Sekunde.
Optimaler Lösungsweg gesucht
Allerdings: Weitaus schwieriger ist dieses kombinatorische Puzzle, wenn es nicht nur um Schnelligkeit, sondern um eine Lösung in möglichst wenigen Zügen geht. „Künstliche Intelligenz kann die besten Schach- und Go-Spieler schlagen“, sagt Seniorautor Pierre Baldi von der University of California in Irvine. „Aber die Lösung für den Zauberwürfel erfordert mehr symbolisches, mathematisches und abstraktes Denken.“
Gängige KI-Systeme wie AlphaGo oder Alpha Zero können den Zauberwürfel zwar lösen. Doch sie benötigen dafür relativ lange und produzieren oft Lösungen, die viele Züge länger sind als der angestrebte Minimalweg, wie die Forscher berichten. Sie haben deshalb ein neuronales Netzwerk entwickelt, das die Kosten-Nutzen-Kalkulation auf etwas andere Weise durchführt. „Deep Cube A kombiniert Deep Learning mit klassischer Verstärkung und Wegfindemethoden“, erklären die Forscher.
Von hinten aufgezäumt
Um das Prinzip des Zauberwürfels zu lernen, beginnt Deep Cube A mit einem gelösten Würfel, der dann in sukzessive ungeordnetere, schwierigere Zustände gemischt wird. „Deep Cube A lernt so die Lösungswege, indem er vom Ziel beginnt und dann die Bewegungen zurückverfolgt“, erklären die Wissenschaftler. Nach zwei Tagen dieses Trainings ohne jeden menschlichen Input war das KI-System dann reif für die große Herausforderung.
Für den eigentlichen Test erzeugten Baldi und sein Team tausend verschiedene, zufällig erzeugte Mischungszustände des Würfels. „Zusätzlich testeten wir Deep Cube A mit den drei bekannten Zuständen, die am weitesten von der Lösung entfernt sind – 26 Züge“, so die Forscher. Sie ermittelten dann, wie schnell das KI-System die jeweiligen Aufgaben löst und wie oft es dabei den kürzestmöglichen Lösungsweg erreicht.
Kürzester Weg in 60 Prozent der Fälle
Das Ergebnis: Die künstliche Intelligenz löste den Zauberwürfel in 100 Prozent der Fälle innerhalb von Sekundenbruchteilen. Noch wichtiger aber: „Deep Cube A findet in rund 60 Prozent der Fälle den kürzesten Lösungsweg“, sagen Baldi und sein Team. Im Rest der Fälle lag der Lösungsweg nur zwei Züge über der optimalen Lösung. Die KI benötigte im Schnitt rund 20 Züge statt der 50, die die meisten Speedcuber brauchen. Gleichzeitig nutzte Deep Cube A für diese Aufgabe deutlich weniger Speicher als gängige Computersysteme, wie die Forscher berichten.
Interessant auch: „Man kann sehen, dass seine Strategie anders ist“, sagt Baldi. So entwickelte Deep Cube A deutlich häufiger symmetrische Lösungswege für symmetrische Konfigurationen des Würfels – und arbeitete so effizienter. „Meine Vermutung ist, dass dieses KI-System das Problem auf völlig andere Weise angeht als ein Mensch“, so Baldi. Ihr KI-System bewährte sich zudem ohne weiteres Training in weiteren kombinatorischen Puzzeln – es konnte das Lösungsprinzip demnach generalisieren.
Ziel ist eine flexiblere und mitdenkendere KI
Nach Ansicht der Forscher zeigt Deep Cube A damit einen Weg auf, um KI-Systeme flexibler und „mitdenkender“ zu machen. „Ein Hauptziel bei der künstlichen Intelligenz ist es, Algorithmen zu erzeugen, die verschiedene Umwelten beherrschen lernen, ohne dass sie dafür Domänen-spezifisches menschliches Wissen benötigen“, so Baldi und sein Team. „Aber wie kreieren wir eine fortgeschrittene KI, die schlauer, robuster und zum Denken, Planen und Verstehen fähig ist? Unsere Arbeit ist ein Schritt in Richtung dieses anspruchsvollen Ziels.“ (Nature Machine Intelligence, 2019; doi: 10.1038/s42256-019-0070-z)
Quelle: University of California – Irvine
