Two Robots A and B competes to leave the maze through either of exits: E 1 and E 2, as shown in the diagram. At each time step, each Robot move to an adjacent free square. Robots are not allowed to enter squares that other robots are moving into. The same exit cannot be used by both robots at once, but either robot may use either exit. A poisonous gas is left behind when a robot moves. No robot may enter the poisonous square for the duration of the gas's 1-time-step presence (ie., If the square is left free for one game round, the poison evaporates and is no longer dangerous). The poisonous squares are represented as 's in the diagram. For utility calculation consider the below assumptions. H(n)=( Max player's ability to win in the board position )-(Min player's ability to win in the board position) Note: Player "Z's" ability to win is given by below: Utility = Minimum (manhanttanDistance (Player " Z", Exit E1), manhanttanDistance(Player " Z ", Exit E2)) + Penalty Penalty = Number of unsafe cells (blockage + poisonous squares) with 4 degree of freedom(Up, Down, Right, Left) in the immediate neighborhood of the Player " Z 's" position. a. If Robot 'A' starts the play, construct game tree with utility up to level 3 or one round per player and one more round by the MAX player. b. Implement a MIN-MAX algorithm for the game tree constructed under part a. Two Robots A and B competes to leave the maze through either of exits: E 1 and E 2, as shown in the diagram. At each time step, each Robot move to an adjacent free square. Robots are not allowed to enter squares that other robots are moving into. The same exit cannot be used by both robots at once, but either robot may use either exit. A poisonous gas is left behind when a robot moves. No robot may enter the poisonous square for the duration of the gas's 1-time-step presence (ie., If the square is left free for one game round, the poison evaporates and is no longer dangerous). The poisonous squares are represented as 's in the diagram. For utility calculation consider the below assumptions. H(n)=( Max player's ability to win in the board position )-(Min player's ability to win in the board position) Note: Player "Z's" ability to win is given by below: Utility = Minimum (manhanttanDistance (Player " Z", Exit E1), manhanttanDistance(Player " Z ", Exit E2)) + Penalty Penalty = Number of unsafe cells (blockage + poisonous squares) with 4 degree of freedom(Up, Down, Right, Left) in the immediate neighborhood of the Player " Z 's" position. a. If Robot 'A' starts the play, construct game tree with utility up to level 3 or one round per player and one more round by the MAX player. b. Implement a MIN-MAX algorithm for the game tree constructed under part a
