BE C A D H a) Initial State AB C DIEF G H (b) Goal State Figure 1: Eight Puzzle Game [2 pts]. Figure 1 lists the initial state and the goal state of Eight Puzzle game (with eight letter-tiles and one empty tile, i.e., the white tile). Please use A* search to build a search tree to carry out search from the initial state to the goal state. 3. a. Please use number of misplaced letter-titles as the heuristic finction and report the search tree from the initial nodes to the goal node (please include the evaluation function values f(N), g(N), and h(N) for each node). b. Please use Manhattan distance between each letter-tile and its goal position as the heuristic function, and report the search tree from the initial nodes to the goal node (please include the evaluation function values fN), gN), and h(N) for each node) BE C A D H a) Initial State AB C DIEF G H (b) Goal State Figure 1: Eight Puzzle Game [2 pts]. Figure 1 lists the initial state and the goal state of Eight Puzzle game (with eight letter-tiles and one empty tile, i.e., the white tile). Please use A* search to build a search tree to carry out search from the initial state to the goal state. 3. a. Please use number of misplaced letter-titles as the heuristic finction and report the search tree from the initial nodes to the goal node (please include the evaluation function values f(N), g(N), and h(N) for each node). b. Please use Manhattan distance between each letter-tile and its goal position as the heuristic function, and report the search tree from the initial nodes to the goal node (please include the evaluation function values fN), gN), and h(N) for each node)