Problem 5. Evaluation Function [20 Points] The Game of Hex was invented by John Nash in the 1940s. Hex consists of a rhombus game map divided into nn hexagons. Each player in a 2-player game has a marker (Blue and red). At each round a player can place a marker on an unmarked hexagon, and players alternate turns. The goal for the players is to link their opposite sides of the board in an unbroken chain. Whoever connects their sides first wins and receives +1 point and the opponent receives 1. It has been proven that a draw is impossible in Hex, hence there's always a winner. A) Players can play optimally using a minimax algorithm. Why is expanding the whole game tree not practical? What are the things that we need to consider when we design the evaluation function so we can evaluate different stages of this game? (7 points) B) Define an evaluation function that approximates the value of each state. ( 7 points) C) If the size of the game is nn and each time the agent considers the next three moves (agents' move, minimizers' response, agents' subsequent move). What is the Big- time cost of the initial action? ( 6 points)