To reduce (see definition in sec. 2.2) Halting game to Linear Chess we introduce a few concepts.
A non-deterministic Turing Machine (NTM) is a TM that
sometimes offers a (restricted) transition choice, made by a
driver, a function (of the TM configuration) of unrestricted
complexity. A deterministic (ordinary) TM M accepts a string
x if 
= yes; a
non-deterministic TM M does if there exists a driver d
s.t. 
yes.
NTM represent single player games, puzzles, e.g. Rubik's Cube with a simple transition rule. We can compute the winning strategy in exponential time (exhausting all positions).
Home Work: Is there a P-time winning strategy for every such game? Nobody knows. Alternatively, show it requires exponential time. Grade A for the course and, probably, a senior faculty position at the university of your choice will be awarded for a solution.
The alternating TM (ATM) is a variation of the NTM driven
by two alternating drivers (players) l and r. A string is
accepted if there is l such that for any 
yes. Our games could be viewed as ATM using a small
space but up to an exponential time and returning the result of the
game. It prompts l and r alternatingly to choose their
moves (in several steps if the move is specified by several bits) and
computes the resulting position, until a winner emerges. Accepted
strings describe winning positions.
We first simulate our Halting Game by L-Chess, a variant of
Linear Chess. It has the same board: 
and, like regular chess, 6 ranks.
Unlike Linear Chess, where only the vanquished piece is replaced, in
L-chess the winning piece may also be replaced by (``promoted to'') a
piece of the same side; the gender bit is set to the side bit of the
previous step, and an arbitrary table rather than the simple ``Gender
Rule'' determines the winning piece.
The simulation is achieved simply by representing the Halting Game as an ATM computation simulated by the universal TM (using ``='' commands for players' input). The UTM is viewed as an array of 1-pointer cellular automata: Weak cells as rightward, Shy leftward. The TM head is set to move upon termination to the end of the tape, so that no loser pieces are left. To transform L-Chess to Linear Chess it is left (as an exercise) to modify genders, extend ranks, and replace each transition by several, so that the winning piece is determined by the Gender Rule and is not replaced. So, any fast algorithm to solve Linear Chess, could be used to solve any game. Since Halting Game requires exponential time, so does the Linear Chess.
Deterministic linear space computations are games where any position has at most one (and easily computable) move. We know no general superlinear lower bound or subexponential upper bound for time to determine their outcome. This is the space-time trade-off problem. You met with such trade-offs using techniques like dynamic programming: saving time at the expense of space.
This is equivalent to the existence of a P-time algorithm for solving any fast game, i.e. a game with a P-time transition rule and a counter decremented at each move, limiting the number of moves to a polynomial. The sec. 3.1 algorithm can be implemented in parallel P-time for such games. Conversely, any narrowly computable predicate may be expressed as one determining the winning side of a fast game (similar to the Halting Game). Thus, fast games (i.e. compact alternating computations) correspond to narrow deterministic computations; general games (i.e. narrow alternating computations) correspond to large deterministic ones.
A Related Question: Do all exponential volume algorithms (e.g., one solving Linear Chess) allow an equivalent narrow computation? The two conjectures are mutually exclusive: otherwise we could solve the exponential-time Bounded Halting Problem in polynomial volume.