1) This problem exercises the basic concepts of game playing, using tic-tac-toe as an example. We define X, as the number of rows. columns, or diagonals with exactly n X's and no O's. Similarly o, is the number of rows, columns, or diagonals with just n O's. The utility function assigns +1 to any position with x3 = 1 and -1 to any position with o, = 1. All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as: Eval(s) = 3x2 (s) + X: (s) - (302 (3) + 01 (3)) For instance, the example state given below would have Eval = 2 because there are two diagonals and one row with 1 X and no O's, and only one row with 1 0 and no X's. + 0 X a) Show the whole game tree starting from an empty board down to depth 2 (i.e., one X and one o on the board), taking symmetry into account. b) Mark on your tree the evaluations of all the positions at depth 2. c) Using the minimax algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those values to choose the best starting move