# P-positions of Nim variant with multi-pile moves

I was looking at a variant of Nim that involves two piles of stones, let's say (m, n), where m and n represent the number of stones of the first and second pile, respectively.

A valid move involves choosing a positive integer x and taking 1) x stones from one Nim pile 2) x stones from both Nim piles 3) x stones from one, and 2x stones from the other.

In general, how would you approach finding the P-positions of a game of Nim involving moves across piles, particularly this one?

Generally you compute the $$N$$ and $$P$$ positions for small numbers and hope to find a pattern. $$(0,n)$$ and (n,n) are $$N$$ because you take all the stones. $$(1,2)$$ is $$N$$ because you take all the stones. Keep working up to larger piles.

There can only be one $$P$$ position with a given number of stones in a pile because you can take stones from the other pile to get there. There can also only be one $$P$$ position with a given difference in the number of stones because the $$(x,x)$$ move will get you there.

I agree with your $$(1,3),(2,6),$$ and $$(4,5)$$ being $$P$$ positions. I think the next are $$(7,10),(8,13),(9,16)$$ but I may have missed something.

• Two matching piles (n,n) cannot be a P-position, since move 2 (in my question) lets the player remove all the remaining pieces, so it would be an N-position. Also, I found recursively that (1,3), (2,6), and (4,5) are P-positions. Apr 18, 2019 at 3:02
• I missed that part. Working. Apr 18, 2019 at 3:03
• I think $(8,13)$ and $(9,16)$ should be $(8,14)$ and $(9,17)$, unless my code has an error (quite possible). Apr 20, 2019 at 17:16

For an arbitrary impartial game like this (since the heaps aren't independent, I wouldn't really call this a heap game, but maybe a variation of Wythoff's game), I find it helpful to write some code to evaluate whether many positions are $$\mathcal{N}$$ or $$\mathcal{P}$$-positions (i.e. whether the next player to move has a winning strategy or not). Since this game has relatively simple rules, it can be coded up quickly, to see pictures of the $$\mathcal{P}$$-positions.

For example, the $$\mathcal P$$-positions for heap sizes up through 19 are shown here:

This shows that $$(0,0)$$, $$(1,3)$$, $$(2,6)$$, $$(4,5)$$, $$(7,10)$$, $$(8,14)$$, $$(9,17)$$, and $$(13,18)$$ are $$\mathcal{P}$$-positions.

No pattern is clear, so we can scale up to the heap sizes through 99:

Unfortunately, this doesn't seem to have a simple pattern. It's a little reminiscent of the pictures of positions of Wythoff's game whose Grundy value is equal to a fixed number. Those pictures have positions that are at most a bounded distance from the key lines of slope $$\phi$$ and $$1/\phi$$.

The best I can produce quickly is the heap sizes up to $$399$$:

They seem to be roughly hugging four lines, but there's some randomness - it's not as simple as the $$\mathcal P$$-positions of Wythoff's game.

Here is some Wolfram Language code (I promise no elegance or efficiency):

moves[pair_] :=
moves[pair] =
Union @@ Table[{If[pair[[1]] >= x, Sort@{pair[[1]] - x, pair[[2]]},
Nothing],
If[pair[[2]] >= x, Sort@{pair[[1]], pair[[2]] - x}, Nothing],
If[pair[[1]] >= x && pair[[2]] >= x,
Sort@{pair[[1]] - x, pair[[2]] - x}, Nothing],
If[pair[[1]] >= x && pair[[2]] >= 2 x,
Sort@{pair[[1]] - x, pair[[2]] - 2 x}, Nothing],
If[pair[[2]] >= x && pair[[1]] >= 2 x,
Sort@{pair[[2]] - x, pair[[1]] - 2 x}, Nothing]}, {x, 1,
Max @@ pair}];
pwins[pair_] := pwins[pair] = AllTrue[moves[pair], Not[pwins[#]] &];
MatrixPlot[
Table[If[pwins[Sort@{a, b}], 1, 0], {a, 0, 199}, {b, 0, 199}],
ColorFunction -> "Monochrome", DataReversed -> {True, False},
Frame -> False, ImageSize -> 800, PlotRangePadding -> 0]


You can run that code without Mathematica by going to the Wolfram Development Platform, clicking on "Create a New Notebook", pasting the code, and then using Shift+Enter or Numpad Enter to evaluate the code. The parameters in that code generate an image of the $$\mathcal{P}$$-positions for heap sizes up to 199.

• What are the slopes of the four lines? I am sure there are two pairs of inverses, reflecting the fact that if $(a,b)$ is a $P$ position so is $(b,a)$. They might be interesting numbers. Apr 20, 2019 at 23:41
• @RossMillikan Well, I only have approximations, but the upper slopes seem to be pretty close to $9/4$ and $3/2$. Apr 21, 2019 at 1:57