2. Informed Search We have the following computer game scenario that is played in a maze (see figure below). The maze is represented by the grey squares connected horizontally or vertically on a 2D grid. A human player places a cake on a square inside the maze that remains there during the game (black circle). A computer player controls the Wumpus (red polygon) that always starts from the same square. The wumpus can move horizontally or vertically to an adjacent square, and sees the complete maze including the cake. The goal of the computer player is to move the Wumpus to the location of the cake within a minimum number of moves. The human player receives one point for each move the wumpus makes, and tries to maximize the total score. a) Formulate this problem as a single-state search problem. Describe how the A* algorithm would find a path from the Wumpus's start position to the position of the cake. Also, specify an admissible heuristic for the A* algorithm and show that your heuristic is admissible. Does the greedy best-first search algorithm with an admissible heuristic, in general, find a better path for the Wumpus than the A* algorithm? c) 2. Informed Search We have the following computer game scenario that is played in a maze (see figure below). The maze is represented by the grey squares connected horizontally or vertically on a 2D grid. A human player places a cake on a square inside the maze that remains there during the game (black circle). A computer player controls the Wumpus (red polygon) that always starts from the same square. The wumpus can move horizontally or vertically to an adjacent square, and sees the complete maze including the cake. The goal of the computer player is to move the Wumpus to the location of the cake within a minimum number of moves. The human player receives one point for each move the wumpus makes, and tries to maximize the total score. a) Formulate this problem as a single-state search problem. Describe how the A* algorithm would find a path from the Wumpus's start position to the position of the cake. Also, specify an admissible heuristic for the A* algorithm and show that your heuristic is admissible. Does the greedy best-first search algorithm with an admissible heuristic, in general, find a better path for the Wumpus than the A* algorithm? c)