Combinatorial Game Theory
who wins, and by how much
Concept

Reduction — where it appears

Removing dominated and reversible options from a position, which changes its form and never its value. Deleting removes exactly one option and bypassing can add several, so the two halves of it behave nothing alike.

Named by 13 essays across 3 fields — each of them below, with the objects they name alongside it.

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.

complexity · 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.

complexity · Complexity The same game, written twice. A position as it arises and the same position reduced. Left would never move to −1 when 0 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form.

Canonical form

Two positions are worth the same when neither player can tell them apart inside any larger game. Deciding that could be an infinite search. Instead there is a normal form — delete what nobody would play, bypass what backfires — and equality becomes a comparison of two small trees.

values · Canonical form Every quantifier is a move. A quantified boolean formula with its quantifiers drawn as turns: an existential is a choice by the player to move, a universal a choice by the opponent. The same formula is put through the reduction to Generalized Geography and the two answers are checked against each other, so the prefix of quantifiers and the game beside it are one claim.

A puzzle asks once, a game asks alternately

Quantifier alternation is the whole difference between a puzzle and a game. One chooser is an existential and its answer is a witness somebody can check; two choosers taking turns is a prefix of alternating quantifiers, and the witness stops being an assignment and becomes a strategy.

complexity · Alternation The same game, written twice. A position as it arises and the same position reduced. Three of the options are dominated — a sibling is at least as good for the player who owns them — so they can go. The two games are equal — checked, not assumed — and the second is the canonical form.

Two hundred and fifty-six ways to write twenty-two things

Every game whose options come from the four born on day one — there are 256 of them, and between them they carry 22 values. The reduction that collapses one to the other has choices in it at every step, and uniqueness is the claim that none of the choices matters.

values · Canonical form Knowing who wins, and knowing what it is worth. Nine positions, each evaluated twice by an instrumented evaluator that starts with an empty cache. The third column counts what deciding the winner costs and the fourth counts what the canonical form costs, in the currency each question is actually paid in.

Knowing who wins, and knowing what it is worth

Deciding a winner expands positions. Computing a canonical form expands pairs of positions, because a comparison unfolds as a recursion over one subposition of each and the reduction makes many comparisons. Measured on the same nine positions by an evaluator that starts empty every time, the second costs between 1.3 and 279 times the first, and the ratio grows with the tree.

complexity · Value cost What the reduction collapses. Each reduced form with the values that reduce to it. The largest class is the one that reduces to zero and it holds every infinitesimal on the list, which is exactly what the reduction is for — against a hot background, none of them is distinguishable from nothing.

What is left when the small change is thrown away

Canonical form answers a demanding question: which positions are interchangeable inside every sum whatever. A player with a hot board does not have every sum — an infinitesimal difference cannot decide anything against a genuine fight — so there is a coarser question with an exact answer. The reduced canonical form takes the 1,474 values born by day three to 61, with 292 of them collapsing to zero, and it is a homomorphism on all 8,100 pairs tested only when a second pass is made.

sums · Reduced form The reduction that puts options back. How the two reductions change the width of a form. Domination only ever removes an option. Bypassing a reversible option substitutes the answer's whole option list, so it can leave the form wider than it started — and the finished canonical form can be wider than the form it came from.

The reduction that puts options back

Canonical form is presented as simplification, and half of it is. Deleting a dominated option takes one away. Bypassing a reversible one substitutes the answer's whole option list, so it can leave the form wider than it started — and 60 of 32,428 forms end up with a canonical form wider than they are.

values · Reversibility What deleting is worth on its own. The reduction split into its two halves and each measured. Deleting a dominated option removes exactly one option and can do nothing else; bypassing a reversible one substitutes an option list and can widen the form. The counts say how much of the reduction the monotone half accounts for.

The reduction that always shrinks

Canonical form is two reductions and they are not the same kind of operation. Deleting a dominated option removes one option and can do nothing else; bypassing a reversible one substitutes a whole option list. Over the 256 forms born by day two, deleting alone finishes 225 of them and accounts for 480 of the 520 options that come off — and the 31 it cannot finish are almost all the ones with a star in them.

values · Dominance One option list, as the order it is. The four options above, with an arrow from each option to every option it is at least as good as. Deleting keeps the one nothing points at and removes the rest, so the reduction takes three of them — a number read off the shape and not off the values.

How much a list of options can lose

Deleting a dominated option is the reduction with no surprises, and how many options it takes is decided by the shape of the order rather than by the values in it: the survivors are the maximal elements, and the count is the length of the list less the number of them. The essay separating the two reductions closed by predicting that the longest chain would give the number. It is a lower bound, exact on 3,859 of the 7,315 four-option lists and wrong on the rest.

values · Dominance How many options a value needs. The canonical form is the smallest form of its value, so the number of options it carries is a property of the value. Three days of the construction, with the widths that occur and the widest value of each.

How wide a form can get

Bypassing a reversible option replaces it with a whole option list, so a form grows in the middle of its own reduction. Whether it can come out wider than it went in is the question that leaves standing, and over 64,515 forms built from day-two options the answer is no, not once — the growth is real, it is transient, and the widest canonical form reached is exactly as wide as the widest form that reaches it.

values · Reversibility What a value costs to write down. Every one of the 1,474 values born by day three, grouped by the width of its canonical form, with the number of symbols the form takes when it is written out. Each count was obtained by walking the canonical form and counting its nodes, so a subposition appearing twice is counted twice — which is what writing it out does. The widest values of the day are not the longest to write.

What a value costs to write down

The canonical form is the smallest form of its value, and it is smallest in the one currency the reduction happens to spend: options. Counted in symbols it is nothing of the kind — the widest value born by day three is not the longest, the longest has six options rather than seven, and every canonical form on the day except the seven integers writes some position out twice.

values · Reversibility Which description of a surviving option is right. The two candidate readings of what the reduction keeps, scored over every Domineering option list on six boards. Taking the most room is right on under half the lists, which is what a description with no content scores on lists this short. Leaving the opponent fewest replies is right on nine in ten.

Which option the reduction keeps

Domination deletes an option when another is at least as good, so what survives is the top of an order. On a board that order is made of moves, and two descriptions of the surviving move suggest themselves. Over 1,586 Domineering option lists one of them is right 47% of the time and the other 90%, and the one that wins is not the one a player would guess.

values · Dominance

Named alongside it

The objects these essays reach for when they reach for this one.

Canonical formComparisonDominated optionExhaustive searchReversible optionUniquenessOption listAntichainBirthdayBorn on dayComplexityDomineering

All concepts