This article was originally published as: A Comparative Study of A* and Greedy Best-First Search Algorithms in Solving 8-Puzzle Game
Original Article Link: Read Original Article
Download PDF: Click Here to Download PDF
Abstract
The 8-puzzle is a classic problem in the real world. It involves swapping a tile’s position with an empty slot until the goal state is reached from a given initial state in the puzzle. A search algorithm helps to solve the problem of finding the shortest path between two points or two states, as in the case of this study.
In this study, we compare the performance of two well-known search algorithms, A* and greedy best-first search, in solving the 8-puzzle game. We implemented both algorithms in Python and ran experiments on test puzzle cases to evaluate their performance. The resulting outcome shows that the A* algorithm consistently outperformed the greedy best-first search algorithm in terms of both the number of moves required to reach the goal state and the running time. For most test cases, Greedy best-search could not solve the given puzzle problem within the stipulated time limit of 2 minutes.
Authors
- Godswill Omonkhodion (Teesside Univesity, UK)
Keywords
AI, Machine learning, A*, ML Algorithm
References
- (1)Russell, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Prentice-Hall.
- (2)Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97-109.
- (3)Pillay, N. (2015) “Intelligent system design using hyper-heuristics,” South African Computer Journal, 56. Available at: https://doi.org/10.18489/sacj.v56i1.268.
- (4)Biship, C. M. (2006). Pattern Recognition and Machine Learning (1st ed.). Springer.
- (5)Bostrom, N. (2014). Superintelligence: Paths, Dangers, and Strategies. Oxford University Press.
- (6)Feigenbaum, E. A., & Feldman, J. (1963). Computers and Thought. MIT Press.
- (7) Gulshan, V., Peng, L., Coram, M., Stumpe, M. C., Wu, D., Narayanaswamy, A., … & Webster, D. R. (2016). Development and Validation of a Deep Learning Algorithm for Detection of Diabetic Retinopathy in Retinal Fundus Photographs. JAMA, 316(22), 2402-2410.
- (8) Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.
- (9) Nguyen, A., Jo, H., & Han, S. (2015). Deep learning for healthcare: review, opportunities and challenges. Briefings in Bioinformatics, 17(2), 358-377.
- (10) Shalev-Shwartz, S., Shammah, S., & Shashua, A. (2017). On the Design and Implementation of Autonomous Driving Systems. Foundations and Trends in Robotics, 6(1), 1-54.
- (11) Brown, T., Mann, G. S., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., … & Neelakantan, A. (2020). Language Models are Few-Shot Learners. arXiv preprint arXiv:2005.14165.
- (12) Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2012). ImageNet Classification with Deep Convolutional Neural Networks. In Advances in Neural Information Processing Systems (pp. 1097-1105).
- Legg, S., & Hutter, M. (2007). Universal Intelligence: A Definition of Machine Intelligence. Minds and Machines, 17(4), 391-444.
