Question

In Sid Sackson's classic book A Gamut of Games, he introduces a game that he calls "Hold That Line." Briefly, it is an impartial pencil-and-paper game played on a finite grid of dots. The first player connects two dots with a horizontal, vertical, or diagonal line; thereafter, each player extends the given piecewise-linear curve at one end, making sure to keep it self-avoiding.

Analyzing this game looks like a nice project in combinatorial game theory, suitable for undergraduates, but has it already been studied? A quick search only turned up a brief discussion in Alan Lipp's book The Play's the Thing.

Answer 1

I'm assuming the last person to move is the winner. After that, it sounds hard.

If, after any move after the first move (the first move occupies occupies two dots and all other moves occupy one), there is an odd number of dots summed over the regions accessible to the two ends, then the player to move is the "winner of the moment." The only way the "loser of the moment" can change the status is to subdivide a region at either end so that one or more regions are not accessible. The player that creates a division is not the one who chooses which region to enter. So if a division is created with one new region odd and another even, then the player creating the division has gained no advantage since the next player will choose the one to enter so as to become "winner of the moment."

As far as I can tell, there are moves that carve a region into two smaller regions, and moves the carve a region into three. I don't see any way of getting four. (Based on the fact that each dot has 8 neighbors.) Getting a curve close to a point where a subdivision can take place depends on the shape of the region (most importantly seen from the end of the curve). Getting to a good place of division can set up quite a fight.

All in all it sounds like a hard analysis.

Answer 2

I'm quite interested in such games. Here are some general speculative thoughts about attacking them.

Piet Hein's old games Nimbi and TacTix are similar, simpler games that were also proposed with the misere play convention. For example, TacTix is played on a 4x4 grid where the players take turns crossing out adjacent tokens (1 up to 4), with diagonal moves not allowed, and the misere play convention, ie, whoever crosses out the last token loses. Nimbi is played on a 12-cell board that is most easily thought of as a triangular arrangement of 15 tokens in an equilateral triangle with its three corners deleted before play begins. Nimbi moves involve taking adjacent tokens in any of the three available directions.

I've recently tried to compute the misere quotient of the full board for TacTix and for Nimbi (actually, I'm still working on both games now). I believe that both quotients are infinite for their respective full-board start positions, but have observed that there are many interesting finite, wild Nimbi and TacTix endgame quotients (one of order 324, for example), and it's conceivable (at least to me) that one might marry an explicit prescription for winning "opening play" of such games that matches the much more easily-computed normal play strategy, and that eventually "connects up" to one of several known to be finite "endgame" misere quotients. Ie, even though the "full board" has an intractable misere theory of sums, this unpleasantness can be dodged by following a "normal play" strategy just long enough to eventually steer play to endgame sums with finite misere quotients.

Answer 3

Jo\~{a}o Pedro Neto has it listed on his site, http://www.di.fc.ul.pt/~jpn/gv/soldiers.htm Though in his version, it seems like non-orthogonal lines must have slope $1$ or $-1$, so that connecting $(1,1)$ and $(4,2)$ is not allowed. He also allows the second player to play or pass the first turn.

Considering that it is a misere game (last person to play loses), a complete analysis may involve introducing Thane Plambeck and Aaron Siegel's misere quotients. See http://miseregames.org/ for more on that.

As written, with slanted diagonals available, the play is easy to analyze on small boards (2x3 and 3x3 are first player wins), and the game conveniently breaks into subgames which can be summed. The difficulty is that the summation is not the usual nimber sum for normal-play games because of the misere condition. Seems like a very nice example for introducing misere quotients though, since the sums are still computable on paper (at least up to 4x5), and don't require any tools like MisereSolver.