Please do it on paper:

You are given the state of a Tic$-$Tac$-$Toe game represented as follows:

The game is played on a $33$ board. $\text{'}$X$\text{'}$ represents Player $1,$ and $\text{'}$O$\text{'}$ represents Player $2.$ An empty cell is represented by

a space.

a$)$ Draw the initial game state and expand the game tree by considering all possible moves for both Player $1(\text{'}$X$\text{'})$ and

Player $2(\text{'}$O$\text{'}).$ Assign utility values to the terminal states $($Player $1$ wins $[+1],$ Player $1$ loses $[-1],$ or draw $[0]).$

b$)$ Use the minimax algorithm to propagate values up the tree, assuming that both players play optimally.

c$)$ What is the best move for Player $2(\text{'}$O$\text{'})$ based on the minimax values at the root of the tree. Provide the final game

tree with minimax values and indicate the best move for Player $2$