\newpage\subsection {Exponentially Hard Games.\label{exp-g}}

A simple example of a full information game is {\em Linear Chess}, played on a
finite linear board. Each piece is loyal to one of two sides: W (weak) or S
(shy). It is assigned a gender M or F and a rank from a set of ranks $\Sigma$;
this set doesn't depend on the board size. All the W's are always on the left
side and all the S's on the right. All cells of the board are filled. Changes
occur only at the {\em active} border where W and S meet (and fight). The
winner of a fight is determined by the following Gender Rules:

1. If S and W are of the same sex, W (being weaker) loses.

2. If S and W are of different sexes, S gets confused and loses.

The party of a winning piece A replaces the loser's piece B by its own
piece C. The choice of C is restricted by the table of rules listing all
allowed triples (ABC). We will see that this game {\em cannot} be solved
in a {\em subexponential} time. We first prove that (see [Chandra,
Kozen, Stockmeyer 1981]) for an artificial game. Then we reduce this
{\em Halting Game} to Linear Chess.

For Exp-Time Completeness of regular (but $n\times n$) Chess, Go and Checkers
see: [Fraenkel, Lichtenstein 1981], [Robson 1983, 1984].

\subsubsection* {Exptime Complete Halting Game.\label{halt-gm}}

We use a universal Turing Machine $u$ (defined as 1-pointer cellular
automata) which halts only by its head rolling off of the tape's left
end, leaving a blank. Bounded Halting Problem BHP$(x)$ determines if
$u(x)$ stops (i.e.\ the leftmost tape cell points left) in $2^{|x|}$
steps. This requires $\Omega(2^{|x|})$ steps. We now convert $u$ into
the Halting Game.

\noindent\parbox{270pt} {The players are: $L$ claiming $u(x)$ halts in
time (and should have winning strategy iff this is true); His opponent
is $S$. The {\em board} has four parts: the diagram, the input $x$ to
$u$, positive integers $p$ (position) and $t$ (time in the execution of
$u(x)$):} \hspace{1pc}
 \fbox {\begin{tabular}{|c|c|c|c|c|c|c} \cline{1-2}\cline{5-5}
 $p$&$t$&\multicolumn{1}{c}{}&&$A$&\multicolumn{1}{c}{}&$t+1$\\
 \cline{1-2}\cline{4-6}\multicolumn{2}{|c|}{$x$}&&$B_{-1}$&$B_0$&$B_{+1}$&$t$\\
 \cline{1-2}\cline{4-6} \multicolumn{3}{c}{}& \multicolumn{1}{c}{$p-1$}&
 \multicolumn{1}{c}{$p$}& \multicolumn{1}{c}{$p+1$} \end{tabular}}

The diagram shows the states $A$ of cell $p$ at time $t+1$ and $B_s,\, s\in
\{0,\pm1\}$ of cells $p+s$, at time $t$. $A,B$ include the pointer direction;
$B$ may be replaced by ``?''. Some board configurations are illegal:
 if (1) two of $B_s$ point away from each other, or (2) $A$ differs from the
result prescribed by the transition rules for $B_s$, or (3) $t=1$, while $(B_s)
\ne x_{p+s}$. (At $t=1$, $u(x)$ is just starting, so its tape has the input
$x$ at the left, the head in the initial state at the end with blanks leading
off to the right.) Here are the {\bf Game Rules:}

The game starts in the configuration shown below.
 $L$ moves first replacing the ?'s with symbols that claim to reflect the state
of cells $p+s$ at step $t$ of $u(x)$. When $S$ moves, he: chooses $s$, copies
$B_s$ into $A$ and fills all $B$ with ?'s; adds $s$ to $p$ and $-1$ to $t$.

\noindent Start: \fbox{\begin{tabular}{|c|c|c|c|c|c|}\cline{1-2}\cline{5-5}
 $p=0$&$t=2^{|x|}$&\multicolumn{1}{c}{}&&$\leftarrow$&\multicolumn{1}{c}{}\\
 \cline{1-2}\cline{4-6}\multicolumn{2}{|c|}{input $x$}&&?&?&?\\
 \cline{1-2}\cline{4-6} \end{tabular}} \hspace{1pc}
	$L$ puts: \fbox{\begin{tabular}{|c|c|c|c}\cline{2-2}
 \multicolumn{1}{c|}{}&$a$&\multicolumn{1}{c}{}&$t+1$\\
 \cline{1-3}$b$&$c$&$d$&$t$\\\cline{1-3} \end{tabular}} \hspace{1pc}
	$S$ puts: \fbox{\begin{tabular}{|c|c|c|c}\cline{2-2}
 \multicolumn{1}{c|}{}&$d$&\multicolumn{1}{c}{}&$t$\\
 \cline{1-3}$?$&$?$&$?$&$t-1$\\\cline{1-3}\end{tabular}}

Note that $L$ may lie (i.e fill in ``?'' distorting the actual computation of
$u(x)$), as long as he is consistent with the above ``local'' rules. All $S$
can do is to check the two consecutive board configurations. He cannot refer to
past moves or to actual computation of $u(x)$ as an evidence of $L$'s
violation.

\paragraph{Strategy:} If $u(x)$ does indeed halt within $2^{|x|}$ steps, then
the initial configuration is true to the computation of $u(x)$. Then $L$ has an
obvious (though hard to compute) winning strategy: he just tells the truth,
what actually happens during the computation. He will be always consistent;
 $S$ will lose when $t=1$ and cannot decrease any more. If the initial
configuration is false then $S$ can win exploiting that $L$ must lie.
If $L$ lies once, $S$ can force $L$ to lie all the way down to $t=1$. How?

If the upper box $a$ of a legal configuration is false then the lower boxes
$b,c,d$ cannot all be true, since the rules of $u$ determine $a$ uniquely from
them. If $S$ guesses correctly which of $b$, $c$, or $d$ is false and brings it
to the top on his move, then $L$ is forced to keep on lying. At time $t=1$ all
chips are down: the lying of $L$ is exposed since the configuration doesn't
match the actual input string $x$, i.e. is illegal. In other words, $L$ can't
consistently fool $S$ all the time: eventually he is caught.

Solving this game amounts to answering whether the initial configuration
is correct, i.e.\ whether $u(x)$ halts in $2^{|x|}$ steps, which
requires $\Omega(2^{|x|})$ steps. This Halting Game is artificial, still
with a flavor of BHP, although it does not mention the exponent in its
definition. We now reduce it to a nicer game (linear chess) to prove it
exponential too.