Combinatorial Game Theory
who wins, and by how much
Concept

Generalized Geography — where it appears

A game of moving a token along a directed graph, deleting what it leaves, used as the standard hard game in reductions. It reduces from quantified formulas in a way a reader can follow, which is why it is the standard hard game rather than merely one of them.

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

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 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 Generalized Geography. 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.

A token on a graph

Geography is an impartial game whose position is a vertex and a history, so a ten-vertex graph has ten thousand states rather than ten. Take the arrows off and the same game is decided by a maximum matching — first player wins exactly when every maximum matching covers the start, verified on 41 vertices across eight graphs. One word in the rules separates a polynomial criterion from a PSPACE-complete problem.

impartial · Geography Using up edges instead of vertices. An undirected graph of 4 vertices and 4 edges, with the winner at every start of two games on it: vertex geography, where a move uses up the vertex it leaves, and edge geography, where it uses up the edge it crosses. The matching criterion decides the vertex game everywhere and is right about the edge game at 0 of 4 starts.

Using up the edges instead

Undirected geography is decided by a maximum matching when a move uses up the vertex it leaves. Use up the edge it crosses instead and the matching is exact on every tree — on a tree the two games are one game — and on nothing else. Over every connected graph on up to six vertices it names the winner at 480 of 745 starts once there is a cycle, it gets a four-cycle wrong from every start, and the more cycles a graph has, the more of its misses are wins that are really losses.

complexity · Geography One cycle, and how much of it the criterion misses. The matching criterion for undirected geography put to the game where a move uses up the edge it crosses, on every connected graph up to 6 vertices with exactly one cycle. It is right at 77 of 114 starts, and at none of the six on the graph whose cycle has six vertices.

Two graphs a rule cannot tell apart

The repair proposed for the matching criterion was to read the cycle as well. Over every connected graph with exactly one cycle up to six vertices — 21 graphs, 114 starts — eleven such rules reach at most 91, and the winner is not a function of the matching, the cycle's length, the start's distance from it, its degree and the edge count together: six cells of that table hold both verdicts, the smallest a pair of five-edge graphs.

complexity · Geography The same plays, a different chooser. Two trees with a ringed starting vertex. From each start edge geography can end after 2 moves or after 3, so the multiset of maximal trail lengths is the same, but on the first the player to move chooses the long play and wins, and on the second the first move is forced and the opponent chooses the short one.

The plays do not say who chose them

Every way a game of edge geography can go is a maximal trail, and the parity of each trail says who moved last. So the list of their lengths ought to decide the game, and over every connected graph to six vertices it nearly does — 780 of 810 starts, 108 of 114 on one cycle, where no rule on the matching and the cycle reached 91. It still fails, and the smallest failure is two trees: the same two plays from each start, and a different player choosing between them. Keep that choice one move at a time and the ambiguity falls from eighteen profiles to seven, one and none. The list costs sixteen times the search.

complexity · Geography

Named alongside it

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

PSPACEExhaustive searchImpartialCertificateComplexityPosition graphCounterexampleEnumerationIntractableNormal playQuantified Boolean formulaReduction

All concepts