Complexity — the series · Combinatorial Game Theory

Which questions are answerable. The theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space.

How hard is it

Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.

part 1 · complexity

A formula, drawn as a game. A token on a directed graph. A move slides it along an edge to a vertex not yet visited, and a player who cannot move loses. That is the whole game, and deciding who wins it is as hard as anything decidable in polynomial space — which is the strongest hardness claim anybody makes about a combinatorial game.

Hard, proved

A game is as hard as a logical formula when the formula can be drawn as the game. Here is the drawing — a quantified formula turned into a graph with a token on it — with every formula over three variables played both ways and required to agree.

part 2 · complexity

What it costs to decide the winner. Three families of game, each at several sizes, with the number of distinct positions an exhaustive solver must evaluate beside the work its closed form does. The bars are logarithmic. Hardness is not about the size of the board or the length of the rules — Domineering has the shortest rule here — it is about whether anybody has found the shortcut.

The game with the shortest rule is the hard one

Deciding a generalised board game is PSPACE-complete, which is a statement about families and encodings rather than about size. Nim in the same subject is settled by one pass over the input at any size, and green Hackenbush by one pass over the edges — while Domineering, whose rules take a single line, has no shortcut anybody has found.

part 3 · complexity

The same position, and two rulers to measure it with. Nim positions with the length of their input under two encodings — the heap sizes in binary, and the counters themselves — beside the work the nim-sum does. The work never changes. Which of the two lengths it is compared against decides whether the same algorithm reads as linear or as exponentially fast, and hardness claims are always made against one particular encoding.

Nim is easy, in binary

Three heaps of a thousand counters take thirty bits to write down and three thousand counters to lay out. The nim-sum does three exclusive-ors either way. Whether that counts as fast depends entirely on which of the two numbers the work is compared against.

part 4 · complexity

A winning strategy on 3×3, drawn whole. The whole of one player's winning strategy on a small Domineering board: their own move at each of their turns, and every reply the opponent has at each of theirs. The strategy branches only where the loser chooses. Its size is what somebody would have to be handed to check the claim that this player wins, and it is far larger than the claim itself.

"Left wins" has no short proof

A complete solution of Nim on heaps of 7, 11 and 13 is 480 table entries. A winning strategy for the same position — one move of the winner's at each of their turns, and an answer to every reply — has 56,167,022 nodes in it. The answer is smaller than the proof by a factor of a hundred thousand.

part 5 · complexity

One node per route, one node per position. For each board, the number of nodes in the recursion tree a solver with no memo table would walk, beside the number of distinct positions that tree contains, beside the longest run of moves in it. The first number is the cost of forgetting; the second is the size of the table that avoids it; the third is the stack, and it stays small however the other two grow.

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

A 4×4 Domineering board has 6,257,129 routes through it, 5,700 distinct positions, and a deepest line eight moves long. Those three numbers are three different resources, and the smallest of them is the one that gives games their complexity class.

part 6 · complexity

Three things the word “solved” is used for. The three standard senses of a solved game, priced on positions this solver can settle completely. Ultra-weak names the winner; weak supplies a strategy from the opening; strong supplies one from every position. They differ by orders of magnitude, and a claim that a game is solved is nearly useless until it says which of the three it means.

Three different claims are all called solved

Hex is solved in the sense that the first player provably wins, by an argument that names no move whatever. Nim is solved in the sense that a formula gives the right move from any position at any size. Between them sit strategies for one opening, and databases of a few billion positions. The word covers all four.

part 7 · complexity