A token on a graph

Almost every impartial game on this site is a collection of heaps. Nim is heaps; octal games are heaps with a rulebook; subtraction games are heaps with a list. Geography is not.

A token sits on a vertex of a directed graph. A move slides it along an edge to a vertex not yet visited, and a player with no such edge loses. The position is therefore not the vertex: it is the vertex together with the set of vertices already used, which is why a graph of ten vertices has ten thousand positions and not ten.

Why the history has to be part of the position #

The rule “not yet visited” is one clause and it changes what kind of object the game is.

In Nim the position is the heap sizes and nothing else: how the heaps got that way is irrelevant, and a solver may memoise on the sizes safely. In geography the token’s vertex is not enough, because the moves available from it depend on which vertices have been used up — and two games that arrive at the same vertex by different routes are genuinely different positions with, in general, different values.

That is the difference between a game whose state is a configuration and one whose state is a configuration plus a history. The second kind is not rare — chess has one in its repetition rule, Go has one in its ko rule — but it is rare on this site, because almost every game here was chosen for having a state a figure can draw.

The practical cost is the size of the state space. A graph of $n$ vertices has $n \cdot 2^n$ positions rather than $n$, and the exhaustion in the hero figure walks a few hundred of them for six vertices. At twenty vertices it would be twenty million, which is still small; at sixty it is beyond anything, and the hardness result says no cleverness rescues the general case.

The value is a value of a position, not of a vertex #

This is the point at which “the Grundy value of a vertex” becomes a phrase to avoid. The recursion is the usual one —

$$\mathcal{G}(v, S) = \operatorname{mex}\{\, \mathcal{G}(u, S \cup \{u\}) : v \to u,\; u \notin S \,\}$$

— and the second argument is what makes it a different subject from heaps. The same vertex carries a different value at different points of the same game, because the graph the token can still reach has shrunk.

That is not a technicality about implementation. It is why the identification a solver makes matters here more than anywhere else on this site: two states with the same vertex and different histories are different positions, and a solver that memoised on the vertex alone would give confident wrong answers.

Games with a board have symmetries to exploit, and treating positions that a reflection or a rotation carries into one another as the same position is what makes a search over a grid affordable. Geography has almost none of that to sell. A relabelling of the vertices is a symmetry of the graph and very little else is, and the visited set destroys even those the moment the token has moved twice, because two states with the same vertex and different histories differ in exactly the part a symmetry would have to preserve. So the state space stays near its worst case of $n \cdot 2^n$, and the saving a solver would like is unavailable — which is a fact about the game rather than about the solver.

What the values are good for here #

A Grundy value is a promise about sums, so the natural check is what a geography position does when something is added to it.

Nothing in the Sprague–Grundy theorem mentions heaps. It says any impartial position under normal play equals a Nim heap, found by the mex rule over its options — and the proof never inspects what the position is made of. A token on a graph qualifies exactly as a row of counters does.

So the labels in the hero figure are directly usable: a graph whose start has value $\ast 2$, beside a Nim heap of two, is a second-player win, and the two components are one game. A board made of three disjoint graphs is the exclusive or of their three values.

What is not transferable is the search. Computing the value of a geography position costs a walk over its state space, and unlike a heap there is no formula to shortcut it — which is why the essay’s second half is about the case where a formula exists.

The same edges, without arrows #

Now delete the arrows. A token on an undirected graph, a move along any edge to a vertex not yet used, a player with no such edge loses.

The game looks harder if anything — more moves, more branching. It is not: it has a criterion, and the criterion has nothing to do with searching.

The first player wins undirected vertex geography exactly when every maximum matching of the graph covers the starting vertex.

The strategy behind the criterion is the pleasure of it. If every maximum matching covers the start, the first player moves along the matched edge from the start; whatever the opponent does, the vertex they move to is matched, and following matched edges is always available. If some maximum matching misses the start, the second player uses that matching the same way. The whole game is a walk along alternating matched and unmatched edges — which is exactly the object augmenting-path arguments are made of.

Those two graphs are drawn in full because a figure can hold them entire. The criterion is checked on more than them, and the wider check is below.

The strategy behind the matching, at length #

The criterion deserves its proof sketch, because the strategy is short and completely explicit — the opposite of what the directed game offers.

Fix a maximum matching $M$. Suppose the start $v$ is covered by every maximum matching, and let the first player move along $v$’s matched edge to $u$. Now suppose the opponent could move from $u$ to some unmatched-from-$u$ vertex $w$ with the play continuing; the trail so far, extended, would be an alternating path, and an alternating path from a matched vertex to an unmatched one is an augmenting path — which would produce a larger matching, contradicting maximality.

So the first player’s rule is: always move along the matched edge. The rule is available every time, because the vertex just arrived at is matched, and the game ends when the opponent has no move — which is a loss for them.

If instead some maximum matching misses $v$, the second player uses that matching by the same argument, and the first player’s opening move lands on a matched vertex.

Two things are worth noticing about that. The strategy is stateless — it consults the matching and the current vertex, not the history — even though the game’s positions are histories. And the same matching works from the beginning to the end of the game, so the whole strategy is computed once.

What the arrow costs #

The two games differ in one word of the rules, and everything about their difficulty is in that word.

Undirected geography is decided by a matching, and a maximum matching can be found in polynomial time — so the game has an efficient winner-decider even on graphs no search could touch.

Directed geography is PSPACE-complete. The reduction from quantified boolean formulas turns a formula into a graph on which the game’s winner is the formula’s truth value, so a fast algorithm for the directed game would be a fast algorithm for every problem solvable in polynomial space.

That gap is the sharpest statement this site can make about what a rule is worth. Both games have the same board, the same token and the same losing condition; one of them is a matching problem and the other is complete for polynomial space.

Eight graphs, and what each one shows #

The graphs the criterion is run on are chosen to make it do different work, and they are worth reading as a set rather than one at a time.

A path of four has a perfect matching, so every vertex is in every maximum matching and every vertex wins. A path of five has three maximum matchings of two edges each; the two interior even-numbered vertices are covered by all of them and win, and the three odd ones are missed by at least one and lose. That is the alternating structure of a path, visible directly, and it is the graph drawn above.

A star of five has four maximum matchings of one edge, and only the centre is in all of them: the centre wins, every leaf loses. A player at a leaf has one move, to the centre, and then the opponent is at a matched vertex with the whole star still available.

A cycle of four has two perfect matchings, so every vertex is covered by both, and every vertex wins. A cycle of five has five maximum matchings of two edges, each missing a different vertex, so no vertex is in all of them and every vertex loses.

That pair is the sharpest of the eight. Two cycles, one vertex apart in size, with opposite answers at every vertex — and the reason is nothing about the game and everything about whether a cycle of that length has a perfect matching.

A kite — a triangle with a two-edge tail — is the one that would be hardest to guess, and the criterion gets it. Its maximum matchings have two edges, and exactly one vertex is in all of them: the middle of the tail. Four of its five vertices lose, including all three of the triangle. Two triangles joined by an edge goes the other way entirely: six vertices, a perfect matching, and so every vertex wins, even though the graph is built out of two odd cycles that separately have none. A tree of seven splits five and two, its two losing vertices being leaves that hang off the same branch point. Across all eight, forty-one vertices, no disagreement.

The criterion quantifies over exponentially many matchings and does not need to #

There is a gap between the criterion as stated and the criterion as an algorithm, and closing it is what makes “polynomial time” a fair description.

Every maximum matching of the graph covers the starting vertex names a set that can be enormous — a graph on $n$ vertices may have exponentially many maximum matchings, and the figures above check the condition by listing them, which is honest at six vertices and is not a method.

The condition has a two-line reformulation. Write $\nu(G)$ for the size of a maximum matching. Then

$$\text{every maximum matching covers } v \quad\Longleftrightarrow\quad \nu(G - v) < \nu(G),$$

because a maximum matching missing $v$ is exactly a maximum matching of $G - v$ of the full size, and conversely. So the test is two matching computations, and matching is polynomial, so the whole criterion is.

Both halves are computed here, and they are computed by different code. The two graphs drawn in full get their verdicts from an enumeration of every maximum matching; the family gets its verdicts from the deletion test, which never lists a matching. The path of five appears in both and comes out the same way twice — a win from its two interior even vertices, a loss from the other three.

That is worth separating from the criterion itself, because the essay’s figures verify a statement and the complexity claim rests on an algorithm, and the two are not the same object. What the six graphs establish is that the statement is right; what makes the undirected game easy is the reformulation, and nothing on this page computes it that way.

Which is really a statement about certificates #

Read that way, the gap between the two games stops being about search and becomes about what can be written down.

The undirected game has a short certificate. A maximum matching is $n/2$ edges, a person can check in a moment that it is a matching, and the reformulation above turns “is it maximum, and does it miss $v$” into more of the same. So the answer to who wins comes with an object of polynomial size that settles it, and the winner’s strategy is that same object used as a lookup table — stateless, consulted once per move, valid from the first move to the last.

The directed game has none anybody knows. Its winning strategy is a subtree of the position graph, and a strategy is not a certificate precisely because such subtrees are exponential. Nothing smaller has been found, and the PSPACE-completeness says nothing smaller is expected.

So the arrow does not merely make the search harder. It removes the possibility of a short answer, and the difference between the two games is the difference between a winner who can show why and a winner who can only win.

That also explains the strangest feature of the undirected result — that a game whose positions are histories is settled by a rule that never looks at the history. It is not that the history turns out to be irrelevant to the game; it is that a matching is a certificate for the whole game at once, and a certificate for the whole game does not have to be consulted per position. The history is still doing work in the position; it has simply been priced into an object computed before play began.

Geography as a summand #

The Grundy values are worth computing rather than merely the outcomes, because a value is what makes a position usable in a sum. A geography position with value $\ast 2$ can be added to a Nim heap of 2 and the sum is a second-player win — the token on the graph and the counters on the table are one game, and the Sprague–Grundy theorem does not care that one of them is a graph.

What the solver computed, and how #

Three routines, all exhaustive.

The outcome is backward induction over states, memoised on the pair (vertex, visited set), with the visited set carried as a bitmask. The Grundy value is the same walk with mex where the disjunction was — one line different, and the difference between “who wins this” and “what is this worth”.

The matchings are got two ways. For a graph drawn in full, every subset of the edges is walked and the maximum matchings are listed, so the criterion becomes a count: how many of them cover the starting vertex, against how many there are. For the family it is the deletion test instead — a memoised search over vertex subsets for the size of a maximum matching, run once on the graph and once on the graph without the vertex. Nothing in either version consults the game, and nothing in the game consults the criterion; they are compared afterwards.

Where the model stops #

The graphs are small. Six vertices for the drawn one, five or six for the undirected cases, and every one of them chosen so that a figure can show the whole graph rather than a sample of it. The state space is $n \cdot 2^n$ and the matching enumeration is $2^{|E|}$, so both halves are affordable only at this size — and the point of the essay is a comparison of criteria rather than a demonstration of scale.

The matching criterion is quoted as a theorem and tested as an instance. Forty-one vertices agreeing is not a proof; the theorem is Fraenkel, Scheinerman and Ullman’s, and the sketch of the strategy above is the argument, not a substitute for it.

Nothing here is a claim about edge geography. Deleting an edge rather than a vertex is a different game with a different theory, and the criterion above says nothing about it.

The matchings are still not found in the sense the theorem means. The criterion is fast because a maximum matching can be found in polynomial time by an augmenting-path method; neither routine here is that. One walks every subset of the edges and the other memoises over vertex subsets, and both are exponential in the worst case and entirely adequate at seven vertices. Nothing in the essay’s numbers depends on the algorithm used, and nothing in it demonstrates the speed the criterion is famous for.

And “polynomial” is not this site’s word. Cost belongs to a different subject, and what is claimed here is only the contrast the two games make: one of them has a criterion that does not search, and the other is complete for a class no criterion of that kind will settle.

Why the contrast is the essay #

A reader could take the hardness result alone and conclude that geography is hard, full stop. The pairing is what makes it informative.

Two games, same boards, same token, same losing condition. One of them is settled by a construction from matching theory that a person can carry out on paper; the other is complete for polynomial space, which means an efficient method for it would be an efficient method for every problem a polynomial amount of memory can decide.

The difference is that an arrow makes the graph’s structure directional, and the alternating-path argument — the whole basis of the matching criterion — needs to walk edges in both directions. Delete the symmetry and the argument has nothing to stand on.

That is the shape this site keeps finding, in the colouring games where one word decides whether the values are cold, in Toads and Frogs with and without the jump, and here. A rule is not a detail of a game; it is most of what the game is, and the way to show that is to hold everything else fixed and change one clause.

Where the ladder goes next #

The obvious rung is the game with edges deleted instead of vertices — edge geography, whose directed version is also hard and whose undirected version is, surprisingly, not the same problem as this one. The other direction is the sum: geography positions are impartial and have Grundy values, so a board made of several disjoint graphs is a single game, and the values of the components are all a player needs.