Exercise $1(30$ points$).$ Consider the following variation of tic$-$tac$-$toe. The board has $\backslash (1\backslash$times $4\backslash )$ cells and there are two players that alternate placing one piece at a time on the board. One player has pieces of the form $\backslash (\backslash$times $\backslash )$ and the other of the form $\backslash (\backslash$circ $\backslash ).$ Whenever a player has two consecutive pieces on the board it wins; if the board fills without consecutive pieces, the game is a tie. Player $\backslash (\backslash$times $\backslash )$ starts. Assume terminal game values of $\backslash (-1/+1/0\backslash )$ for loss$/$win$/$tie for the starting player. An example game: $\backslash (\backslash$rightarrow $\backslash )\backslash (\backslash$rightarrow $\backslash )$ player $\backslash (\backslash$times $\backslash )$ wins.

$1.(10$ points$)$ Solve this game by constructing its complete minimax tree. Draw the tree as in fig. $5\mathrm{.}1.$ Give the optimal value $\backslash ($ v$^\{*\}\backslash )$ at the root, and the corresponding move$($s$).$

$2.(2$ points$)$ Explain how a real game would develop, i$.$e$.,$ give the move sequence that would happen according to your tree.