Der DeepCube-Solver-Ansatz könnte über den Würfel hinaus in andere Forschungen gehen

Eine Illustration von DeepCube. Der Trainings- und Lösungsprozess ist in ADI und MCTS aufgeteilt. Zuerst trainieren wir ein DNN iterativ, indem wir den wahren Wert der Eingabezustände mithilfe der Breitensuche schätzen. Dann verwenden wir das DNN, um die Erkundung zu leiten, und lösen Würfel mithilfe der Monte-Carlo-Baumsuche. Bildnachweis: arXiv:1805.07470 [cs.AI]

Wie kann eine Maschine den Zauberwürfel lösen? Zahlreiche Teams können aufstehen und sagen, dort gewesen, fertig. Wir haben auch viele Schlagzeilen darüber gesehen, wie sie sich eingeloggt haben, um Zeitrekorde aufzustellen. Was ist also das Große an der neuesten Machine-solving-Cube-Geschichte?

David Grossmann in Beliebte Mechanik bemerkten, dass die kalifornischen Wissenschaftler die Dinge mit einem Algorithmus in die dritte Dimension gebracht haben, der herausfinden kann, wie man einen Zauberwürfel löst.

Hinter einem Ansatz, der besondere Aufmerksamkeit erregte, steht ein Team der University of California Irvine. “Solving the Rubik’s Cube Without Human Knowledge” ist der Titel ihres Papers, das ihre Erforschung beschreibt, und das Paper ist auf arXiv.

Stephen McAleer, Forest Agostinelli, Alexander Shmakov und Pierre Baldi sind die Autoren.

“Wir stellen Autodidaktische Iteration vor: einen neuartigen Reinforcement-Learning-Algorithmus, der sich selbst beibringen kann, wie man den Zauberwürfel ohne menschliche Hilfe löst.”

Paul Lilly in HotHardware: Maschinen verwenden normalerweise eine selbstlernende Methode, die auf einem Belohnungssystem basiert. Forscher füttern die Maschine mit den Spielregeln, und dann verwendet sie einen Belohnungsprozess, um festzustellen, ob ein Zug gut oder schlecht war.

Wie die Autoren jedoch schrieben, “sind die Belohnungen für viele kombinatorische Optimierungsumgebungen spärlich und die Beendigung von Episoden ist nicht garantiert.”

Sie nahmen den Weg der Autodidaktischen Iteration. Sie sagten: „Um den Zauberwürfel mithilfe von Reinforcement Learning zu lösen, lernt der Algorithmus eine Richtlinie. Die Richtlinie bestimmt, welche Bewegung in einem bestimmten Zustand erfolgen soll.“

MIT-Technologie-Überprüfung festgehalten, wie es funktioniert. „Bei einem ungelösten Würfel muss die Maschine entscheiden, ob ein bestimmter Zug eine Verbesserung der bestehenden Konfiguration darstellt. Dazu muss sie in der Lage sein, den Zug auszuwerten. Die autodidaktische Iteration tut dies, indem sie mit dem fertigen Würfel beginnt und rückwärts arbeitet, um zu finden eine Konfiguration, die dem vorgeschlagenen Umzug ähnlich ist.”

Die Autoren schrieben, dass “DeepCube während seines Trainingsprozesses eine bemerkenswerte Menge an Rubik’s Cube-Wissen entdeckt hat, einschließlich des Wissens darüber, wie komplexe Permutationsgruppen und Strategien verwendet werden, die den besten menschlichen ‘Speed-Cubers’ ähneln.”

Ihre Trainingsmaschine war ein 32-Core Intel Xeon E5-2620 Server mit drei NVIDIA Titan XP GPUs. Sie nannten ihren Solver DeepCube.

Lillys Einschätzung: Es ist keine perfekte Lösung des Problems, aber in puncto Genauigkeit einwandfrei.

Das Team erklärte in der Zusammenfassung des Papiers: “Unser Algorithmus ist in der Lage, 100 % der zufällig verwürfelten Würfel zu lösen und dabei eine durchschnittliche Lösungslänge von 30 Zügen zu erreichen, die größer oder gleich der von Solvern ist, die menschliches Domänenwissen verwenden.”

Warum das so wichtig ist: Es ist eine Geschichte, die Würfel löst und mehr. Das Team erwähnte zusätzliche Tore.

„Neben der weiteren Arbeit mit dem Rubik’s Cube arbeiten wir daran, diese Methode zu erweitern, um Näherungslösungen für andere kombinatorische Optimierungsprobleme wie die Vorhersage der Proteintertiärstruktur zu finden. Viele kombinatorische Optimierungsprobleme können als sequentielle Entscheidungsfindungsprobleme betrachtet werden wir können Reinforcement Learning einsetzen.”

MIT-Technologie-Überprüfung sagte, dass der neue Ansatz “ein wichtiges Problem in der Informatik angeht, um komplexe Probleme zu lösen, wenn die Hilfe minimal ist.”

Im Idealfall, so Lilly, “könnte es Heilmittel für Krankheiten finden, wenn die Methode bei solchen Dingen genauso gut funktioniert wie beim Lösen eines Zauberwürfels.”

MIT-Technologie-Überprüfung: “Der eigentliche Test wird natürlich sein, wie dieser Ansatz komplexere Probleme wie die Proteinfaltung bewältigt. Wir werden sehen, wie er funktioniert.”


Leave a Comment