A Comparative Study of Informed and Uninformed Search Algorithm to Solve Eight-Puzzle Problem

Abstract

Problems in artificial intelligence can be solved using intelligent tracking methods through intelligent search mechanisms. Understandably, search algorithm performances are highly dependent on the problem solved. In this study, we evaluate and compare the performance of five uninformed and informed search (breadth-first search, depth first search, optimal search and best first search using two heuristic functions, namely mismatched tile and Manhattan distance) algorithms to solve the eight-puzzle game problem. For each algorithm, the numbers of raised and explored nodes were assessed and analyzed. Our experiment demonstrates that informed search with heuristic outperforms uninformed search significantly, both in terms of memory usage efficiency and computational power efficiency. On average, the informed search using heuristic requires only 5.33% of memory used by uninformed search and only 4.45% of computational power demanded by uninformed search. Boxplot analysis also confirms that informed search using heuristic also delivers more stable performance contrasted to uninformed search. These could be a concern for researchers and game developers to consider implementing the heuristically enhanced search algorithm to utilize memory and computational power efficiently to solve similar problems.