A* search algorithm heuristic function

Question

I am trying to find the optimal solution to a Sliding Block Puzzle of any length using the A* algorithm.

The Sliding Block Puzzle is a game with white (W) and black tiles (B) arranged in a linear game board with a single space(-). Given the initial state of the board, the game aims to arrange the tiles into a target pattern.

For example, my current state on the board is BBW-WWB and I have to achieve BBB-WWW state. Tiles can move in these ways: 1. slide into an adjacent space with a cost of 1. 2. hop over another tile into space with a cost of 1. 3. hop over 2 tiles into space with a cost of 2.

I have everything implemented, but I am not sure about the heuristic function. It computes the shortest distance (minimal cost) possible for a misplaced tile in the current state to a closest placed same color tile in goal state.

Considering the given problem for the current state BWB-W and goal state BB-WW the heuristic function gives me a result of 3. (according to minimal distance: B=0 + W=2 + B=1 + W=0). But the actual cost of reaching the goal is not 3 (moving the misplaced W => cost 1 then the misplaced B => cost 1) but 2.

My question is: should I compute the minimal distance this way and don't care about the overestimation, or should I divide it by 2? According to the ways tiles can move, one tile can for the same cost overcome twice as much(see moves 1 and 2).

I tried both versions. While the divided distance gives better final path cost to the achieved goal, it visits more nodes => takes more time than the not divided one. What is the proper way to compute it? Which one should I use?

Answer 1

The naive function you used is not admissible and therefore will not give you good performance. For A* to work properly, the heuristic used must be admissible; to be admissible, the heuristic must always give an optimistic estimate. What you can do is move 2 spaces for 1 cost. So dividing by 2 provides a best-case scenario, which will be admissible and consistent.

To learn more about Artificial Intelligence, you can join Artificial Intelligence Training in Bangalore.