TASK $4(20$ points$)$

Figure $1.$ A tic$-$tac$-$toe board state.

Consider the tic$-$tac$-$toe board state shown in Figure $1.$ Draw the full minimax search tree starting from this state, and ending in terminal nodes. Show the utility value for each terminal and nonterminal node. Also, show which move the Minimax algorithm decides to play for X$.$ Utility values are $+1$ if $\backslash ($ X $\backslash )$ wins, $0$ for a tie, and $-1$ if $\backslash ($ O $\backslash )$ wins. $($Note: $\backslash ($ X $\backslash )$ is the MAX player$).$