$5\mathrm{.}9$ This problem exercises the basic concepts of game playing, using tic$-$tac$-$toe $($noughts

and crosses$)$ as an example. We define Xn as the number of rows, columns, or diagonals

$198$ Chapter $5.$ Adversarial Search

with exactly n X$$s and no O$$s$.$ Similarly, On is the number of rows, columns, or diagonals

with just n O$$s$.$ The utility function assigns $+1$ to any position with X$3=1$ and $1$ to any

position with O$3=1.$ All other terminal positions have utility $0.$ For nonterminal positions,

we use a linear evaluation function defined as Eval$($s$)=3$X$2($s$)+$X$1($s$)(3$O$2($s$)+$O$1($s$)).$