next up previous contents
Next: 3.3 Reductions; Non-Deterministic and Up: 3 Games; Alternation; Exhaustive Previous: 3.1 How to Win.

3.2 Exponentially Hard Games.

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].

Exptime Complete Halting Game.

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

next up previous contents
Next: 3.3 Reductions; Non-Deterministic and Up: 3 Games; Alternation; Exhaustive Previous: 3.1 How to Win.

Leonid Levin
Wed Aug 21 20:35:42 EDT 1996