Two players are playing a modified tic-tac-toe game in which grid spaces have point values, shown on the left grid below. The players take turns marking a grid space with their own designation (X or O) until either one player gets three marks in a row or the board has no empty spaces. When the game ends, a score is computed as the sum of the values of the X spaces minus the sum of the values of the O spaces. In addition, if X has three in a row, 3 points are added to the score; if O has three in a row, 3 points are subtracted from the score. X seeks to maximize the total score and O seeks to minimize it. 2 5 2 X 5 1 5 X O 2 5 2 0 0 X (a) The right grid shows the current board configuration, whose current value is -3. It is X's turn to move. Draw out the entire game tree with the root corresponding to the current board. Use game tree convention to draw the MAX and MIN nodes. Also sketch out the tic-tac-toe board configuration for each terminal node (e.g., draw them right below each node). (b) Compute the minimax values of each node. What is the best move for X to make, and what is the expected score of the game assuming both players play optimally? (c) Suppose we are performing alpha-beta search. In what order would the successors of the root node have to be processed in order to maximize the number of nodes that can be pruned? Identify the node(s) in the game tree that can be pruned, and find the a, 3, and v values of the parent node right before pruning occurs. (d) Suppose that instead of playing to minimize the score, player O chooses a random valid move with uniform probability. Explain how the game tree will change (you do not have to redraw it), and compute the new utility and best move for X starting from the current state.