How hard is it

The theory is exact. Every value is a theorem, every comparison is decided, and nothing on this site is an approximation.

None of that helps with a game anybody plays, and the reason is not a gap in the theory. It is that the answers, while perfectly well defined, cannot be computed.

The right complexity class #

The instinct is to reach for NP — the class of problems whose solutions are easy to check. It is the wrong class, and seeing why is worth a paragraph.

An NP problem has a short certificate. To be convinced a graph is three-colourable, look at a colouring. To be convinced a number is composite, look at a factor.

A game has no such certificate. To be convinced Left wins, it is not enough to see a move: the claim is that Left has a move such that for every Right reply, Left has a move such that for every Right reply, and so on. The certificate is an entire strategy tree, exponentially large.

That alternation of “there exists” and “for all” is the signature of PSPACE — problems solvable with polynomial memory and unbounded time. The game recursion is the canonical PSPACE algorithm: walk the tree depth-first, keep only the current line in memory, and the line has length bounded by the game.

So games sit in PSPACE naturally, and the interesting results are the ones showing particular games are PSPACE-complete — as hard as anything in the class.

What is known to be hard #

The list is long and covers most of the games anybody has bothered to ask about.

Generalised Go is PSPACE-hard, and EXPTIME-complete under Japanese ko rules, which is worse.

Generalised chess is EXPTIME-complete. Generalised checkers likewise.

Hex is PSPACE-complete. Amazons is PSPACE-complete. Konane is PSPACE-complete.

Generalised geography, the abstract graph game, is PSPACE-complete and is the standard reduction target — most hardness proofs for board games go through it.

The word “generalised” is doing real work. Chess on an eight-by-eight board is a finite problem with a finite answer, and complexity theory has nothing to say about a single finite instance. The results are about families — chess on $n \times n$ boards — which is the only way to ask an asymptotic question about a game.

That is a genuine caveat, and it is sometimes overstated in the other direction. The reduction shows that the difficulty in the generalised family is intrinsic, and the eight-by-eight instance is unsolved, and neither fact implies the other.

What this site’s evaluator reaches #

Concretely, here is where the code stops.

lib/cgt.js evaluates by the definition: build the options, recurse, canonicalise. Memoisation and interning are in place, so structurally identical positions are computed once.

That reaches: Nim positions with a few heaps of a few dozen counters. Hackenbush strings up to length six exhaustively, longer strings individually. Domineering boards up to about $4 \times 5$. Toads and Frogs strips up to seven squares exhaustively. Thermographs of positions three or four levels deep.

It does not reach: a $6 \times 6$ Domineering board, a ten-square Toads and Frogs strip, or any Go position larger than a toy. Those are not slow; they do not finish.

The ceiling is roughly a few dozen moves of depth, and every figure on this site sits below it. Where a claim depends on smallness, the essay says so, and no value is quoted that the code did not produce.

The size of the tree #

Numbers make the ceiling less abstract.

A position with branching factor $b$ and depth $d$ has roughly $b^d$ leaves. For a small Domineering board — say twelve empty cells, so about ten moves available and ten plies of play — that is $10^{10}$ leaves, which a naive recursion will not finish.

Memoisation helps enormously, because the number of distinct reachable positions is far smaller than the number of paths to them. For Domineering, a position is a subset of occupied cells, so the reachable set is bounded by $2^{\text{cells}}$ rather than $b^d$. Twelve cells gives at most 4,096 positions, which is instant.

But $2^{\text{cells}}$ is still exponential, and it is the honest bound. Twenty cells is a million; thirty is a billion; a Go board’s 361 points is a number with no physical meaning. Memoisation converts an impossible search into an exponential one, which is progress and is not a solution.

Then canonicalisation multiplies that by the reduction cost, and the effective ceiling drops by several cells from what the raw position count suggests. Which is why the honest figure for this site’s evaluator is “a few dozen moves of depth” rather than a clean formula.

Why impartial games reach further #

A useful contrast: the impartial theory computes much larger positions than the partizan theory, and the reason is structural rather than a matter of better code.

Sprague–Grundy reduces an impartial position to a single non-negative integer. Comparing two positions is comparing two integers. Adding them is an exclusive-or. The expensive primitive of the partizan theory — comparison by playing out a difference — does not exist, because the value is a number and numbers compare in one step.

So the whole cost of the impartial theory is computing the Grundy values, and for heap games that is a one-dimensional dynamic program: linear in the largest heap, with each entry a mex over a bounded set. Sequences have been computed past $2^{40}$ terms.

Partizan values are trees. They do not compare in one step, they do not add in one step, and they grow with the position rather than staying bounded. That is the entire difference, and it is why this site’s Domineering table stops at $4 \times 5$ while its Grundy strips could run to any length that fits on the page.

The lesson generalises: the tractability of a value system is about how expensive its comparison operation is, and everything else follows.

Why canonicalisation is the bottleneck #

The cost is not evenly spread, and the expensive part is worth naming.

Evaluating a position means recursing over its options — expensive, but linear in the number of reachable positions with memoisation.

Canonicalising means comparing every option against its siblings and against the whole position, repeatedly, until nothing changes. Each comparison is itself an evaluation of a difference, whose state space is the product of the two operands’. And the reduction loop may run several passes.

So the cost of a value is not the cost of the search; it is the cost of the search times the cost of the reduction, and the reduction is quadratic in the option count per pass with an expensive primitive.

That is why interning mattered so much here. Without it, structural keys for sums like $\ast 3 + \ast 5$ grew to megabytes and comparison spent all its time building keys. With integer identities the primitive is cheap and the ceiling rises by several levels of depth — which is the difference between evaluating a $3 \times 4$ Domineering board and not.

A theory that knows its own reach #

One thing this subject does unusually well is state its limits, and the reason is that the limits are theorems rather than admissions.

An empirical field with a model that stops working at some scale has a calibration problem: nobody knows exactly where the model fails, and the boundary is found by trying. Here the boundary is proved. Generalised Go is EXPTIME-complete, which is a statement about every possible algorithm, not about the ones anybody has written.

That changes what “the theory does not reach this” means. It is not a promise that better methods will arrive; it is a statement that they will not, conditional on separations that are themselves open but universally believed.

The same precision applies at the small end. This site’s evaluator stops where it stops for reasons that can be counted — reachable positions, comparison cost, reduction passes — and the figures sit below that line by construction rather than by hope. A value that appears here was computed; a value that could not be computed does not appear.

Where the theory still earns its place #

None of this makes the theory useless, and the reason is decomposition.

A large position is intractable. A large position that has broken into twenty small independent regions is twenty tractable problems and an addition. The theory’s contribution is precisely that the addition is exact and free.

So the practical method is: wait until the position decomposes, evaluate the parts, add. That is what Go endgame analysis does, what Domineering analysis does, and what makes the theory applicable to real games at all.

It also explains the shape of the applicability. The theory reaches endgames, not middlegames — not because endgames are simpler in some vague sense, but because an endgame is by definition a position that has decomposed. A middlegame is one connected region, and one connected region of any size is out of reach.

Approximation, where exactness fails #

When exact evaluation is unaffordable, the theory offers approximations, and they are structured rather than ad hoc.

Temperature approximates a position by a mean and an urgency. The mean is exact and adds; the temperature is exact per component and does not add. That is a principled trade: keep the additive part exact, approximate the rest.

Atomic weight does the same for infinitesimals — approximately how many ups a position is worth, ignoring differences below a star.

Both are lossy on purpose, and both come with a statement of what was lost. That is what distinguishes them from a heuristic evaluation function, which is lossy in ways nobody can characterise.

Undecidable in the pattern, not the answer #

There is a second kind of hardness on this site, and it is worth separating from the first.

Grundy sequences are trivially computable term by term. The recursion is a first exercise in dynamic programming and each entry costs almost nothing. What is unknown is whether the sequences ever become periodic — and for $\mathbf{0.007}$, Grundy’s game and a handful of others, they have been computed past $2^{35}$ terms without repeating.

That is not intractability in the complexity sense. Every individual answer is available cheaply. What is missing is a description, and no amount of computation produces one.

So there are two failures with different characters. Complexity says the answers are unreachable. The periodicity problem says the answers are reachable one at a time and the pattern in them is unknown. A theory can have both, and this one does.

What kind of limit this is #

It is worth being precise about what complexity does and does not damage, because it is the mildest of the three boundaries.

Misère play makes the theorems false. Loops make the recursion undefined. Complexity leaves every theorem true and every definition well formed, and puts the answers out of reach.

That is a real limit and a different kind. The value of a $19 \times 19$ Go position exists, is unique, and would compose correctly with any other position’s. Nobody will ever know it.

Which is a comfortable position for a mathematical theory and an uncomfortable one for anybody wanting to use it. The response is decomposition and approximation, and both are principled, and neither closes the gap.

Solved, unsolved, and unsolvable #

Three words that get used interchangeably and should not be.

Solved means the outcome from the starting position is known. Checkers is solved — Jonathan Schaeffer’s team established in 2007 that perfect play draws — and that took eighteen years of computation over a search space of $5 \times 10^{20}$ positions.

Unsolved means nobody has done it yet. Chess and Go are unsolved. Whether they are solvable in principle is not in question; they are finite, and a sufficiently patient machine would settle them.

Intractable means no machine will. Generalised Go being EXPTIME-complete says that the family of Go problems cannot be decided in polynomial time, which is a statement about all algorithms and all futures.

The three are independent, and conflating them produces bad claims in both directions. “Go is PSPACE-hard, so nobody will ever solve it” confuses the family with the instance. “Checkers was solved, so Go will be” ignores the several orders of magnitude between them.

What this site’s evaluator does is a fourth thing again: it does not solve games, it computes values of small positions, which is a stronger claim about a much smaller object. A solved game gives one answer for one starting position; a computed value gives an object that composes correctly with every other position there is.

Who proved what, and when #

The PSPACE-completeness of generalised geography is Thomas Schaefer’s, from 1978, and it is the foundation most later results build on.

Go’s hardness is due to David Lichtenstein and Michael Sipser (1980) for the PSPACE-hardness, and to Robson (1983) for the EXPTIME-completeness under Japanese ko rules. Fraenkel and Lichtenstein proved generalised chess EXPTIME-complete in 1981. Hex’s PSPACE-completeness is Even and Tarjan (1976) for a variant and Reisch (1981) for Hex itself.

Aviezri Fraenkel maintained the standard bibliography of the field for decades, and it is the reason the complexity results and the combinatorial results are usually cited together.

The chronology is worth noticing: the hardness results arrived within a decade of Conway’s theory, and largely independently. The theory of values and the theory of difficulty grew up side by side, which is why the subject has been candid about its limits from early on.

Where the model stops #

Generalised games only. Asymptotic statements need families, not instances.

The ceiling here is a few dozen moves of depth. Every value on this site sits below it, and none is claimed above it.

Decomposition is necessary, not automatic. A position that has not broken up is out of reach at any size worth caring about.

Approximations have bounds, and the bounds are not tight. The hottest-first rule is good and provably imperfect.

Complexity is orthogonal to the other limits. A game can be intractable, misère and loopy at once.

The ladder from here #

Nearby: the PSPACE-completeness of geography, proved; the reductions from geography to specific games; the EXPTIME results and why loops raise the class; and the complexity of evaluating a position as against deciding it, which is a different and less-studied question.

Then back to the constructive side. The theory’s response to intractability is decomposition and approximation, and both are what most of this site is about — temperature exists because exactness ran out, and it is a better answer than resignation.