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])

1. Approximately how many possible games of Tic-Tac-Toe are there?
2. 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.
3. Mark on your tree the evaluations of all the positions at level 2.
4. 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.
5. 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.