Combinatorial Game Theory
who wins, and by how much
Series

Geography — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · impartial
  2. 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.

    part 2 · complexity
  3. 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.

    part 3 · complexity
  4. 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.

    part 4 · complexity

All series