Game on simple finite graphs

Question

Consider the following game on graphs (no multiple edges, but graphs can be disconnected).

Players A and B alternate picking a vertex. After picking a vertex, a number is assigned to that vertex such that the number is the smallest non-negative integer that is not already assigned to its neighbours.

The game ends when all vertices have numbers assigned to them. The last player to make a move wins if and only if that vertex was assigned an odd number.

Even for path graphs (that is, $n$ vertices in a line, connected with edges), I have no idea for which $n$ the first player has a winning strategy.

Some computations suggests that the first player lose if $n=1, 2, 4, 5, 6, 7, 9, 11, 13, 15$. I don't find a hit in OEIS that seem to make sense.

Answer 1

The cycle graphs and path graphs are easily related, as far as winning vs. losing positions. Upon making the initial move in a cycle $C_n$ graph, it becomes equivalent for the opposing player to moving in a path $P_{n+1}$ where the first and last nodes are already numbered $0$ (and the $n-1$ nodes between are still unnumbered).

Indeed it is subsequently more efficient to represent the intermediate graph game states as a "union" of path subgraphs whose unnumbered nodes are disjoint. It is convenient to consider artificially adding nodes numbered $-1$ to the ends of otherwise unnumbered path graphs, so that every unnumbered node has exactly two neighbors, and this does not affect the outcomes of games.

That is, an initial path graph $P_k$ is equivalent to a path graph $P_{k+2}$ with first and last nodes numbered $-1$. The next move would number one of the $k$ unnumbered nodes, effectively dividing the game's graph into two paths, each with a zero at one end and a $-1$ at the other, or leaving a single stretch $P_{k+1}$ with a zero at one end and a $-1$ at the other.

In this fashion any intermediate game state for a cycle $C_n$ or path $P_n$ can be represented as a sorted collection of "components" that partition the unnumbered nodes in arrangements compactly specified by $p(a,b,k)$, where $a \ge b$ are numbers of the two endpoints of a path that otherwise consists of $k \gt 0$ unnumbered nodes between those endpoints.

Update:

Using these more compact "path" segments to represent the "board" (partially numbered graphs), symmetries/equivalences can be more efficiently recognized. Runs with fifteen unnumbered nodes now take about several minutes rather than the better part of a day.

A striking pattern emerges. The table below shows the winning or losing status of a single path segment path(A,C,K), having K yet unnumbered nodes between endpoints numbered A and C respectively:

(A,C)\K =  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |...even | odd |
=====================================================================
(-1,-1) :  L :  L :  W :  L :  L :  L :  L :  W :  L :...  W  |  L  |
( 0,-1) :  W :  W :  W :  W :  W :  W :  L :  W :  L :...  W  |  L  |
( 0, 0) :  W :  W :  W :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 1,-1) :  L :  W :  L :  W :  W :  W :  L :  W :  L :...  W  |  L  |
( 1, 0) :  L :  W :  W :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 1, 1) :  L :  L :  L :  W :  L :  W :  W :  W :  L :...  W  |  L  |
( 2,-1) :  W :  W :  W :  W :  W :  W :  L :  W :  L :...  W  |  L  |
( 2, 0) :  W :  W :  W :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 2, 1) :  W :  W :  L :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 2, 2) :  W :  W :  W :  L :  W :  W :  W :  W :  L :...  W  |  L  |

While columns for $k=1,\ldots,7$ contain a good bit of variation, longer paths seem to be exclusively winning for $k$ even and losing for $k$ odd, regardless of the endpoints. Computations have been done for all the endpoints shown up to $k=15$, and for "default" endpoints $a=c=-1$ with $k=16,17$ as well.

Some general results

Intuitively there should be some Nim-like rule for determining the winning or losing status of such collections of paths with numbered endpoints. So far I have only been able to prove the following easy lemma.

Suppose the game state $S$ can be expressed as the union of two subgraphs $S_1$ and $S_2$ such that no unnumbered node is shared by $S_1$ and $S_2$. If $S_1$ and $S_2$ are losing positions (i.e. for the player required to move next), and if both $S_1$ and $S_2$ have even counts of unnumbered nodes, then $S$ is a losing position (and also has an even count of unnumbered nodes, aka moves left).

The proof is easy. As the current player moves in $S_1$ or $S_2$, the opponent can responds with a perfect defending move accordingly. The updated game state is again a union of two losing positions with even numbers of moves left in each, unless such a pair of moves "finishes" $S_1$ or $S_2$, leaving only one unfinished subgraph with its losing position.

An immediate corollary to this is that if $S_1$ is a winning position with an odd number of moves left, and $S_2$ (disjoint from $S_1$ as to unnumbered nodes) is a losing position with an even number of moves left, then the "union" of $S_1$ and $S_2$ is a winning position. The proof is just to observe that after making a winning move in $S_1$, one is left with a losing position (either by the preceding lemma, or by exhausting $S_1$ leaving only $S_2$).

Answer 2

This is only a partial answer, mainly to add some observations which haven't been recorded but which don't fit neatly in comments.

General lemma

A vertex $v$ with $m$ edges will be labelled with a value at most $m$.

Proof: suppose the contrary. Then $v$ is labelled with a value greater than $m$, so its adjacent vertices must include among their labels all values from $0$ to $m$, so there must be at least $m+1$ adjacent vertices. But $v$ only has $m$ edges.

Corollary

If a vertex $v$ has $m$ edges, we can attach to the graph a vertex $u$ with label $(m+1)$ and the edge $(u, v)$. This does not affect the game-theoretic value of the position.

Proof: we were never going to label $v$ with a value of $(m+1)$ or greater, so $u$ is irrelevant to the labelling of $v$. And since it has no edges to any other vertex, it is irrelevant to the labelling of every other vertex.

Corollary for path graphs

Instead of adding additional vertices at the ends with label $-1$, as in hardmath's answer, we can add additional vertices at the ends with label $2$.

Note that this shows directly that path(A,-1,K) should have the same value as path(A,2,K), and there must be something wrong with his table. I get a table with a few disagreements:

(A,C)\K =  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |...even | odd |
=====================================================================
( 0, 0) :  W :  W :  W :  W :  W :  W :  W :  W :  L :...  W  |  L  |
( 1, 0) :  L :  W :  L :  W :  L :  W :  L :  W :  L :...  W  |  L  |
( 2, 0) :  W :  W :  W :  W :  W :  W :  L :  W :  L :...  W  |  L  |
( 1, 1) :  L :  W :  L :  W :  L :  W :  L :  W :  L :...  W  |  L  |
( 2, 1) :  L :  W :  L :  W :  L :  W :  L :  W :  L :...  W  |  L  |
( 2, 2) :  L :  L :  W :  L :  L :  L :  L :  W :  L :...  W  |  L  |

I do agree that it seems that for $n > 7$ all single-path positions are a win if there are an even number of unlabelled vertices, and a loss if there are an odd number. I suspect that it may be possible to prove this by induction with a sufficiently strong inductive hypothesis. A sketch of the inductive step:

• If $n$ is even and greater than 8, path(A,C,n) reduces in one step to path([A=0],C,n-1) (using Iverson notation), which is a losing (P) position. Therefore path(A,C,n) is a winning (N) position.

• If $n$ is odd and greater than 8, a play at one of the ends of the path reduces it to a winning position path([A=0],C,n-1) or path(A,[C=0],n-1). Therefore if we want to find a losing position for our opponent, we must split into two paths as path(A,0,i) + path(0,C,n-1-i) for some $1\le i\le n-2$. We now have a further case-split:

  • $i$ is odd, and one or both of the paths is a special-case winning position for small odd $K$.
  • $i$ is odd and we hand our opponent a sum of two losing odd paths.
  • $i$ is even and we hand our opponent a sum of two winning even paths.

  The first sub-case can probably be dealt with by brute force. The other two might be amenable to joint treatment if we show that the sum of a losing odd path and a winning even path is a losing position. (Empirically this seems to be the case. A possible approach would be to strengthen to "the sum of a losing odd position and a winning even position with a total of $n$ unlabelled vertices is a losing position; the sum of two losing odd positions or two winning even positions with a total of $n$ unlabelled vertices is a winning position" and try to induct on $n$).

Answer 3

The reason that, as others have noted, the player who wants the last number to be even wins on large path graphs is that the configuration $0..0$ (and also, less importantly, $1..1$) leads to an even number independent of the order of play, whereas the parity of the last number placed in the configuration $0..1$ depends on the order of play. Thus, when the "even" player sets up $0..0$, the other player has to spend two moves filling in the two dots to prevent these from being the last numbers, whereas there is no corresponding manoeuvre for the "odd" player.

A sketch for a proof that the even player wins sufficiently large path graphs: If the odd player goes first, she has to place a $0$. The even player creates a $0..0$ configuration. If the odd player plays elsewhere, the even player just continues improving his situation by creating more $0..0$ configurations. Likewise, if the odd player plays inside the $0..0$ to destroy it, the even player creates further such configurations (using the sufficiently available space). The best the odd player can do is to create one $0.0$ configuration per move, but for every move she spends doing that, the even player creates another $0..0$.

If the even player goes first, he plays somewhere in the middle. The odd player can then create one $0.0$, or can place a $1$ next to the $0$ in an attempt to destroy opportunities of $0..0$ creation. But the even player still has the other side to create a $0..0$. Then the odd player can create another $0.0$, or shield the $0$ on the other side with a $1$. But neither helps. If the odd player opts for $0.0$s, the even player can win either by creating more $0..0$s or by filling in the $0.0$s (since he's now half a move ahead in the filling race), and if the odd player opts for shielding $1$s, the even player can play another $0$ in a sufficiently distant part of the field and create another $0..0$ there.

Obviously there are some details to fill in to turn this into a rigorous proof, but it seems clear to me that this asymmetry, the ability to build a winning configuration that takes two moves to destroy whereas the other player can only build single winning spots, is the basic reason for the results for large path graphs.