I am currently implementing a solver for Rush Hour (a very interesting sliding puzzle) using A*. I’m testing the whole thing with a database that contains all the game configurations, and thanks to various optimizations I can now solve the most difficult configuration in under 3s, which is pretty cool.
However, none of my four heuristics manage to find minimal solutions in all 225 configurations that are of interest to me (I ignore the game boards with obstacles), so I assume that the heuristics I use are not valid and consistent, but firstly I don’t know why and secondly I can’t think of a more useful heuristic.
Here are the heuristics I use:
- Count number of fields between the red car and the exit
- The performance is not too good compared to other approaches, the performance as well as the results (= how many solutions found are minimal) are poor
- Consistency: The heuristic decreases or stays the same as you make progress toward the goal.
- Admissibility: Maybe here ist the problem? It should not overestimate the true number of moves needed, but if I count the fields, the sum could be higher than the moves I need to solve the puzzle.
- Count blocking cars between the red car and the exit and penalize the cars that can’t move
- Great performance
- Consistency/Admissibility: I guess using a constant penalty of 5 per car can cause some problems here?
- Count blocking cars starting from cars between the red car and the exit recursively
- Best performance and best results
- Consistency: I thought this heuristic is consistent because the number of blocking cars will decrease or remain the same as the state progresses toward the goal.
- Admissibility: It only counts the cars and not the moves, so I guess overestimation is no problem.
Based on all my considerations and attempts, I am somewhat at a loss as to how to create a reasonable heuristic that firstly always finds the minimal solutions and secondly is efficient enough to maintain the runtimes.
1