Small PacMan Maze: In the map below, the pacman and the ghost can move to any adjacent squares (the action space is {U,D,R,L} ). The pacman and the ghost can move in any direction if there is no wall on the way and the solid lines represent the wall. The movement of the ghost is random. Pacman starts first and alternates turns with the ghost. The game starts in the shown figure, and it ends in either one of the two cases. Note that pacman and the ghost cannot move in the direction of a wall (for example, in the start state shown, pacman cannot move 'down' or 'left'; the only valid actions are 'up' or 'right'). - Winning: Pacman (maximizer) eats all the dots. - Losing: The ghost catches the pacman. Pacman will receive the score of +1 for eating a dot and a penalty score of 2 if it is caught by the ghost. The final score of the pacman is calculated as the number of dots eaten by the pacman and the penalty if the ghost caught the pacman. A) Draw the expectimax search tree for the first four total turns (pacman moves first, then the ghost, then pacman again, and finally the ghost). The ghost moves horizontally with probability of q and it moves vertically with probability of 1-q. Use the letter ' P ' for pacman and ' G ' for ghost when drawing game states. On the tree please distinguish the max-nodes, terminal nodes and the expectation nodes. Note that each of the pacman or the ghost's movements counts as the turn. You don't need to expand the whole tree; you can calculate the values of non-terminal states at depth 4 . (5 points) B) Calculate the expected score of Pacman if it plays optimally for q=1/3. Hint: the tree can be infinitely large, but you don't need to expand the whole tree in order to compute this expected score -- Pacman will get a score of +2 for eating both dots and winning the game. (5 points) C) Explain in plain English what Pacman's strategy should be (2 points)