Enhancing A* Search Efficiency: Machine Learning-Driven Heuristic Optimization for the 8 Puzzle Problem

The 8-puzzle problem is a well-known puzzle that has always been used to eval- uate different search algorithms in artificial intelligence (AI). The most favorite search algorithm for solving this problem is the A* search algorithm which re- lies on heuristics such as Manhattan distance to guide the search. However, the effectiveness of A* heavily depends on the quality of the heuristic function, which impacts both the number of expanded nodes and the time taken to find the optimal solution. This thesis explores integrating machine learning methods to improve the heuristic function for A* search in the 8-puzzle problem. A dataset of all solv- able puzzle states and their corresponding solution lengths was generated, and several machine learning models, including Linear Regression, Random For- est, and XGBoost, were trained to predict the solution length for a given input state. Features such as Manhattan distance, misplaced tiles, and row/column correctness were used to capture the essential properties of each puzzle state. The performance of the learned heuristic was integrated into the A* search algorithm and then compared against the traditional Manhattan distance heuris- tic. Results indicate that the learned heuristics, particularly those based on the XGBoost model, significantly reduced the number of the expanded nodes dur- ing the search, achieving optimal solutions while maintaining reasonable search times. The XGBoost model tuned using Grid search, expanded only 127 nodes on average, compared to 273 nodes for traditional heuristics, and demonstrated a promising balance between search efficiency and solution optimality. This thesis demonstrates the potential of machine learning to enhance search algorithms by learning effective heuristics, offering a viable alternative to hand- crafted heuristics like Manhattan distance. The findings suggest further avenues for optimization, including hybrid heuristics and neural network-based models for more complex search problems.