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
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
- 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
/ Peter Flach