A simple example of a full information game is *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 ; 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 *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 *cannot* be
solved in a *subexponential* time. We first prove that (see
[Chandra, Kozen, Stockmeyer 1981]) for an artificial game. Then we
reduce this *Halting Game* to Linear Chess.

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

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 determines if stops (i.e. the leftmost tape cell points left)
in steps. This requires steps. We now convert **u**
into the Halting Game.

The diagram shows the states **A** of cell **p** at time
**t+1** and 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 point
away from each other, or (2) **A** differs from the result prescribed
by the transition rules for ,
or (3) **t=1**, while . (At
**t=1**, 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
**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 . When **S** moves, he: chooses **s**, copies
into **A** and fills all
**B** with ?'s; adds **s** to **p** and **-1** to **t**.

Start: **L** puts:
**S** puts:

Note that **L** may lie (i.e fill in ``?'' distorting the actual
computation of ), 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 as an evidence of **L**'s violation.

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 halts in
steps, which requires **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.

Wed Aug 21 20:35:42 EDT 1996