1.a) Consider the problem of finding a path in the grid shown below from the position S to the position G. The agent can move on the grid horizontally and vertically, one square at a time (each step has a cost of one). No step may be made into a forbidden crossed area. In the case of ties, break it using up, left, right, and down. i) Draw the search tree in a greedy search. Manhattan distance should be used as the heuristic function. That is, h(n) for any node n is the Manhattan distance from n to G. The Manhattan distance between two points is the distance in the x-direction plus the distance in the y-direction. It corresponds to the distance traveled along city streets arranged in a grid. For example, the Manhattan distance between G and S is 4. What is the path that is found by the greedy search? ii) Draw the search tree in an A* search. Manhattan distance should be used as the 1 heuristic function. What is the path that is found by the A* search? G S b) Consider the following game tree in which the static scores are all from the first player's point of view: i) Suppose the first player is the maximizing player. What move should be chosen? ii) What nodes would not need to be examined using the alpha-beta pruning procedure? ¡¡¡) Suppose now the first player is the minimizing player. What move should be chosen? iv) What nodes would not need to be examined using the alpha-beta pruning procedure?

1.a) Consider the problem of finding a path in the grid shown below from the position S to the position G. The agent can move on the grid horizontally and vertically, one square at a time (each step has a cost of one). No step may be made into a forbidden crossed area. In the case of ties, break it using up, left, right, and down. i) Draw the search tree in a greedy search. Manhattan distance should be used as the heuristic function. That is, h(n) for any node n is the Manhattan distance from n to G. The Manhattan distance between two points is the distance in the x-direction plus the distance in the y-direction. It corresponds to the distance traveled along city streets arranged in a grid. For example, the Manhattan distance between G and S is 4. What is the path that is found by the greedy search? ii) Draw the search tree in an A* search. Manhattan distance should be used as the 1 heuristic function. What is the path that is found by the A* search? G S b) Consider the following game tree in which the static scores are all from the first player's point of view: i) Suppose the first player is the maximizing player. What move should be chosen? ii) What nodes would not need to be examined using the alpha-beta pruning procedure? ¡¡¡) Suppose now the first player is the minimizing player. What move should be chosen? iv) What nodes would not need to be examined using the alpha-beta pruning procedure?