5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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:

P-positions up through heap size 19

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:

P-positions up through heap size 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$:

P-positions 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 20 at 23:41
  • $\begingroup$ @RossMillikan Well, I only have approximations, but the upper slopes seem to be pretty close to $9/4$ and $3/2$. $\endgroup$ – Mark S. Apr 21 at 1:57
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rakeeb Hossain Apr 18 at 3:02
  • $\begingroup$ I missed that part. Working. $\endgroup$ – Ross Millikan Apr 18 at 3:03
  • $\begingroup$ I think $(8,13)$ and $(9,16)$ should be $(8,14)$ and $(9,17)$, unless my code has an error (quite possible). $\endgroup$ – Mark S. Apr 20 at 17:16

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.