The plays do not say who chose them

Two graphs a rule cannot tell apart closed one line of repair and opened another. The line it closed was the idea that the matching criterion, which decides undirected geography when a move uses up the vertex it leaves, could be patched to decide the game in which a move uses up the edge it crosses by also reading the cycle. On every connected graph with one cycle up to six vertices, eleven such rules reach at most 91 of 114 starts, and a pair of five-edge graphs agrees on everything a rule of that kind could read and has opposite winners.

The line it opened was the one rule that had done better than the criterion. That rule was about trails — the walks the token can make without reusing an edge — and it was the loosest of the eleven, because it assumed the opponent would end the game as fast as possible. The obvious next object is the whole of what that rule was a shadow of. From any start, the game can end in a finite number of ways, each of them a trail that cannot be extended. Their lengths are a property of the graph and the start, not of anybody’s play. And the parity of each length says who made the last move.

So the question is whether the winner is a function of that list. If it were, the list would be a criterion of the matching’s own kind: something computed from the graph that names the winner without playing the game.

Two plays from each start, and a different chooser #

The list is easiest to see on the smallest pair it gets wrong, and the smallest pair is two trees.

On the left the graph is a path of six vertices, and the start is the third of them. The first player can walk towards the short end, where the game lasts two moves, or towards the long end, where it lasts three. On the right the start is a leaf, joined to a centre with two branches, one of one edge and one of two. From that start the game again lasts either two moves or three, so the multiset of trail lengths is {2, 3} on both sides.

A play of odd length is won by the player who began it, because that player makes moves one, three and five. So the list says that each start has one play the first player wins and one the second player wins. What it does not say is who picks the play. On the path the first player picks, at the first move, and picks the three-move trail. On the spider the first move is forced — a leaf has one edge — and it is the second player, standing on the centre, who picks, and picks the two-move trail. The same two plays, and opposite winners, because the fork between them belongs to different people.

That already settles the question the earlier essay posed. The list is not a criterion, and it fails where the matching does not: both graphs are trees, and on a tree the matching criterion is exact — the vertex game and the edge game are one game when there is no cycle to come back along, as using up the edges showed on every tree to six vertices. The criterion reads the path and the spider correctly. The list of every play from the start does not.

A near miss is not a criterion #

A pair of trees shows that the list is not a function of the winner. It does not show how close it comes, and it comes very close.

The census covers all 143 connected graphs on up to six vertices, one of each shape, and all 810 of their starts. For each start the winner is found by exhaustive search, and the start is filed under its multiset of trail lengths. A multiset that holds only wins, or only losses, is one a rule could read; a multiset holding both is a pair of starts no rule on the list can tell apart.

Eighteen of the 414 distinct lists hold both verdicts. A rule that named, for each list, whichever verdict is commoner under it would be right at 780 of 810 starts — 96 per cent, against the matching criterion’s 545. On the graphs with one cycle it would be right at 108 of 114, against 91 for the best of the eleven rules the earlier essay tried. So the list is much the most informative object tried on this game so far. It is also not enough, and not merely on the graphs where the criterion fails; one of the eighteen mixed lists is the pair of trees.

The row that repays a second look is the densest. From six independent cycles up the list decides every start, and those are among the graphs on which the matching criterion does worst — it is right at 35 of 59 starts with six cycles and 17 of 30 with seven. A dense graph has so many trails that its list is nearly a fingerprint: at six vertices and fifteen edges a single start has 289,920 of them. On a sparse graph the list is short, and short lists collide.

What the list forgets is who chose #

The trees make the defect plain, and it is worth stating exactly, because it says what a repair has to add.

A play of edge geography is a sequence of choices, alternately the first player’s and the second’s. The list records where each sequence ends and nothing about where it forked or whose turn it was when it did. Two game trees with the same leaves at the same depths have the same list, however differently the leaves hang from the branches — and the winner of a game is decided by the branches. The first player needs one branch at each of their turns that leads to a win, and every branch at each of the opponent’s turns. A list of leaf depths cannot say which quantifier applies at which fork.

There is one thing it can certify, and the census measures how much.

If some first move leads to a position all of whose plays have odd length counted from the start, the first player wins by making it, whatever follows: every play the opponent could choose ends on a move of the first player’s. That is a certificate in the sense a strategy is not a certificate uses the word — a short object that proves the verdict — and it is never wrong. It is also a reading of the list one move deep: the lists after each first move, checked for a list with no even entry.

On trees it certifies 32 of the 34 wins. On graphs with one cycle, 58 of 69; with two, 57 of 89; then 22 of 98 with three cycles and nothing at all from seven. The decline is the same fact as the census’s densest row, read from the other side. A dense graph gives the opponent many ways to go on, and a first move after which none of them ends badly for the first player is rare. The first player still wins most of those starts — six of the six on the complete graph — but by forcing the opponent’s choices several moves later rather than by making them irrelevant at once, and a statement about every play after one move cannot see that.

Keeping the choices one move at a time #

The defect has a natural repair, and it can be applied a little at a time. The list is the leaves of the game tree with the branching thrown away; keep a little of the branching and the list becomes a richer object.

Call the list the level-nought profile of a position. The level-one profile is the multiset, over the moves available, of the level-nought profiles of the positions those moves reach: for each first move, the list of plays after it. The level-two profile is the multiset of level-one profiles of the positions one move away, and so on. Each level keeps one more move of the tree’s shape, and a profile as deep as the longest game is the game tree itself, which decides everything because it is everything. The measurement is how early the profile decides, because that says how much of the tree’s structure the winner depends on.

The answer on these graphs is three. Eighteen profiles hold both verdicts at level nought, seven at level one, one at level two and none at level three. The best a rule could do climbs from 780 to 802 to 809 to all 810. The graphs have up to fifteen edges, so the longest game on them lasts fifteen moves; the lengths of the plays, with the shape of the first three moves kept, decide every start of every one.

On trees the repair takes one level. Every tree start the plain list confuses is separated as soon as the lists after each first move are kept apart, which is what the path and the spider need: on the path the start has two first moves with lists {1} and {2} after them, and on the spider one first move with list {1, 2}. Keeping a single move of choice is enough to tell who owns the first fork, and on a tree the first fork is where these two differ.

One cycle, and a move spent going round it #

Seven profiles survive one level, and every one of them is on a graph with a cycle. The smallest pair shows what the cycle adds.

Both starts are leaves, so the first move is forced onto the triangle, and both have six maximal trails, two of three moves and four of four. After the forced move the second player stands on a corner of the triangle with two ways on, and the lists of plays from there are equal as well: 2, 2, 3, 3, 3 and 3 counted from that corner, on both graphs.

The difference is the arrangement of the two pendant edges. On the left each of the other two corners carries one. Whichever way the second player goes round, the first player arrives at a corner with two choices: continue round the triangle or step off onto the pendant. One of them leaves the second player a single move and the other leaves none, and the first player takes the one that ends the game on their own move. On the right both pendants hang from one corner, and the second player has a move the left graph does not offer: go away from that corner, to the bare one, which forces the first player to walk the third side of the triangle into the crowded corner. That spends one move going round the cycle, and at the crowded corner every way on is a single edge, so the second player makes the last move.

That is the thing a cycle does in this game and a tree cannot. A trail can come back to a vertex by the other side, and the player who controls the order in which the sides of a cycle are walked controls the parity of everything after it. The lists after one move are the same because the same number of edges is left in each direction; they differ one move later because of who is standing where when the round trip ends.

The last pair, two moves deep #

One pair of starts in the whole census survives two levels of the profile, and it is worth drawing because it is where the reading stops being cheap.

Each start has three first moves. On both graphs two of them lead to a position with seven moves left on every play, and one leads to a position with plays of four and seven moves remaining. Every play is therefore either five or eight moves long, and a play of eight is the second player’s. On both graphs the balanced first moves lose, since every reply to them keeps the game at eight. The whole question is the unbalanced move — the one after which two plays are short.

On the left the first player makes it and wins: whichever of the two replies comes, the first player then has a move into the short part of the graph, after which every play that remains ends on the first player’s move. On the right the same move exists and loses. Both of the second player’s replies lead to a position from which the first player has only one move, and that move hands the second player a vertex with a choice between a short play and long ones — the choice the first player had on the left. The lists after the first move agree, the lists after each reply agree, and what differs is whether the reply is followed by a forced move — a fork on one graph and a corridor on the other, two moves deeper than either list can see.

A reading that has to look three moves into an eight-move game is a reading that is nearly searching it, and that is the honest summary of where the profile ends up.

A list longer than the search #

The profile is a property of the graph, as the earlier essay hoped. It is not a cheap one.

The search behind every verdict on this page stores a state for each pair of a vertex and a set of spent edges it visits, and from every start of every graph on six vertices that comes to 148,362 states. Listing the maximal trails from the same starts means walking every path of the game tree to its end, which comes to 2,421,824 — sixteen for every state the search looks at. At five vertices the two are within a third of each other, so the gap opens exactly where the graphs get interesting.

The reason is the one a position reached eleven ways is one position measures on Domineering and Nim. A search keyed on the state finds a position once however many routes lead to it; a list of trails is a list of routes. The complete graph on six vertices has 289,920 maximal trails from one start, and the search visits 6,016 states to decide it. So the list is not a shortcut to the winner. It is a more expensive description of the same tree, with the part that decides the winner removed, and each level of the profile puts back some of what was removed at a price.

That is what the earlier essay’s closing sentence anticipated: a negative answer would settle where the remaining work is, in the search. It settles it more sharply than a bare negative would. The list is close enough to right that a reader might trust it, it is wrong on the smallest trees, and making it right means keeping the shape of the tree, at which point the search is the cheaper way to hold the shape.

What the census cannot show #

Six vertices is the range. There are 143 connected graphs within it and the counts are exact there. That three levels suffice is a statement about those 810 starts. On larger graphs the game can run longer and the corridors that hid the last pair can be longer too, and nothing here says whether some fixed level suffices for every graph. The expectation from what is known is that none does: the undirected edge game is complete for polynomial space, a result of Fraenkel, Scheinerman and Ullman in 1993 that how hard is it sets in context — hard, proved draws the reduction for the directed game — and a fixed-depth reading of the list would be a strange thing for a complete problem to have. That is an expectation and not a proof, and the census does not test it.

The profile is one way of keeping the choices. It keeps the multiset of subtrees’ lists at each level, which is a natural refinement and not the only one. A reading that recorded, say, the parity of the depth of each fork, or the number of forks on each trail, might separate starts earlier or later, and none of those is scored here.

And the certificate is a single sufficient condition. A first move after which every play is odd is proof of a win; a win without such a move is not a failure of anything, only a win proved some other way. The certificate’s decline with density is a measurement of that one condition, not of how hard the wins are to prove in general.

The convention the census is run under #

Normal play: the player who cannot move loses, which here means the player to move when every edge at the token’s vertex has been used. A move crosses an unused edge and uses it up; vertices may be revisited by another edge, which is the whole difference between this game and the vertex game, and the difference that disappears on a tree.

A maximal trail is counted as a sequence of edges from the start, so two trails that use the same edges in a different order are two trails, and the multiset has one entry for each. That is the object that corresponds to the plays of the game: two different orders are two different games, even when they end in the same place. Its length is the number of moves in the play, and an odd length is a win for the player who moved first.

The graphs are connected, undirected and simple, one of each isomorphism class, with every vertex tried as the start. The winner at each start is the exhaustive search the earlier geography essays use, and every profile is compared against it rather than against any rule.

The surprise: the matching knew who chose #

The most striking thing on this page is the pair of trees, and it is striking for what it says about the matching criterion rather than about the list.

The list of every play from a start is, by construction, everything that can happen. It records every ending the game can reach and how long each takes, and on the two trees it is identical. The matching criterion records none of that. It asks whether every maximum matching of the graph covers the starting vertex, which is a question about pairs of vertices and says nothing about plays, turns or endings. And the criterion gets both trees right.

The reason is that a maximum matching is a strategy in disguise, in the way a winning strategy that is a spanning tree finds a structure of the board doing duty for a rule of play. The player who wins the vertex game does so by always moving along a matched edge, so that the opponent is always the one who has to find an unmatched edge and cannot; the matching assigns every edge an owner, which is exactly the information the list throws away. On the path, the start is covered by every maximum matching and the first player’s matched edge points down the long branch; on the spider there is a maximum matching that leaves the leaf uncovered, and the second player’s matched edge at the centre points down the short one. The criterion is a picture of who chooses, and the list is a picture of what is chosen. Only the first decides a game.

Still open: whether three moves is a constant #

The census ends with a number, and the number is the question. Three levels of the profile decide every start on graphs to six vertices, while the longest game on them runs fifteen moves. If three were a constant of the game — if some fixed depth of the tree’s shape always sufficed — the undirected edge game would have a reading far cheaper than its search, which the hardness result makes very unlikely. So the level needed must grow, and the measurement that would say how is the same census on seven vertices, where there are 853 connected graphs and the complete graph alone has more trails from one start than the whole of the six-vertex census.

That census is out of reach by listing, for the reason the cost table gives, and within reach by computing the profiles directly on the states rather than on the routes: a profile of a position depends only on the position, so the search’s own table can carry it. What it would report is the depth at which the last ambiguous pair on seven vertices separates, and whether that pair looks like the one drawn here — a fork on one graph and a corridor on the other, a move or two deeper than the profile can see. A token on a graph is where the whole family began, and where a search may stop is the other place in these essays where the question is how deep a reading has to go before its verdict can be trusted.