- Titel
- Solving general Twisty Puzzles with Reinforcement Learning and automatic Algorithm Generation
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-949917
- Erstveröffentlichung
- 2025
- Datum der Einreichung
- 01.12.2024
- Datum der Verteidigung
- 19.12.2024
- Abstract (EN)
- The Rubik's Cube and hundreds of twisty puzzles that were made afterwards have challenged millions of people around the world for decades. Coming up with new solution strategies for a twisty puzzle can be very difficult and often takes even experienced humans many hours. Recently, Machine Learning has been used to find new solutions to such puzzles with little to no human knowledge required. But these solutions are difficult for humans to replicate as there is little obvious structure. We propose a method to automatically generate algorithms for puzzles and use them to augment the action set of reinforcement learning agents. The augmented action set enables learning with an intuitive, dense reward function and the resulting agents learn more interpretable solution strategies while using significantly less compute than previous methods to solve the Rubik's Cube.
- Freie Schlagwörter (EN)
- reinforcement learning, machine learning, Rubik's Cube, AI interpretability
- Klassifikation (DDC)
- 006
- 620
- 510
- Klassifikation (RVK)
- ST 300
- ST 134
- GutachterIn
- Prof. Dr. Ostap Okhrin
- Prof. Dr. Pascal Kerschke
- Ankit Anil Chaudhari
- Den akademischen Grad verleihende / prüfende Institution
- Technische Universität Dresden, Dresden
- Version / Begutachtungsstatus
- aktualisierte Version
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-949917
- Veröffentlichungsdatum Qucosa
- 02.01.2025
- Dokumenttyp
- Masterarbeit / Staatsexamensarbeit
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY-NC-SA 4.0- Inhaltsverzeichnis
1 Introduction and motivation 1 1.1 Related work 3 1.2 Mathematical Foundation 4 1.2.1 Permutations 4 1.2.2 Modeling Twisty Puzzles 4 1.2.3 Group Properties of non-bandaged Twisty Puzzles 6 2 Algorithm generation 7 2.1 Automatic Symmetry Detection 8 2.2 Automatic Piece Detection 11 2.3 Algorithm Generation 14 2.4 Reinforcement Learning 18 3 Experiments and Results 21 3.1 Experiment Description 22 3.1.1 Research Questions 22 3.1.2 Investigated Puzzles 22 3.2 Results and Discussion 27 3.2.1 Training behavior 27 3.2.2 Training Time Scaling with State Space Size 28 3.2.3 Policy Analysis 30 3.2.4 Limitations 39 3.3 Further questions 40 3.4 Conclusion 42 A Compute Hardware & training time 47 B Alternative Symmetry Detection 49