Can anyone analyze this misere game? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T12:21:04Z http://mathoverflow.net/feeds/question/85314 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85314/can-anyone-analyze-this-misere-game Can anyone analyze this misere game? zeb 2012-01-10T07:14:39Z 2012-05-02T11:09:07Z <h3>Problem</h3> <p>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\}$.</p> <blockquote> <p>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$?</p> </blockquote> <p>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$.</p> <blockquote> <p>Second question: Is the set of such $n$s infinite, with density $0$?</p> </blockquote> <hr> <h3>Motivation</h3> <p>There is a recent conjecture due to Ezra Miller and Alan Guo (see Conjecture $4.5$ in <a href="http://arxiv.org/abs/1105.5413" rel="nofollow">this paper</a>) which implies that the set of multiples of any misere game that are wins for the previous player to move is eventually periodic.</p> <p>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.</p> <hr> <h3>Computation</h3> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/85314/can-anyone-analyze-this-misere-game/88969#88969 Answer by Thane Plambeck for Can anyone analyze this misere game? Thane Plambeck 2012-02-19T22:24:12Z 2012-02-19T22:24:12Z <p>Have you seen these slides by Alex Fink (and the associated papers)?</p> <p><a href="http://www4.ncsu.edu/~arfink/lattice_game_slides.pdf" rel="nofollow">http://www4.ncsu.edu/~arfink/lattice_game_slides.pdf</a></p> http://mathoverflow.net/questions/85314/can-anyone-analyze-this-misere-game/95750#95750 Answer by zeb for Can anyone analyze this misere game? zeb 2012-05-02T11:09:07Z 2012-05-02T11:09:07Z <p>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.</p> <p>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.)</p> <p>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$.</p> <p>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 <code>$*2$</code> as follows: green corresponds to a lost game, red corresponds to a game that loses when you add <code>$*$</code>, and blue corresponds to a game that is a first player win and remains a first player win when you add <code>$*$</code> 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)$.</p> <p>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:</p> <pre><code>(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) ... ... </code></pre> <p>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.</p> <p>The end result is <a href="http://www.its.caltech.edu/~notzeb/test.table" rel="nofollow">this rule table</a>, with <a href="http://www.its.caltech.edu/~notzeb/test.colors" rel="nofollow">these colors</a> 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:</p> <p><img src="http://www.its.caltech.edu/~notzeb/misere.png" alt="Blah"></p>