Seeing more A-star Search in action …
Obtain (re-use) copies of file graphsearch18.py and puzz8.py
Exercise 1: Implement as alternative to the given evaluation function (tiles out of place), an evaluation function that evaluates the “goodness” of a 8-puzzle state by the sum of horizontal and vertical displacements of all tiles relative to our goal state. As before, smaller evaluation function values are “better”.
Run best-first and A* search with the new evaluation function. Puzzles puzzD and puzzE are best for testing. You can also try a few of your own design. Record the results and performance of the searches.
Rerun best-first and A* with the old evaluation function. Compare the results of these run with your findings for the new evaluation function.
Can we say which evaluation function is better? Discuss.
Exercise 2: Start with the implementation of the goal function, evaluation function and successor function for another tile puzzle, the Red Donkey Puzzle.
Tile 1 is the red donkey. It wants to get out and exit through the opening on the bottom. But it is blocked by tiles 5, 7, and 8. It is also boxed in by tiles 2, 3, 4, and 6. Solve the puzzle so that the donkey can exit from the enclosure.
This a related, but in several ways, more challenging puzzle to solve. Get started and see how far you can take it. The completion of this exercise will carry over into Homework Assignment 2.
To receive credit:
Nothing to be handed in. During the lab, keep smiling (and working). Make sure you sign your name on the signup sheet.
