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 5 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

Named alongside it

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

PSPACEComplexityExhaustive searchImpartialCertificatePosition graphIntractableNormal playQuantified Boolean formulaReductionAlternationCounterexample

All concepts