[3+2+4=9 Marks In this single player game, the Pacman Agent aims to efficiently reach the "Exit" in the shortest way possible, after eating atleast one Red food pellet and one Green food pellet (though Pacman may eat more than one of each food pellets in its path). Pacman has four actions: moveNorth, moveSouth, moveWest, or moveEast and it does not have a "stay" action. Each action incurs a cost of +2 for the agent. In addition to this, if an agent eats a red pellet and green pellet it incurs a cost of +5 and +3 respectively. In below fixed board configuration of dimension NM, there are 3 red pellets and 6 green pellets. a. Depict the search tree for up to exactly three levels ie., level 3. (Given initial state can be assumed to be on level-0.) with calculated path cost shown in the diagram neatly b. Compute the heuristic value for each state and check the admissibility and consistency for any three generated states. Heuristics is given by, H(n)=2(Manhattandistance(PacmanAgent,Exit)) c. Implement the A algorithm only for the first 4 closed list updates. Show the status of OPEN and CLOSE list at each level