12
$\begingroup$

Two players play a game as follows. There is a line of $n>3$ spaces, initially empty. The players take alternate turns. On each turn, the turn player puts a stone onto an empty space. If, as a result of a player placing a stone, four (or more) consecutive spaces have stones on, that player wins.

Where there is room for 4, neither player would dare extend a line of 2, or play next to either of 2 stones which have only 1 space in between, so these in effect split the game into subgames. Where $\square$ is an empty space and $\blacksquare$ is a stone,

$$G \square\square\blacksquare\blacksquare\square\square H = G + H$$

because playing on any of the empty spaces shown lets the opponent make a winning 4 on the next turn. But

$$G \square\blacksquare\square\square\blacksquare\square H = G\square\blacksquare + \blacksquare\square H$$

because neither player will play between the 2 stones shown, but it is OK to play on the leftmost or rightmost of the empty spaces shown.

So it is enough to analyse positions where every 2 stones have either 1 or at least 3 empty spaces in between.

So we have positions like $$\begin{array}{ll} 5&\square\square\square\square\square\\ [4&\blacksquare\square\square\square\square\\ [4]&\blacksquare\square\square\square\square\blacksquare \end{array}$$ but also positions like $\square\square\square\square\square\blacksquare\square\square\square$ which are not yet the sum of two subgames.

This is an impartial combinatorial game, so the value of each position is a nimber.

One easy result is that $2k$ is a P-position because the 2nd player can adopt a reflexive copy-cat strategy.

Is this game (or one isomorphic to it) already known? I can't see it in Winning Ways or any of the first 3 volumes of Games of No Chance.

(If the winning condition is changed to "3 (or more) consecutive spaces have stones on", then the game becomes Treblecross or .007, which is well-known.)

$\endgroup$
  • $\begingroup$ I'm not sure about the first decomposition into subgames $G\square\blacksquare\blacksquare\square H=G+H$. For example, $G=\square\square\blacksquare\blacksquare$ and $H=\blacksquare\blacksquare\square\square$ are $P$ positions, but $G\square\blacksquare\blacksquare\square H$ is an N position. $\endgroup$ – Julian Rosen Mar 20 '18 at 1:07
  • $\begingroup$ @JulianRosen Whoops! Yes, two consecutive stones means four "taboo" empty spaces, 2 on each side. I will alter my OP accordingly. $\endgroup$ – Rosie F Mar 20 '18 at 7:38
  • $\begingroup$ I'm not convinced by the second one either: $G\square\blacksquare\square\blacksquare\square H$ with $G = \square\square\blacksquare\blacksquare$ is an N-position regardless of what $H$ is, and even though $G$ is a P-position. $\endgroup$ – Peter Taylor Mar 22 '18 at 11:34
  • $\begingroup$ @PeterTaylor So it is. And I don't see a way of saving it either. $G\square\square\blacksquare\square\blacksquare\square\square H$ isn't $G\square\square\blacksquare + \blacksquare\square\square H$ (playing 2 to G's right is safe in the sum but $N$ in the original). And in the original, playing at G's rightmost and the space to its right is $N$, so each summand must have an explicit $\blacksquare$. $\endgroup$ – Rosie F Mar 22 '18 at 12:56
5
+150
$\begingroup$

Since four-in-a-row is the winning configuration, $\blacksquare\blacksquare\blacksquare$ and $\blacksquare\square\blacksquare\blacksquare$ and $\blacksquare\blacksquare\square\blacksquare$ are immediately losing configurations. We can say instead that these are forbidden configurations, and change the winning condition to the usual one for impartial games: when the current player has no legal move, the other player wins. So no player is permitted to play inside $\blacksquare\square\square\blacksquare$, next to or inside $\blacksquare\square\blacksquare$, or within two squares of $\blacksquare\blacksquare$. This can be used to decompose a game into a Nim-sum of smaller games whenever two $\blacksquare$ are within three spaces of each other; but it's necessary to keep track of forbidden spaces in the sub-games. We can say that $$ G\blacksquare\square\square\blacksquare H = G\blacksquare \;\oplus\;\blacksquare H, $$ that $$ G\blacksquare\square\blacksquare H = G_{+1}\blacksquare \;\oplus\;\blacksquare H_{-1}, $$ and that $$ G\blacksquare\blacksquare H = G_{+2}\blacksquare \;\oplus\;\blacksquare H_{-2}, $$ where $G_{+2}$ represents the game $G$ with its rightmost two squares forbidden. Note that only empty squares are ever forbidden by this procedure, and at most two on either end of a game. So we only need to analyze irreducible games, in which there are at least three white squares between every pair of black squares, with at most two forbidden white squares on either end. It may seem that we need special consideration of whether the end squares are black or whether there are terminal white blocks. In fact, we may with no loss of generality assume both end squares to be black: note that the initial white block of length $k$ is equivalent to a white block of length $k+4$ between two black squares, where $2$ white squares are forbidden on each end.

As such, for analysis purposes we can represent every irreducible game as a list of integers representing lengths of white blocks (all at least $3$), flanked by two integers representing the number of forbidden squares at each end. We analyze games of the form $(a_1,a_2,\ldots,a_{n-1},a_n)_{\ell}^{r}$, where $0 \le \ell, r \le 2$ and all $a_i \ge 3$. By left-right symmetry, $$(a_1,\ldots,a_{n})_{\ell}^{r} \simeq (a_{n},\ldots,a_{1})_{r}^{\ell}.$$ The initial game of length $k$ is represented as $(k+4)_{2}^{2}$. Now, any legal move is made within one of the white blocks, and splits that block into two. The transition $$ (a_1,\ldots,a_k,\ldots,a_{n})_{\ell}^{r} \rightarrow (a_1,\ldots,a_k-b-1,b,\ldots,a_{n})_{\ell}^{r} $$ is legal if $0 \le b \le a_k-1$, and as long as $b \ge r$ if $k=n$ and $b \le a_k-1-\ell$ if $k=1$. If the resulting game is reducible (i.e., if some $a_i < 3$), we decompose it into a sum of smaller games. In particular, $$ (a_1,\ldots,a_{k-1},a_{k},a_{k+1},\ldots,a_n)_{\ell}^{r} \simeq (a_1,\ldots,a_{k-1})_{\ell}^{2-a_k} \oplus (a_{k+1},\ldots,a_{n})_{2-a_k}^{r} $$ whenever $a_k \le 2$. Note that when two reductions apply, the order doesn't matter: $$ (5,4,5)_{\ell}^{r}\rightarrow (5,2,1,5)_{\ell}^{r} \simeq (5)_{\ell}^{0} \oplus (1,5)_{0}^{r} \simeq (5)_{\ell}^{0} \oplus \left(\right)_{0}^{1} \oplus (5)_{1}^{r} $$ or $$ (5,4,5)_{\ell}^{r}\rightarrow (5,2,1,5)_{\ell}^{r} \simeq (5,2)_{\ell}^{1} \oplus (5)_{1}^{r} \simeq (5)_{\ell}^{0} \oplus \left(\right)_{0}^{1} \oplus (5)_{1}^{r}. $$ The Nim-value of any irreducible game can now be computed in terms of the Nim-values of simpler (e.g., with smaller sum $a_1+a_2+\ldots+a_n$) irreducible games by applying the usual Sprague-Grundy minimum-excluded-value rule.


Update:

I've analyzed starting positions out to $k=37$ by applying the above considerations. All even-$k$ starting positions are second-player wins (by strategy stealing, as pointed out by OP); it turns out that all odd-$k$ starting positions are first-player wins with Nim-value $1$, with the single exception of $k=13$, which is a second-player win. Intermediate positions encountered in the analysis have Nim-values as high as $13$, so the structure of the game is nontrivial... and actually describing the optimal strategy for the first player does not seem to be simple.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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