DRAW THIS TREE: Consider a tic$-$tac$-$toe game $(3$x$3$ grids$).$ We define Xn as the number of rows, columns, or diagonals with exactly n X$$s and no O$$s$.$ Similarly, On is the number of rows, columns, or diagonals with just n O$$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$)=3$X$2($s$)+$ X$1($s$)(3$O$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.