This problem exercises the basic concepts of game-playing using tic-tac-toe (noughts and crosses) as an example. we define x[n] as the number of rows, columns, or diagonals with exactly n x's and no o's. similarly, o[n] is the number of rows, columns, or diagonals with just n o's. the utility function thus assigns +1 to any position with x[3], = 1 and —1 to any position with o[3], - 1.all other terminal positions have utility 0. we will use a linear evaluation function defined as eval = 3*x[2] + x[1] - (3*o[2] + o[1])approximately how many possible games of tic-tac-toe are there? 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. you should have 3 positions at level 1 and 12 at level 2.mark on your tree the evaluations of all the positions at level 2.mark on your tree the backed-up values for the positions at levels 1 and 0, using the minimax algorithm, and use them to choose the best starting move. circle the nodes at level 2 that would not be evaluated if alpha-beta pruning were applied, assuming the nodes are generated in the optimal order for alpha-beta pruning.