Simply Logical lab exercises chapter 6

The assignment deals with heuristic search and the 8-puzzle.

The well-known 8-puzzle consists of 8 tiles and an empty space, organised in a square. A move consists in sliding a tile to the empty space, or equivalently, moving the empty space horizontally or vertically. Each move has equal cost. The objective is to reach the following position:

   1 2 3
   8   4
   7 6 5

The file labs6.pl contains a program for solving the 8-puzzle from an arbitrary starting position. The query puzzle(C,N) will return the cost of the found solution (the number of moves) and the number of nodes searched. During the search it prints the f-value of the current node taken from the front of the agenda. By typing ; after a solution has been found, you can backtrack over different starting positions specified by start_p.

- Analyse the search space in terms of number of different board positions and branching factor. Estimate the number of nodes at depth 20. What does this tell you about the occurrence of duplicates in the search space?
- The given algorithm is an A algorithm, i.e. it combines an estimate h of the distance to a goal with the cost g of the current partial solution. What happens if g is not taken into account? Demonstrate this on one of the given starting positions.
Adapt the predicate merge such that it only adds a node to the agenda if it does not already contain the same node with a lower f-value.
- Does this affect the ability of the program to find optimal solutions?
- Demonstrate the increased efficiency of the search.
The predicate eval_p evaluates a board position in terms of its overall Manhattan distance to the goal by using totdist. This heuristic is not always very effective. Improve it by adding the result of the predicate insequence, which punishes tiles that are not followed in clockwise direction by their successor.
- Demonstrate the increased efficiency of the search on a starting position of your choice.
- Demonstrate that the new heuristic is not optimistic by showing that it does not always return an optimal solution.
- What does it mean when the printed evaluation of the current node is lower than the previous one?
Make the search algorithm non-exhaustive by limiting the agenda to a fixed size. Demonstrate and discuss the effect this has on the ability of the program to find (optimal) solutions.

Back / Peter Flach