3022jp1 This game has two types of player's tiles "Horse" (H) and "Kangaroo" (G). The player with a has two types of player's tiles Kangaroo tile starts the game from the below Initial State. A player can move any of their tile to the empty space/tile, resulting in the position swapping with the empty tile. Below defines the valid moves/swaps allowed. The Goal State below depicts the respective player's win 4/01th positions. Goal State GGG HHH 450The Initial State HGGHGH The two legal moves allowed for a player is: Wayl: A player may swap their tile with an adjacent empty location. [6+5=11 Marks] 01/06-2022jp150 Way2: A player may only hop over one tile ahead or hop over two other tiles into the empty position to swap. The static evaluation function recommended for this problem in comparison to the goal state is calculated as:2* (Total number of misplaced tiles of MAX player - Total number of misplaced tiles of MIN player) + Manhattan distance of the empty tile. 2022 (i) Expand & depict the complete game tree for up to exactly two rounds (ie., 2-ply) per player. Calculate the static evaluation values and depict in the tree. Show all the computations. (ii) Apply minimax algorithm on the game tree obtained in above part a. and list the optimal