\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, 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.