\newpage \section {Games; Alternation; Exhaustive Search;
Time v. Space.}\label{games}
\subsection {How to Win.\label{win}}
In this section we consider a more interesting {\em provably}
intractable problem: playing games with full information, two players
and zero sum. We will see that even for some simple games there cannot
be a much more efficient algorithm, than exhaustive search through all
possible configurations.
The rules of an {\em $n$-player game} $G$ are set by families $f,v$ of
{\em information} and {\em value} functions and a {\em transition rule}
$r$. Each player $i\in I$ at each step participates in transforming a
configuration (game position) $x\in C$ into the new configuration
$r(x,m),\ m:I\to M$ by choosing a move $m_i= m(i)$ based only on his
knowledge $f_i(x)$ of $x$. The game proceeds until a {\em terminal}
configurations $t\in T\subset C$ is reached. Then $v_i(t)$ is the loss
or gain of the $i$-th player. Our games will have {\em zero sum} $\sum
v_i(t)=0$ and {\em full information:} $f_i(x)=x$, $-|x|