Combinatorial Game Theory
who wins, and by how much
Generator

Generalized Geography

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

6 essays call geography-graph. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

12 distinct positions, harvested by drawing the figure again at the options each essay asked for.

PositionWorth OutcomeDrawn in
undirected on 5 vertices and 4 edges, starting at a ∗0 P A token on a graph
undirected on 5 vertices and 4 edges, starting at b ∗1 N A token on a graph
undirected on 5 vertices and 4 edges, starting at c ∗0 P A token on a graph
undirected on 5 vertices and 4 edges, starting at d ∗1 N A token on a graph
undirected on 6 vertices and 5 edges, starting at a ∗0 P A token on a graph
undirected on 6 vertices and 5 edges, starting at b ∗2 N A token on a graph
undirected on 6 vertices and 5 edges, starting at c ∗0 P A token on a graph
undirected on 6 vertices and 5 edges, starting at d ∗2 N A token on a graph
undirected on 6 vertices and 8 edges, starting at a ∗1 N Hard, proved
undirected on 6 vertices and 8 edges, starting at b ∗1 N Hard, proved
undirected on 6 vertices and 8 edges, starting at c ∗1 N Hard, proved
undirected on 6 vertices and 8 edges, starting at d ∗2 N Hard, proved

Where it is called

Every one of these figures is a drawing of the same construction, so a correction to it corrects them all.

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. What it costs

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.

 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. What it costs

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.

 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. Impartial games

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.

 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. What it costs

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.

 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. What it costs

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.

 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. What it costs

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.

The whole library · The position index · The figures that play back