$(15$ pts$)$ Consider a tic$-$tac$-$toe game $(33$ grids$).$ We define $x_n$ as the number of rows,

columns, or diagonals with exactly $nx\text{'}$s and no $O^{\text{'}}\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 position with $x_3$

$=1$ and $-1$ to any position 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))).$

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 $($i$.$e$.,$ at depth $1,$ there are only

three states$).$

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

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 highlight the best starting move.