French University in EgyptExercisesAnswer the Following Question:Q.1)Suppose that an agent is in 3x3 maze environment like the one shown in the following figure. The agent knows that its initial location is (1, 1), that the goal is at (3,3), and that the four action Up, Down, Left, Right have their usual effects unless blocked by a wall. The agent does not know where internal walls are. In any given state, the agent perceives the set of legal actions; it can also tell whether the state is one it has visited before or a new state.3 G21 S 1 2 3a. Define an appropriate state space, and propose a heuristic function, if it is possible.b. Apply suitable search technique on the created search space.================Q.2)Consider the following simple game tree showing the utility (or heuristic evaluation) of each of the leaves. Assume alpha-beta search is used to pick the bestmove for Max at the top level and that siblings are explored in left to right order. Circle each leaf node that is actually evaluated and show each updated bound and exact value established for the utility of any intermediate nodes. Number each stepin order. What is the best move for Max (left or right)?================Q.3) a. Consider the following search problem. Assume a state is represented as an integer,that the initial state is the number 1, and that the two successors of a state n are theArtificial Intelligence Prof. Magdy Aboul-Ela - Exercises 1/3French University in Egyptstates 2n and 2n + 1 (in this order). For example, the successors of 1 are 2 and 3, the successors of 2 are 4 and 5, the successors of 3 are 6 and 7, etc. Assume the goal state is the number 12 Consider the following heuristics for evaluating the state n where the goal state is g• h1(n) = |n − g| (the absolute value of the difference)• h2(n) = (g − n) if n< g, and h2(n) = 1 otherwise (n > g)Show the search trees generated for each of the following strategies for the initial state 1 and the goal state 12, numbering the nodes in the order expanded. Assume goal states are detected as soon as they are generated instead of waiting until they are expanded.(a) Depth-first search(b) Breadth-first search(c) Best-first with heuristic h1(d) Best-first with heuristic h2(e) Hill-climbing with heuristic h1If any of these strategies get lost on an infinite path and never find the goal, simply show the search tree for a few steps and then say “FAILS.”==============Artificial Intelligence Prof. Magdy Aboul-Ela - Exercises 2/3French University in EgyptQ.4) Consider the Fox and Goose problem: FoxGooseFoxGoal: - Goose in column 4 (HOME)Rules: - If fox next to goose and foxes turn, then fox can eat goose- Fox/goose can move diagonal as well as vertical/horizontal. - Only ONE fox can move each turn.- Fox can’t move to last column, Obstacle to reduce movement.i. Define an appropriate state space, and propose a heuristic function.ii. Apply a search technique to find a solution path.*****Good LuckProf. Magdy Aboul-Ela Artificial Intelligence Prof. Magdy Aboul-Ela - Exercises