questions $3,4,5$

Exercise $1(30$ points$).$ Consider the following variation of tic$-$tac$-$toe. The board has $1$xx$4$ cells and there are two

players that alternate placing one piece at a time on the board. One player has pieces of the form xx and the other of the

form @$.$ 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 xx starts. Assume terminal game values of $-1//+1//0$ for loss$/$win$/$tie for the starting player. An

example game: $|$rarr$|$xx$|$@$|$rarr xx$|$xx$|$@rarr player xx wins.

$(10$ points$)$ Solve this game by constructing its complete minimax tree. Draw the tree as in fig. $5\mathrm{.}1.$ Give the optimal

value v$^(**)$ at the root, and the corresponding move$($s$).$

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

your tree.

Assume now that player xx plays randomly in the following way: in its first move, it places a piece in one of cells $1,2,3,$

$4$ with probability q$,$p$,$p$,$q$,$ respectively, for some fixed values p$,$q in$[0,1]$; in any subsequent moves, it picks uniformly

at random among all possible moves. Player o plays optimally as usual $($to minimize$).$

$(11$ points$)$ Solve this game by constructing its complete minimax tree. Draw the tree as in fig. $5\mathrm{.}1.$ Give the optimal

value v$^(**)($p$)($as a function only of p $)$ at the root, and the corresponding move$($s$).$

$(5$ points$)$ Explain how a real game would develop; give all the possible games $($move sequences$)$ that can happen

according to your tree and the probability of each game.

$(2$ points$)$ Since v$^(**)($p$)$ depends on p$,$ find the maximum and minimum value that v$^(**)$

can achieve and for what value

of p$.$