The game with the shortest rule is the hard one

Three heaps of thirty counters. An exhaustive solver — one that evaluates every position it can reach and works backwards — visits 5,456 of them before it can say who wins.

The rule says the same thing in three steps: take the exclusive or of $30$, $30$ and $30$; it is $30$; it is not zero; the player to move wins.

What “hard” is a statement about #

Deciding a generalised board game is PSPACE-complete, and that sentence is easy to hear as “games are hard”. It says something narrower and more useful.

Hardness is a property of a family of games together with the way its positions are written down. Generalised Geography is hard because there is a way of turning any quantified boolean formula into a Geography position of comparable size, so a fast solver for the family would be a fast solver for the formulas. That is a statement about the family and the encoding, and it is silent about any particular position.

It is also silent about the rest of the subject. Nim is in the same subject, is played on the same kind of object, and is settled by one pass over the input at any size whatever. So is Cutcake. So is green Hackenbush. The theorems that make those easy are not evasions of the hardness result; they are what a hardness result leaves room for.

Three families with a shortcut, and what each shortcut is #

Nim. The nim-sum: the exclusive or of the heap sizes, one operation per heap. The player to move wins exactly when it is not zero. The work is linear in the number of heaps and does not depend on their sizes at all — a heap of $2^{40}$ costs the same as a heap of three.

Green Hackenbush. Fusion and the colon principle: find the edges lying on no cycle, fuse everything else, count loops modulo two, run one recursion up what is left. The work is linear in the edges, which is a different promise from Nim’s and worth drawing on its own.

Cutcake. Every value is an integer, and the integer is decided by the binary expansions of the two side lengths — so an $m \times n$ cake is settled by looking at two numbers rather than by cutting anything. That every value is a whole number is itself the shortcut: a game whose positions are all cold has nothing to fight over, so the only question is how many spare moves one player has, and counting spare moves is arithmetic.

And one without #

Domineering has the shortest rule of the four. Left places a vertical domino, Right a horizontal one, and a player who cannot place loses. That is it.

Nobody has found a closed form for it. The values of small boards are irregular — switches, infinitesimals and worse — with no visible pattern, and the only way to the value of a board is to evaluate every position on it.

The counts are the point. A $2 \times 3$ board is 18 positions and a $4 \times 5$ board is 58,830 — and $4 \times 5$ is still a board somebody could draw on the back of an envelope. The published solutions for Domineering run to boards of around $10 \times 10$ and required substantial computation for each.

Two questions that are not the same question #

There is a distinction buried in the last two sections that deserves its own heading, because conflating the two is the commonest way to misread a complexity claim about games.

Who wins? is one question. What is the position worth? is a different and generally harder one. For an impartial game the second means finding a Grundy value; for a partizan game it means finding a canonical form, which is a tree rather than a number.

Nim answers both cheaply — the nim-sum is the value and its being non-zero is the answer. But the two come apart quickly. Deciding the winner of a sum of positions whose values are known is trivial: add the values. Computing those values is where all the cost is, and that is why decomposition matters so much — it is the operation that turns one expensive question into several cheap ones.

That is worth a sentence on its own, because it is where the closed forms above are actually spent. Four components with values already computed add in one step, whatever they are; the expensive work happened once per part rather than once per combination, so a board with $k$ regions has exponentially many combined positions and only $k$ things to evaluate. Putting positions side by side and adding their values is the operation the whole subject is built on, and it is free.

So the cheapness of the closed forms on this page is not really about who wins. It is about values, and about the fact that a value computed once can be reused in every position that contains that component.

Why the rules being short does not help #

That the hard family has the shortest rule is not a coincidence to be shrugged at, and it is worth saying what is actually going on.

A short rule generates a large state space when its moves interact. Domineering’s dominoes interact: a vertical placement removes two squares from every horizontal placement that would have used either of them, so the board does not fall into independent parts until late in the play. Nim’s heaps do not interact at all — a move in one heap leaves the others exactly as they were — which is precisely the condition under which the disjunctive sum theory applies and a value can be computed part by part.

So the real distinction is not rule length or board size. It is whether the position decomposes, and how early.

Green Hackenbush is the instructive middle case. It does not decompose on the board — the edges are all tangled together — but a theorem decomposes it, by proving that every cycle can be collapsed. The shortcut is not something a reader could see in the picture; it had to be found and proved, and then it made a hard-looking family easy.

The lattice in the first figure is the clearest illustration. Twelve edges, every one of them tangled with the rest, 1,283 reachable positions — and the structural rule reads the answer off in twelve steps without looking at a single one of them. Nothing about the drawing suggests that is possible, and a solver that did not know the theorem would have no way to discover it while searching.

A shortcut may exist and be undiscovered #

Nothing in the counts distinguishes “no closed form exists” from “no closed form has been found”, and the essay will not pretend otherwise.

Domineering is not known to be hard as a family. There is no reduction from anything to it. What is known is that nobody has found a rule, that the values look irregular, and that computation is the only route anybody has. That is an entirely different epistemic situation from Generalised Geography, where hardness is proved.

That is the honest picture. The subject contains a proved hardness result, a handful of proved shortcuts, and a large middle where the answer is “somebody is still computing”.

It is worth adding what would count as settling one of the middle cases, because it is not obvious. A closed form for Domineering would be a rule assigning a value to every board in time polynomial in the board’s dimensions; a hardness result would be a reduction turning some known-hard problem into a Domineering position of comparable size. Neither has been produced. What exists instead is a table of computed values with no pattern in it, which is evidence for nothing in particular — the octal games in the figure above spent decades looking exactly that way before their periods appeared.

The asymmetry is what makes the middle uncomfortable. A shortcut can be found by anybody at any time; the absence of one can only be established by a proof of hardness, which is a much harder thing to produce and which nobody has any idea how to produce for most of these games.

The three shortcuts are not easy in the same sense #

The essay opens by saying hardness is a property of a family and its encoding, and then lists three easy families without asking which encoding each is easy in. They differ, and the difference is the sharpest thing on this page.

Nim is easy on a succinct input. Three heaps of $2^{40}$ are written as three numerals of forty bits, and the nim-sum is forty bit-operations per heap. The work is polynomial in the length of the input, not in the number of counters — which is exponentially smaller. That is the strongest form of easiness available: the answer is cheap even when the object is astronomically larger than its description.

Cutcake is the same. An $m \times n$ cake is two numerals, its value is decided by their binary expansions, and nobody cuts anything. A cake of $2^{40}$ by $2^{40}$ is settled as fast as a cake of three by four.

Green Hackenbush is not, and does not have to be. Its input is a graph, written out edge by edge, and the shortcut is linear in the edges. That is polynomial in the input because the input already is the object — there is no compressed way to write a graph down that the algorithm is beating.

So two of the three shortcuts are beating an exponential and the third is not being asked to. Both are worth having and they are different achievements: one says the game’s answer does not depend on the size of the position, the other says it depends on it only linearly.

Which means the Domineering question has two versions #

That distinction lands directly on the essay’s own account of what would settle Domineering, and it makes the account ambiguous in an important way.

A rule assigning a value to every board in time polynomial in the board’s dimensions. Polynomial in $m$ and $n$ — or polynomial in the number of bits it takes to write $m$ and $n$? A board of $m \times n$ has $mn$ squares, so the two demands differ by an exponential, and which one is being asked changes what a positive answer would mean.

The written-out version. Give the algorithm a board of $mn$ squares and ask for the value in time polynomial in $mn$. That would be a real result and it would be the weaker of the two: the input is already as large as the board.

The succinct version. Give it $m$ and $n$ as numerals and ask for the value in time polynomial in their digits. That is what Nim and Cutcake do, and it is the version a reader has in mind when they notice that a $10 \times 10$ Domineering board needed substantial computation while a Nim heap of $10^{100}$ needs none.

Nobody has either. But the two are different targets and the gap between them is exactly the gap between a position and how it is written down — the same observation that makes “Nim is easy” a claim about binary numerals rather than about counters.

And it says which of the three easy families Domineering is being compared with. Against green Hackenbush the comparison is fair and Domineering simply lacks a theorem. Against Nim and Cutcake it is not: those two answer a succinctly-posed question succinctly, and a rectangle of dominoes may have no such answer for reasons that have nothing to do with anybody’s ingenuity — the value of an $m \times n$ board could be genuinely irregular in $m$ and $n$ while being perfectly computable from the written-out board.

That is worth separating because it splits the open problem in two. One half might be settled by a better search and a pattern; the other would need the values to have arithmetic structure in the dimensions, which is a much stronger property and one no measurement on this site has looked for.

What can be measured is the shape of the search that stands in for both.

What the solver computed, and how #

The position counts are counts, not estimates. Each family’s solver is the ordinary memoised recursion with the memo table’s size read off at the end.

For Nim, positions are sorted heap lists and a move takes any number from one heap. For Domineering, positions are bitmasks of occupied squares and the solver walks every placement by either player. For green Hackenbush, positions are bitmasks of surviving edges with the disconnected ones dropped after each cut.

The “steps” column is the work the closed form does, stated in the units the closed form is stated in — one exclusive-or per heap, one pass over the edges. Where no closed form is known the entry is absent and the figure says so rather than filling it with a number.

The two columns are only comparable because the green Hackenbush family is checked both ways: greenValue computes the answer by search and by the structural rule and refuses to return anything if they differ, over all ten graphs and 1,438 positions in total. Without that, the figure would be two columns of numbers with nothing tying them to the same question.

The bars are logarithmic because the counts span four orders of magnitude, and a linear scale would draw every row but one as a line of zero width — hiding exactly the thing being shown.

Where the model stops #

The sizes are small. The largest Domineering board here is $4 \times 5$. The point of the figure is the shape of the two columns, and a family run to a size where the difference is spectacular would take longer to draw than the figure is worth.

“Steps” is a rough unit. One exclusive-or and one pass over an edge list are not the same amount of work, and the column does not pretend they are. What it distinguishes is a cost that grows with the input from one that grows with the state space, which is the distinction the essay is about.

Nothing here is a lower bound. Counting the positions an exhaustive solver visits says what this algorithm costs, not what the problem costs. A cleverer Domineering solver — alpha-beta, transposition tables, symmetry reduction — visits far fewer, and the published solutions use all of those. The column is an upper bound on the difficulty and an honest measure of the naive route.

Memoisation is doing a lot of the work already. The counts are of distinct positions, so a solver without a memo table would visit vastly more. Even the “naive” route in this figure is using the single most important optimisation there is.

Space is not counted at all. The complexity class in the hardness result is PSPACE — a statement about memory — and every number on this page is a count of positions visited, which is closer to a statement about time. The two are related for these games and are not the same, and a solver that visits 58,830 positions must also find somewhere to keep them if it is going to memoise. That is the resource the hardness result is really about, and this essay measures the other one.

Who found it, and when #

Bouton solved Nim in 1901. The Sprague–Grundy theorem is from 1935 and 1939. Fusion and the colon principle are in Winning Ways (1982), as is Cutcake’s integer-valued table. Every shortcut on this page is at least forty years old, and each one converted a family that had looked like a search problem into one that is a calculation.

The hardness results came later and from a different community. Even, Tarjan and Fraenkel established PSPACE-completeness for Generalised Geography and its relatives in the 1970s and 1980s, and the technique — reduce a quantified boolean formula to a game — has since been applied to dozens of games.

The two lines of work read as opposites and are not. Both are answers to the same question about a family, and a subject with only one of them would be much less interesting: all shortcuts and it would be arithmetic, all hardness and there would be nothing to compute.

The gap in dates is worth noticing too. Every shortcut here was found by people looking for structure in a particular game, decades before anybody had a vocabulary for saying that a family is hard. The hardness results did not close off that search; they described where it can and cannot succeed, and left the individual games exactly where they were. Domineering was unsolved before Even and Tarjan and is unsolved now, and their theorem says nothing about it at all — which is the most useful thing to hold on to when reading a complexity claim about games.

Where the ladder goes next #

This is the third rung on the complexity ladder, after what an exact evaluator can and cannot reach and the reduction that proves the hardness. Those two describe the ceiling; this one describes the floor, and the large gap between them.

The next rung is about the middle of the gap: what a shortcut costs to find. A period in an octal game’s Grundy sequence is a closed form, and finding one has taken decades of computation for some codes and has never succeeded for others — so “does this family have a shortcut?” is itself a question with a computational cost, and one that nobody knows how to bound.