Heuristic pathfinding for the N-puzzle with neural networks

/Module/Year-5

The 15-puzzle is a very common puzzle game involving the sliding of tiles to reach a goal state. The 15-puzzle can be solved by using a pathfinding algorithm as you are finding a "path" to the goal state. I used A* which requires a heuristic to predict the number of moves to solve a given state. I used AI as the heuristic which learns from previously scrambled states with known path lengths. After training the model, I found that the Neural network was 16 times more efficient than one of the best man-made heuristics in terms of explored states.