Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
For the sake of completeness, you might expand your definition of the game to include how many players, what a win or scoring condition is, and so on. Additionally, there are those of us who might try analyzing Sid's version and giving back to you new information if you do this. Gerhard "I Suspect I'm Not Alone" Paseman, 2012.01.08 –  Gerhard Paseman Jan 8 '12 at 22:38
1  
Here are the rules, copied from A Gamut of Games (pg. 146): "To play, just draw 16 dots in 4 rows of 4. The first player connects as many dots as he wishes in a straight line [which an illustration indicates may run diagonally]. From either end of the first line the second player draws another straight line. From either free end the first player now makes a line. Continue until no further lines can be drawn. The player who was forced to make the last line is the loser! The completed line must be continuous, with no branches, no crossings, and no dot visited twice." –  Barry Cipra Jan 9 '12 at 2:38
4  
The first player draws a main diagonal, and then plays to make the piecewise-linear $\hspace{1 in}$ curve symmetric about the center of the grid. $\;$ –  Ricky Demer Jan 9 '12 at 3:20
    
Demer's comment explains why my assumption was wrong and the rules give the win the next to last player. –  Matt Brin Jan 9 '12 at 3:24
    
A better description of the rules (or at least somebody's understanding of them) is at books.google.com/… –  Kevin O'Bryant Jan 9 '12 at 4:18

3 Answers 3

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.

share|improve this answer
    
The rules allow a move to cover more than one dot, and the first move can connect, for example, dots (1,1), (2,2), and (3,3). I'm also reading the rules as allowing connecting (1,1) to (4,2). –  Kevin O'Bryant Jan 9 '12 at 4:16

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.