The class is named after memory, and that is not an accident

Solving the 4×4 Domineering board with a memo table takes 5,700 entries. Solving it with no table at all takes 6,257,129 visits and eight positions of memory.

Eight, because that is how long the longest line of play is, and a solver that keeps only the current line needs to remember nothing else.

Three resources, and the small one names the class #

The recursion that evaluates a position can be run in two ways, and they sit at opposite ends of a trade.

With a table. Every position visited is stored, so nothing is computed twice. Time is the number of positions; memory is also the number of positions.

Without one. Every position is recomputed each time it is reached. Time is the number of routes; memory is one position per level of the current line, and nothing else — because once a subtree has returned its answer, everything in it can be forgotten.

The second is hopeless on the clock and extraordinary on memory. For the 4×4 board it is six million visits against eight stored positions. For three heaps of 7, 11 and 13 it is 7.6 × 10¹⁶ visits against thirty-one stored heaps triples, which fits comfortably in a few hundred bytes.

That second column is where the complexity class comes from. PSPACE is the set of problems decidable in memory polynomial in the input, with no restriction on time, and the table-free recursion puts every game of this kind squarely in it: the depth of a game is bounded by the size of the position — a Domineering move covers two squares, so a board of $n$ squares lasts at most $n/2$ moves — and each level of the stack holds one position.

Why the depth is always small #

The reason this works is a property of the games rather than of the algorithm, and it is worth saying plainly: these games are short.

Every move in Domineering permanently covers two squares. Every move in Clobber permanently removes a stone. Every move in Geography permanently uses up a vertex. In each case a quantity that cannot rise is falling, so the game ends in at most as many moves as that quantity had to give.

The technical name for the requirement is the ending condition, and this site’s whole apparatus rests on it: the recursion that defines a value terminates precisely because play does. So the depth is bounded by something linear in the position, always, in every game here.

The exception is exactly the case where the theory breaks. A loopy game has no such falling quantity — play can return to a position it has already visited — and the stack-based solver would run for ever. That is why loopy games need a different method entirely, one that works over the whole position set rather than down a line, and it is why they are filed under the theory running out rather than under cost.

The depth bound is a rank, and there are two ways to lose it #

These games are short is the load-bearing sentence of the whole argument, and it is worth saying exactly what it is claiming, because the essay names one way it can fail and there are two.

What the stack needs is a finite rank: a quantity attached to each position, taking natural-number values, that strictly falls at every move. Every termination argument on this site is one — covered squares, removed stones, used vertices — and a finite rank does double duty. It proves the game ends, and it bounds the depth by its own value, which is what puts the stack in polynomial space.

A loopy game has no rank at all. Play returns to a position it has already visited, nothing falls, the stack solver runs for ever, and the essay’s exception clause covers it.

And a game can have a rank that is not finite. Some games end and nothing says when: every line terminates, so there is a rank, and the rank is an ordinal past $\omega$ rather than a natural number. Such a game is not loopy — no position ever recurs — and the stack argument fails anyway, because an ordinal rank bounds nothing.

Which the site has an example of #

That second case is not hypothetical here. Sylver Coinage is a genuine two-player impartial game on this site, it terminates — the theorem that says so is Sylvester’s, from number theory — and the length of a game is bounded by no function of the opening move.

So a stack-based solver for it has no depth bound to quote, and the polynomial-space argument above does not reach it. That is a different situation from a loopy game, which fails the ending condition outright and needs a method that works over the whole position set instead. Sylver Coinage satisfies the ending condition and still defeats the stack.

So the essay’s exception is really two exceptions, and they fail differently: a loopy game has no rank, and an unboundedly-long one has a rank with no finite bound in it. Only the first is a failure of the theory; the second is a failure of the complexity argument while the theory holds perfectly.

What that says about the class #

The distinction matters for what “these games are in PSPACE” is claiming.

It is a statement about a family, and the family is games with a finite rank bounded polynomially in the position size. Domineering, Clobber, Nim written out, Geography — every game with a board that fills up or a supply that runs down.

It is not a statement about games in general, and it is not a statement about combinatorial game theory. The subject’s own boundary — the ending condition — is weaker than the complexity argument’s, and the gap between them contains at least one game somebody plays.

And the gap is worth knowing before quoting the class. A reader told that these games are PSPACE-complete may reasonably assume the class covers whatever this site studies. It covers the games whose depth is bounded by their size, which is nearly all of them, and the exceptions are exactly the ones the last two fields of the site are about.

The trade, priced both ways #

Set the two regimes against each other on the same board and the numbers are almost comic.

A factor of about a thousand in time, bought with a factor of about seven hundred in memory. That is a good trade on this board and on any board a person is likely to care about, and it is the trade every real solver makes.

It stops being a good trade at exactly one point: when the table no longer fits. Past that, a solver must choose what to forget, and every eviction reintroduces some of the routes the table was there to remove. Real engines handle this with replacement policies and lossy tables, accepting collisions in exchange for capacity — which is a different kind of program from the one described here, and one whose answers are only as good as its hash function.

What one level of the stack actually holds #

It is worth writing out what the memoryless solver stores, because “polynomial space” is the kind of phrase that hides whether a claim is tight.

At each level there is the position — a Domineering board is one bit per square, so sixteen bits on 4×4 — plus a note of which option is currently being tried, plus the best answer found so far among the options already tried. Call that a few times the size of a position.

The number of levels is the depth, which is at most the number of moves the game can last: half the squares for Domineering, one per stone for Clobber, one per counter for Nim written out. So the whole stack is quadratic in the size of the position at worst and usually much less — sixteen positions of sixteen bits is thirty-two bytes for the 4×4 board, against a table of 5,700 entries.

Two things follow that are easy to miss. First, the bound holds for the whole family: it is a statement about every board, not about the ones drawn here. Second, it does not depend on the game being small — a 40×40 Domineering board has a stack of eight hundred levels, which is nothing, and a search that would not finish before the sun burns out.

The bound is also not the same bound in two families, and setting them on one scale is the way to see it.

That combination — trivial memory, impossible time — is the exact profile of a PSPACE algorithm, and it is what the class was defined to capture. It is also the profile nobody would choose to run: the class is a statement about what is possible within a resource, and the possibility is being demonstrated by an algorithm no sane person would use.

Playing it out is the algorithm #

There is something pleasing about the fact that the space-efficient method is not a clever construction. It is playing the game.

A person sitting at a board with no notes, trying every reply and taking back moves that did not work, is running precisely the algorithm above: one position at a time, the current line remembered, everything else forgotten. The stack is their memory of how they got here, and the backtracking is the recursion returning.

What they cannot do is the other half — remembering the answer to every position they have ever evaluated. That is the part a machine can do and a person cannot, and it is the part that turns six million visits into 5,700.

So the two regimes are not two algorithms so much as two kinds of player: the one who reasons and forgets, and the one who reasons and remembers. The theory’s complexity class describes the first. Every practical solver, including the one behind the playable figures here, is the second.

Space is the honest measure of what is out of reach #

There is a practical reason to watch memory rather than the clock, and it is the reason this essay exists as a separate rung.

A program that is too slow gives partial information: it can be left running, it can be stopped, it can report progress. A program that runs out of memory stops dead, and it stops dead at a size that is predictable in advance — the table size can be computed before the search is started, as this site’s figures do routinely.

So a person planning to solve something can ask “will this fit?” and get an answer without running anything. The 4×4 board needs 5,700 entries; 5×5 needs far more; the crossover from comfortable to impossible is a calculation rather than an experiment. That is a much better position to be in than waiting to find out.

It also explains why so many strong results in game solving are space engineering rather than search engineering. Endgame databases for chess and checkers are exactly this: pay enormous memory once, and every position covered becomes free for ever. The retrograde analysis that builds them is the same method the loopy games here need, applied at industrial scale.

Where the two classes meet #

Two facts about PSPACE are worth having, because together they explain why games sit there so comfortably.

It absorbs NP. Anything with a short certificate can be checked in small memory by trying certificates one at a time, keeping only the current one. So the puzzle question is in PSPACE too, and games being PSPACE-complete says they are at least as hard as puzzles.

Non-determinism buys nothing in space. Savitch’s theorem says a problem solvable in non-deterministic space $s$ is solvable deterministically in space $s^2$ — a polynomial change, so PSPACE is unchanged by allowing guessing. Nothing like that is known for time, where the analogous question is P against NP.

That second fact is why alternation lands in a space class rather than somewhere new. A game’s alternating quantifiers would be expected to add power, and in space they do not: the stack that plays out one line and backtracks handles every quantifier the same way, whichever player it belongs to.

It is worth seeing why in the smallest case. A quantified formula over three variables is three turns, and a solver playing it out holds one variable’s assignment per level of its stack — three levels — revisiting the alternatives by backtracking rather than by keeping them. Existential and universal quantifiers are handled by the same loop with a different test at the end of it, so the alternation that makes the formula problem the hardest in the class costs the solver time and no memory at all.

What the model leaves out #

Three limits, and the first is the sort that only shows up on a real machine.

Memory is not flat. The model above counts positions, and a real table’s cost depends on whether it fits in cache, in RAM, or spills to disk — three regimes with performance an order of magnitude apart. A “5,700-entry table” that thrashes is slower than a table-free search on the same board, and no amount of counting entries reveals it.

The stack holds more than a position. Each level also holds the loop state — which option is being tried, what the best answer so far is — so the constant per level is a small multiple of the position size rather than one. Polynomial either way, and the distinction matters when the polynomial is being measured rather than merely asserted.

Decomposition changes the accounting entirely. A board that splits into regions is several small searches with several small tables, and the memory needed drops from the product to the sum exactly as the time does. This is the single largest thing a solver can do about memory pressure, and it is available only because the theory says values add.

The measurement this site actually makes #

Every count in this essay comes from walking position graphs, and one of the numbers is measured in a way worth describing, because it is the one that cannot be obtained by running the thing being measured.

The route count for three heaps of 7, 11 and 13 is 75,707,699,717,937,900. No process visits that many nodes. The number is computed bottom-up through the 480-position graph — the size of the tree at a position is one plus the sizes at its options — and it comes out exact, in a BigInt, in a few milliseconds.

So the cost of the memoryless method is established by the memoryful one. That is not a trick; it is the same observation the whole essay rests on. Any quantity that depends only on the position, and not on the route taken to it, can be computed once per position — and time, unlike memory, is exactly such a quantity.

The one place the depth is not small #

Every game on this site has short play, and it is worth being precise about what would have to change for that to fail, because the failure is instructive.

The ending condition requires some quantity to fall with every move. Nim has counters, Domineering has free squares, Geography has unused vertices. Take that away and two things happen at once: the recursion defining a value has no base case to reach, and the stack-based solver has no bound on its depth.

Loopy games are exactly that situation, and their analysis abandons the stack altogether — it labels the whole set of positions in rounds, outward from the ones already lost, and whatever is never labelled is a draw with no value at all. The memory that method needs is the whole position set, which is the memoised regime and not the memoryless one.

So the tidy statement these games are in PSPACE has a precondition that is invisible until it fails: the games must end. Where they do, the depth is linear in the position and the stack is cheap. Where they do not, the space-efficient method is not merely slower — it does not exist, and what replaces it is the expensive one.

That is a reasonable summary of the boundary this field is drawing. Cost is what happens when the theory holds and the answer is far away. The theory failing is a different thing entirely, and it is filed one field over.

Who named it #

The complexity class was defined and studied in the early 1970s, in the same run of work that produced NP-completeness; Savitch’s theorem dates from 1970 and Stockmeyer and Meyer’s quantified-satisfiability result from 1973. Games arrived immediately afterwards, and the reason they arrived so quickly is the one this essay has been making: the connection between a stack and an alternating quantifier is short enough to see at once.

The lasting lesson is a reframing rather than a theorem. Asked why a game is hard, the natural answer is there are too many positions. The better answer is that there are too many routes, that positions are far fewer, and that a machine can always afford the depth — so the whole engineering question is how much of the middle quantity can be paid for.

The next rung turns from what a solution costs to what a solution is. Three different claims are all spoken as “solved”, they differ by orders of magnitude in price, and the playable figures on this site are the most expensive kind on the smallest possible positions.