Consider a scenario where a Tic-Tac-Toe game is being played on a 3X3 board using the MiniMax algorithm. a) Formulate the Tic-Tac-Toe game problem in terms of 6 game elements described on page 147 of your textbook (Note: all the game elements must be described specific to Tic-Tac-Toe game only) (7 points) b) Draw and label a simple game search tree for Tic-Tac-Toe, considering possible moves and their corresponding outcomes for both players. (10 points) a. Game search tree should start from an initial state and end to a leaf node when the game ends. b. Assign a utility value to each node and label each node with Player who will play next. C. Use the MiniMax algorithm to determine the optimal move for the maximizing player (X) at each level of the tree. c) How many terminal nodes are possible for the Tic-Tac-Toe game (3 points)

Fig: 1