PSPACE and Games

"Can White force a win from this position?" is not a question about finding one clever move. It is a question about a whole strategy: a move for White, such that for every Black reply, there is a White move, such that for every Black reply… all the way to checkmate. The quantifiers alternate without bound, and the answer depends on the entire, exponentially large game tree. No short certificate — no single "winning line" — settles it, because the opponent gets to choose.

Problems like this live one storey above the polynomial hierarchy, in PSPACE — everything solvable with a polynomial amount of memory, however much time it takes. This page shows why "solving games" is the beating heart of PSPACE, through one master problem: the true quantified Boolean formula.

PSPACE: bounded memory, unbounded time

PSPACE is the class of problems a Turing machine can decide using memory bounded by a polynomial in the input size. Time is not bounded: a PSPACE machine may run for exponentially many steps, as long as it never uses more than \mathrm{poly}(n) tape cells — happily overwriting the same cells again and again.

That single freedom makes PSPACE roomy. We know \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PH} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}, and by the space hierarchy theorem \mathrm{PSPACE} \subsetneq \mathrm{EXPSPACE}. Yet whether any of the earlier inclusions is strict — even \mathrm{P} \overset{?}{=} \mathrm{PSPACE} — is open. What we can pin down exactly is PSPACE's hardest problem.

TQBF: the PSPACE-complete problem

Take a Boolean formula and put a quantifier on every variable, alternating freely:

\exists x_1\, \forall x_2\, \exists x_3 \cdots Q x_n\; \varphi(x_1,\dots,x_n)

This is a quantified Boolean formula (QBF). Because every variable is bound, the whole thing is simply true or false — no free variables, no assignment to supply. TQBF is the decision problem: is this QBF true?

In PSPACE. Evaluate recursively: to check \exists x_i\,\psi, try x_i = 0 and x_i = 1 and OR the results; for \forall x_i\,\psi, AND them. The recursion is n deep and each frame stores O(1) bits, so O(n) space suffices — even though it explores 2^n leaves.
PSPACE-hard. Every PSPACE computation can be encoded as a QBF (the alternating quantifiers simulate the machine's configuration graph, using the same doubling trick as Savitch's theorem below). So TQBF is PSPACE-complete — the SAT of PSPACE.
Note the contrast with SAT: SAT is \exists-only (one quantifier block, NP). TQBF's alternation is exactly what lifts it from NP up to PSPACE.

Reading a QBF as a two-player game

Here is the move that makes everything click. Read each quantifier as a player choosing a bit:

Quantifier	Player	Wins if…	Boolean op
\exists x_i	Me ("I move")	I can pick a value making the rest true	OR / max
\forall x_i	Opponent	every value the opponent picks still leaves it true	AND / min

The QBF is true exactly when I have a winning strategy: whatever the opponent does at the \forall moves, I can respond at my \exists moves so the final formula \varphi comes out true. Evaluating the QBF is solving the game. The tree below shows it for \exists x\,\forall y\,\varphi: my move at the top, the opponent's replies below, leaves are the value of \varphi. I OR my options; the opponent ANDs theirs.

Follow the winning line: I play x = 1; then both of the opponent's replies (y = 0 and y = 1) lead to a true leaf, so that whole subtree ANDs to true — I win. Had I played x = 0, the opponent could pick the false leaf. Because a good move exists, the formula \exists x\,\forall y\,\varphi is true.

Why generalised games are PSPACE-hard

A one-off puzzle (a fixed 8×8 board) is only a finite lookup — no asymptotics. The interesting question is the generalised game: play on an n \times n board, and ask whether the first player can force a win as n grows. Because such a game is precisely an alternating \exists/\forall search — my move, your move, my move — it maps straight onto TQBF, and many generalised games turn out PSPACE-complete:

Generalized Geography — the canonical PSPACE-complete game; the standard textbook reduction from TQBF builds a geography graph whose gadgets mimic each quantifier.
Generalized Hex and Generalized Go (with suitable rules) — both PSPACE-hard; "can the first player force a win?" is as hard as any PSPACE problem.
The signature is bounded-length alternating play. (Games that can last exponentially long, like Go with certain rules, can climb even higher, to EXPTIME.)

So "is there a winning strategy?" is the game-flavoured face of TQBF, and its difficulty is a feature, not a bug: it is why perfect play in rich combinatorial games is, in general, computationally out of reach.

Savitch's theorem: nondeterminism is (almost) free for space

For time, nondeterminism looks enormously powerful — that is the whole \mathrm{P} vs \mathrm{NP} mystery. For space, it nearly evaporates.

For any s(n) \ge \log n, \mathrm{NSPACE}(s) \subseteq \mathrm{SPACE}(s^2) — a nondeterministic space-s machine can be simulated deterministically in space s^2.
Squaring a polynomial is still a polynomial, so \mathrm{NPSPACE} = \mathrm{PSPACE}: nondeterministic polynomial space buys nothing.
The proof is the recursive reach(a, b, 2^k) "can I get from configuration a to b in \le 2^k steps?" halving trick — it guesses a midpoint and recurses on the two halves, reusing space. Its \forall-over-midpoints / \exists-midpoint shape is exactly the alternation that also encodes PSPACE as TQBF.

Savitch is why we do not bother with a separate class "NPSPACE," and it is the engine behind TQBF's PSPACE-hardness. It also tightens the map: combined with the earlier chain, \mathrm{PH} \subseteq \mathrm{PSPACE}, so the entire polynomial hierarchy — every finite tower of alternations — fits inside the single class that TQBF completes.

The tempting shortcut: "a winning strategy is a certificate — guess it, then verify." The trouble is size. A full strategy must prescribe a reply to every possible opponent history, and there are exponentially many of those, so the strategy itself is an exponentially large object — not a polynomial certificate at all. Worse, verifying it means checking all opponent responses, which is another exponential sweep. NP's \exists can guess my moves, but it cannot handle the interleaved \forall over the opponent's moves. That unbounded alternation is precisely what PSPACE (and TQBF) captures and NP cannot — unless, of course, the polynomial hierarchy collapses and PSPACE turns out surprisingly small.

A PSPACE algorithm may run for exponentially long — the TQBF evaluator visits all 2^n leaves — while touching only O(n) memory cells, because it reuses the same cells on every branch. "PSPACE" bounds the tape, never the clock. Conversely, everything in P is trivially in PSPACE (in t steps you can scribble on at most t cells), but the reverse — is \mathrm{PSPACE} \subseteq \mathrm{P}? — is a famous open problem, almost surely false. Do not read "small memory" as "fast."