Informed Search Maze html: https://drive.google.com/drive/folders/1BvKrLniVCS4YpBHtfiHckHLGnRMnOU_m?usp=sharing

8. [1 pt + 1 Extra credit] The "Informed Search to Play Maze [Notebook, html]" posted on Canvas shows a Maze game using A-Star Search (AStar), Greedy Best First (GBF) and Uniform Cost Search (UCS) (using "AStar", "GBF", or "UCS" as parameters). Use Notebook as the skeleton code, validate and compare following settings and results. a. Using Figure 7 as the game field, and set initial state as [0,0] and goal state as [9,9]. Use A-Star Search (AStar), Greedy Best First (GBF) and Uniform Cost Search (UCS) to find path from initial state to goal state, respectively. Report path of each method [0.25pt], and explain which method is optimalot optimal, why? [0.25pt]. b. What is advantage of AStar search, comparing to greedy best first search (GBF) and Uniform Cost Search [0.25 pt] c. What is advantage of Greedy Best First search, comparing to A-Star search (AStar) and Uniform Cost Search [0.25pt] d. Bonus Question [1 extra credit|. Based on the randomly generated board in the program, revise the code to visually show generated nodes (color nodes in blue), expanded nodes (color nodes in brown), and the final discovered path from source to the goal node (color path in red). Your program should show a GUI interface of the board layout and the path, nodes etc. (an example is shown in Figure 8). i. You must submit a notebook of the extra credit question (in html or pdf format) for grading. ii. No credit if screenshot is submitted. iii. Solutions CAN NOT use API calls (or a third party tool) to solve a search problem. Figure 7 Figure 8: An example of GUI interface (for extra credit) showing path, generated nodes, and expanded nodes