Research Article Open Access

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

Wahyu Hidayat1, Fitri Susanti1 and Dedy Rahman Wijaya1
  • 1 Telkom University, Indonesia

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.

Journal of Computer Science
Volume 17 No. 11, 2021, 1147-1156

DOI: https://doi.org/10.3844/jcssp.2021.1147.1156

Submitted On: 24 June 2021 Published On: 3 December 2021

How to Cite: Hidayat, W., Susanti, F. & Wijaya, D. R. (2021). A Comparative Study of Informed and Uninformed Search Algorithm to Solve Eight-Puzzle Problem. Journal of Computer Science, 17(11), 1147-1156. https://doi.org/10.3844/jcssp.2021.1147.1156

  • 2,679 Views
  • 3,538 Downloads
  • 3 Citations

Download

Keywords

  • Comparative Study
  • Uninformed Search
  • Informed Search
  • Heuristic
  • 8-Puzzle Game