NO implementation needed, just pseudocode theory

Goal: develop representations for games and formulate and categorize heuristics. This is a theoretical assignment and does not require implementation. 18 Puzzle Consider the 8 Puzzle and as heuristic h1 the Manhattan Distance as described in the lecture slides. h1 is admissible, because its estimated distance to the goal state falls short when it isn't exact. You are to augment the Manhattan distance to create a heuristic h2 that is more informed. You may consult https://medium.com/ swlh/looking-into-k-puzzle-heuristics-6189318eaca2 for inspiration. Task 1 1. (.2pts, Attrib 1,4) Devise a representation scheme for 8 Puzzles using only parentheses, alphanumeric characters, punctuation and (possibly nested) list structures. 2. (.5pts, Attrib 1,4) Describe your representation scheme abstractly. 3. (.2pts, Attrib 1,4) Illustrate your representation scheme by giving the input representation for 8 Puzzle Problem 1. 4. (.2pts, Attrib 1,4) Illustrate your representation scheme by giving the output representation for 8 Puzzle Problem 1. 5. (.5pts, Attrib 1,4) List the operators that generate possible successor states for each of the 9 possible positions of the blank space for any 8 Puzzle Problem. Bragging points for elegant answers. 6. (.2pts, Attrib 1,4) List the three possible successor states for the initial state of 8 Puzzle Problem 1 using your representation scheme. Task 2 1. (.5pts, Attrib 1,4) Algorithmically describe the Manhattan Distance heuristic for the 8 Puzzle using your representation scheme. 2. (.5pts, Attrib 1,4) Describe your heuristic h2, which is admissible and more informative than h1. 3. (.5pts, Attrib 1,4) Show that h2 is admissible. 4. (.5pts, Attrib 1,4) Show that h2 is more informative than h1. Figure 1: 8 Puzzle Problem 1 initial and goal state