Combinatorial Game Theory
who wins, and by how much
Series

Geography — the series

3 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

All series