0 votes
1 view
in AI and Deep Learning by (30.6k points)

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?

1 Answer

0 votes
by (68k points)

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.

Welcome to Intellipaat Community. Get your technical queries answered by top developers !


Categories

...