Application of Reinforcement Learning to Solve Rubrik’s Cube with Markov Decision Process
DOI:
https://doi.org/10.29207/resti.v9i5.6552Keywords:
markov decision process, optimal solution, reinforcement learning, Rubik’s CubeAbstract
The Rubik's Cube is a complex puzzle with an enormous number of possible configurations, making it a challenging problem for both humans and computational methods to solve. While traditional solving algorithms rely on predefined strategies, this study explores the application of reinforcement learning (RL) to develop an adaptive and efficient solution model. This study aims to create an RL_based solver using the Markov Decision Process (MDP) framework, optimizing for speed, move efficiency, and solving steps. The proposed model employs Q-learning and Monte Carlo Tree Search (MCTS) to determine the optimal actions at each game state, which are trained through extensive Rubik's Cube simulations. The key novelty of this study lies in the integration of MCTS with Q-learning to enhance decision-making efficiency by reducing the number of moves compared with conventional methods. The experimental results demonstrate that the model achieves near-optimal solutions with fewer moves, outperforming basic rule-based approaches. Additionally, a web-based application was developed to provide real-time solving strategies based on user-input cube configurations. This study contributes to the advancement of RL applications in combinatorial puzzles and offers a practical tool for Rubik's Cube enthusiasts seeking to improve their solving techniques.
Downloads
References
K. Boyce and C. Storm, “Rubik’s Cube: What Separates the Fastest Solvers From the Rest?,” J Emerg Investig, vol. 5, pp. 1–6, Jul. 2022, doi: 10.59720/21-189.
E. S. Toshniwal and Y. Golhar, “Rubik’s Cube Solver: A Review,” in 2019 9th International Conference on Emerging Trends in Engineering and Technology - Signal and Information Processing (ICETET-SIP-19), IEEE, Nov. 2019, pp. 1–5. doi: 10.1109/ICETET-SIP-1946815.2019.9092272.
M. G. Mohanan and A. Salgoankar, “A Survey of Robotic Motion Planning in Dynamic Environments,” Rob Auton Syst, vol. 100, pp. 171–185, Feb. 2018, doi: 10.1016/j.robot.2017.10.011.
B. Muppasani, V. Pallagani, B. Srivastava, and F. Agostinelli, “On Solving the Rubik’s Cube with Domain-Independent Planners Using Standard Representations,” arXiv.org, Jul. 2023, [Online]. Available: http://arxiv.org/abs/2307.13552
M. Liu, “Introduction to Reinforcement Learning,” in Machine Learning, Animated, Boca Raton: Chapman and Hall/CRC, 2023, pp. 264–284. doi: 10.1201/b23383-14.
M. Vidyasagar, “A Tutorial Introduction to Reinforcement Learning,” SICE Journal of Control, Measurement, and System Integration, vol. 16, no. 1, pp. 172–191, Dec. 2023, doi: 10.1080/18824889.2023.2196033.
A. M. K. Adawadkar and N. Kulkarni, “Cyber-Security and Reinforcement Learning — A Brief Survey,” Eng Appl Artif Intell, vol. 114, p. 105116, Sep. 2022, doi: 10.1016/j.engappai.2022.105116.
Z. Lyu, Z. Liu, A. Khojandi, and A. Junfang Yu, “Q-learning and traditional methods on solving the pocket Rubik’s cube,” Comput Ind Eng, vol. 171, 2022, doi: 10.1016/j.cie.2022.108452.
M. E. Chasmai, “CubeTR: Learning to Solve The Rubiks Cube Using Transformers,” in ICLR 2022 Conference, Nov. 2023. doi: 10.48550/arXiv.2111.06036.
M. Zuccotto, A. Castellini, D. La Torre, L. Mola, and A. Farinelli, “Reinforcement learning applications in environmental sustainability: a review,” Artif Intell Rev, vol. 57, no. 4, p. 88, Mar. 2024, doi: 10.1007/s10462-024-10706-5.
blackburn, “Introduction to Reinforcement Learning : Markov-Decision Process,” Medium.
blackburn, “Reinforcement Learning : Markov-Decision Process (Part 2),” Medium.
R. S. Sutton and A. G. Barto, Reinforcement Learning : an Introduction, 2nd ed. Cambridge: MIT Press, 2018. Accessed: Jun. 25, 2024. [Online]. Available: https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf
H. Pan and R. Kondor, “Fourier Bases for Solving Permutation Puzzles,” Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 130, pp. 172–180, 2021.
E. Testé, “Rubik’s Cubes and Markov Chains,” Toward Data Science. Accessed: Jul. 10, 2024.[Online].Available: https://towardsdatascience.com/a-random-walk-on-the-rubiks-cube-684dd304bf3e
A. F. Mukminin, “Aplikasi Reinforcement Learning untuk Menyelesaikan Rubik’s Cube dengan Markov Desicion Process Berbasis Web,” Computer Science, Politeknik Negeri Padang, Padang, 2023.
X. Wang, Z. Yang, G. Chen, and Y. Liu, “A Reinforcement Learning Method of Solving Markov Decision Processes: An Adaptive Exploration Model Based on Temporal Difference Error,” Electronics (Basel), vol. 12, no. 19, p. 4176, Oct. 2023, doi: 10.3390/electronics12194176.
C. G. Johnson, “Solving the Rubik’s Cube with Stepwise Deep Learning,” Expert Syst, vol. 38, no. 3, May 2021, doi: 10.1111/exsy.12665.
F. Agostinelli, S. McAleer, A. Shmakov, and P. Baldi, “Solving the Rubik’s Cube with Deep Reinforcement Learning and Search,” Nat Mach Intell, vol. 1, no. 8, pp. 356–363, Jul. 2019, doi: 10.1038/s42256-019-0070-z.
Downloads
Published
Issue
Section
License
Copyright in each article belongs to the author
- The author acknowledges that the RESTI Journal (System Engineering and Information Technology) is the first publisher to publish with a license Creative Commons Attribution 4.0 International License.
- Authors can enter writing separately, arrange the non-exclusive distribution of manuscripts that have been published in this journal into other versions (eg sent to the author's institutional repository, publication in a book, etc.), by acknowledging that the manuscript has been published for the first time in the RESTI (Rekayasa Sistem dan Teknologi Informasi) journal ;





