This problem exercises the basic concept of game playing, using tic$-$tac$-$toe $($noughts and crosses$)$ as an example. We defined $$ as the number of rows, columns, or diagonals with exactly $$s and no $$s$.$ Similarly, $$ is the number of rows, columns, or diagonals with just $$s$.$ The utility function assigns $+1$ to any position with $3=1$ and $1$ to any position with $3=1.$ All other terminal positions have utility $0.$ For nonterminal positions, we use a linear evaluation function defined as $()=32()+1()(32()+1()).$