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.
does indeed halt within
steps, then the initial
configuration is true to the computation of 
. 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 
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.