11
$\begingroup$

Problem

Let $* = \{0\}$ be the one matchstick nim game, let $*2 = \{0,*\}$ be the two matchstick nim game, let $*3 = \{0,*,*2\} = *2+*$ be the three matchstick nim game, let $g = \{0, *2+*3, *2+*2+*2\} = *2_{22}2_30$, and finally let $h = \{*3, g+*, g+g\}$.

Question: For which numbers $n$ does the misere game consisting of $n$ copies of $h$ have the same outcome as the misere game consisting of $n+1$ copies of $h$?

The $n$s below $4000$ with this property are $1, 2, 3, 12, 14, 17, 38, 40, 56, 74, 101, 227, 319, 464, 692, 1025, 1189,$ and $1781$.

Second question: Is the set of such $n$s infinite, with density $0$?


Motivation

There is a recent conjecture due to Ezra Miller and Alan Guo (see Conjecture $4.5$ in this paper) which implies that the set of multiples of any misere game that are wins for the previous player to move is eventually periodic.

I found the game I am calling $h$ while I was searching for a counterexample to their conjecture. It seems likely that it can be completely analyzed. If the answer to the second question is yes, then $h$ is clearly a counterexample to their conjecture.


Computation

To calculate the winning positions quickly, it is useful to think of playing a sum of such games as moving around on a four dimensional lattice, where the coordinates correspond to the numbers of copies of $*, *2, g,$ and $h$ that are currently in play. A move corresponds to decreasing one of the positive coordinates while increasing some of the other coordinates, and the position $(0,0,0,0)$ is a win for the next player to move. Thinking this way, you can easily calculate the set of winning positions inductively.

Since $*+* = 0$ even as misere games, we can further simplify by imagining that we are playing a game on $\mathbb{Z}/2\times \mathbb{N}^3$, which gives a computational speedup. In theory one could probably rephrase this again as a fairly simple (directional) two-dimensional cellular automata (by taking two dimensional diagonal slices of the three dimensional lattice), so some version of the hashlife algorithm should give an exponential computational speedup, but I haven't found a way to make it work yet.

$\endgroup$
1
  • $\begingroup$ "Since $∗+∗=0$ even as misere games" I think you mean $\\{0\\} + \\{0\\} = \\{0|0\\}$, i.e. it is a first player win as a misere game. In misere Nim, the one matchstick game is a first player loss, so one usually does not denote it by $*$. $\endgroup$ Jan 10, 2012 at 13:21

2 Answers 2

4
$\begingroup$

I recently managed to convert this problem into a cellular automata, and the answer to the second question appears to be no, making this question uninteresting.

However, I think some people might appreciate the details of the computations, so I'll put them here (and then close the question? I'm not sure how I should deal with answering my own question.)

First, the results of the computations. Let $N(x)$ denote the number of values $n$ below $x$ such that $n$ copies of $h$ and $n+1$ copies of $h$ have the same outcome. Then $N(10^3) = 15, N(10^6) = 86, N(10^9) = 148, N(10^{12}) = 196,N(10^{15}) = 205,$ and $N(10^{54}) = 205$. The last value of $n$ below $10^{54}$ is (if I didn't make any mistakes) $3,814,460,171,075$.

Next, the details of the computation. I start by visualizing the situation as a coloring of $\mathbb{N}^3$ in the colors red, green, and blue. The coloring of $(i,j,k)$ corresponds to the outcome of the game formed by $i$ copies of $h$, $j$ copies of $g$, and $k$ copies of $*2$ as follows: green corresponds to a lost game, red corresponds to a game that loses when you add $*$, and blue corresponds to a game that is a first player win and remains a first player win when you add $*$ to it. In order to calculate the color of $(i,j,k)$, one needs to know the colors of $(i,j,k-1)$, $(i,j-1,k)$, $(i,j-1,k+2)$, $(i,j-1,k+3)$, $(i-1,j,k+1)$, $(i-1,j+1,k)$, and $(i-1,j+2,k)$.

In order to convert this to a cellular automata, I take "diagonal cross sections" of $\mathbb{N}^3$. I lay out one such diagonal cross section as follows:

(3,0,0) (3,0,1) (3,0,2) (3,0,3) (3,0,4) (3,0,5) (3,0,6) (2,0,7) (2,0,8) ...
        (3,1,0) (3,1,1) (2,1,2) (2,1,3) (2,1,4) (2,1,5) (2,1,6) (2,1,7) ...
                (2,2,0) (2,2,1) (2,2,2) (2,2,3) (2,2,4) (2,2,5) (2,2,6) ...
                        (2,3,0) (2,3,1) (2,3,2) (2,3,3) (1,3,4) (1,3,5) ...
                                (1,4,0) (1,4,1) (1,4,2) (1,4,3) (1,4,4) ...
                                        ...

To go from this cross section to the next higher cross section, we just need to replace the cell marked $(2,0,7)$ with $(3,0,7)$, the cell marked $(2,1,2)$ with $(3,1,2)$, the cell marked $(1,3,4)$ with $(2,3,4)$, etc. With the cells laid out like this, it is easy to see that these updates only require the knowledge of the colors of cells within two steps of the cell you would like to update. Unfortunately, most cellular automata only allow the transition rules to depend on the values of the cells immediately adjacent, so I had to emulate this cellular automata with a slightly more complicated one.

The end result is this rule table, with these colors which you can load in a program such as Golly and experiment with. The automata needs a single white square to get started, and then proceeds to compute winning positions automatically. When it detects an $n$ such that the outcome of $(n,0,0)$ matches the outcome of $(n+1,0,0)$, it fires a cyan signal upwards, so you can calculate $N(x)$ by simulating up to generation $12x+14$ and counting the number of cyan signals produced. Here is a screenshot of a computation in progress:

Screenshot

$\endgroup$
0
$\begingroup$

Have you seen these slides by Alex Fink (and the associated papers)?

http://www4.ncsu.edu/~arfink/lattice_game_slides.pdf

$\endgroup$
3
  • $\begingroup$ I hadn't seen those slides, but I had seen the associated papers. This question is about a game in the unknown area - it can be phrased as a squarefree lattice game under misere play. $\endgroup$
    – zeb
    Feb 19, 2012 at 23:30
  • $\begingroup$ have you run your game h through Aaron Siegel's MisereSolver? $\endgroup$ Feb 21, 2012 at 5:33
  • $\begingroup$ Sorry, didn't notice your comment until just now. Unfortunately, from the very beginning there is no hope to run the game h through MisereSolver, since even the game g has an infinite misere quotient. $\endgroup$
    – zeb
    Mar 5, 2012 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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