This problem exercises the basic concepts of game playing, using tic$-$tac$-$toe as an example. We

define $x_n$ as the number of rows, columns, or diagonals with exactly $nx\text{'}$s and no O$\text{'}$s$.$ Similarly $O_n$ is

the number of rows, columns, or diagonals with just $n$ O$\text{'}$s$.$ The utility function assigns $+1$ to any

terminal position with $x_3=1$ and $-1$ to any with $O_3=1.$ All other terminal positions have utility

$0.$ For nonterminal positions, we use a linear evaluation function defined as:

Eval$(s)=3x_2(s)+x_1(s)-(3O_2((s))+O_1((s)))$

For instance, the example state given below would have Eval $=2$ because there are two diagonals

and one row with $1x$ and no O$\text{'}$s$,$ and only one row with $1O$ and no X$\text{'}$s$.$

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. Assume that $x$ goes first.

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.