a$.$ This problem exercises the basic concepts of game playing, using tic$-$tac$-$toe $($noughts and crosses$)$ as an example. We define$$as the number of rows, columns, or diagonals with exactly$$and no$.$ Similarly,$$is the number of rows, columns, or diagonals with just$.$ The utility function assigns$$to any position with$$and$$to any position with$.$ All other terminal positions have utility $0.$ For nonterminal positions, we use a linear evaluation function defined as$.$

$$ i$.$ Approximately how many possible games of tic$-$tac$-$toe are there?

$$ ii$.$ 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.

$$ iii.$$ Mark on your tree the evaluations of all the positions at depth $2.$

$$ iv$.$ 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.

$$ v$.$ Circle the nodes at depth $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.