5
$\begingroup$

I am learning the basics of combinatorial game theory (impartial games). After learning about decompose a game into the sum of games, I feel comfortable with games that can divided into the sum of 1 pile games. The situation is more or less clear to me: I have to find the game graph, calculate the Sprague-Grundy values and use them to find the solution to a game.

But I do not really know what to do in case when I can't decompose a game in 1 pile games. Here is an example:

You have piles of stones, people alternate turns, person who can't make a move loses. During the move, a player can select any one of the piles divide the stones in it into any number of unequal piles such that no two of the newly created piles have the same number of stones.


I have huge problem in analyzing the 1 pile subgame (calculating grundy values for the pile of $1, 2, 3, ... n$ stones in the pile), because after each move 1 piles is divided into more piles.

How should I analyze such games?

$\endgroup$
  • 1
    $\begingroup$ Start with the computation of the S-G values of games with few stones, not with few piles. $\endgroup$ – Mariano Suárez-Álvarez May 23 '16 at 6:51
  • 1
    $\begingroup$ Can't you just recursively apply the usual rules on all combinations of piles that can result from a single move? It probably won't be easy to calculate the S-G value of a single $n$ stone pile. (read: I don't know the answer, but I haven't tried yet). Piles of 1 or 2 stones are "dead" in that they offer no further legal moves. So a pile of 3 has value 1, because all moves turn it into "no moves". A pile of 4 can only be split 3+1, a value 1 position, and hence has value 0 itself. A pile of 5 can be split 4+1 or 3+2 with respective values 0 and 1, so it has value 2. Keep going! $\endgroup$ – Jyrki Lahtonen May 23 '16 at 6:54
  • $\begingroup$ Thank you @MarianoSuárez-Alvarez and JyrkiLahtonen. Will try to do this $\endgroup$ – Salvador Dali May 23 '16 at 7:07
2
$\begingroup$

It’s not hard to use Jyrki’s suggestion to make a table of Sprague-Grundy values of small single heaps:

$$\begin{array}{rcc} \textbf{heap size}:&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \textbf{S-G value}:&0&0&0&1&0&2&3&4&0&5&6&7&8&9&10&11&12 \end{array}$$

  • For $n=6$ the possible splits are $\langle 5,1\rangle,\langle 4,2\rangle$, and $\langle 3,2,1\rangle$, with S-G values $2$, $0$, and $1$, respectively, so the S-G value of $6$ is $3$.
  • For $n=7$ the possible splits are $\langle 6,1\rangle,\langle 5,2\rangle,\langle 4,3\rangle$, and $\langle 4,2,1\rangle$, with respective values $3$, $2$, $1$, and $0$, so the value of $7$ is $4$.
  • For $n=8$: $\langle 7,1\rangle,\langle 6,2\rangle,\langle 5,3\rangle,\langle 5,2,1\rangle$, and $\langle 4,3,1\rangle$, with respective values $4$, $3$, $2\oplus 1=3$, $2$, and $1$, so the value of $8$ is $0$.
  • For $n=9$; $\langle 8,1\rangle,\langle 7,2\rangle,\langle 6,3\rangle,\langle 5,4\rangle,\langle 6,2,1\rangle,\langle 5,3,1\rangle$, and $\langle 4,3,2\rangle$, with values $0$, $4$, $3\oplus1=2$, $2$, $3$, $2\oplus 1=3$, and $1$, so the value of $9$ is $5$.
  • For $n=10$: $\langle 9,1\rangle,\langle 8,2\rangle,\langle 7,3\rangle,\langle 6,4\rangle,\langle 7,2,1\rangle,\langle 6,3,1\rangle,\langle 5,4,1\rangle,\langle 5,3,2\rangle$, and $\langle 4,3,2,1\rangle$, with respective values $5$, $0$, $4\oplus1=5$, $3$, $4$, $3\oplus1=2$, $2$, $2\oplus 1=3$, and $1$, so the value of $10$ is $6$.
  • For $n=11$ the values of the reachable positions are $6,5,1,4,1,0,5,3,2,2,3$, so the value of $11$ is $7$.
  • For $n=12$ the values of the reachable positions are $7,6,4,0,6,5,1,4,1,5,3,3,2,2$, so the value of $12$ is $8$.
  • For $n=13$ the values of the reachable positions are $8,7,7,5,2,7,6,4,0,6,1,2,5,3$, so the value of $13$ is $9$.
  • For $n=14$ the values of the reachable positions are $9,8,6$, $6,7,3$, $7,7,5$, $2,7,4$, $0,6,5$, $0,1$, $4,1,3$, so the value of $14$ is $10$.
  • For $n=15$ the values of the reachable positions are $10,9,9$, $7,4,6$, $4,8,6$, $6,7,3$, $7,5,2$, $7,1,7$, $1,4,0$, $6,2,3$, so the value of $15$ is $11$.
  • For $n=16$ the values of the reachable positions are $11,10,8$, $8,5,5$, $1,9,9$, $7,4,6$, $4,6,6$, $7,3,4$, $3,6,6$, $7,5,2$, $7,5,0,2$, so the value of $16$ is $12$.

I had hoped that the S-G value of $16$ would be $0$, suggesting a pattern of values increasing by $1$ but dipping to $0$ at each power of $2$. Since that failed, I have no reasonable guess at the actual pattern.

It’s probably worth investigating the possibility that for $n\ge 9$ the S-G value of a heap of $n$ is simply $n-4$; I do intend to give it some thought.

$\endgroup$
  • $\begingroup$ Not sure whether the SG values are correct. I think so because your received the values for a Grundy's game, playing a modification of a Grundy game. In Grundy game you can divide a heap into two heaps. In this game you can divide a heap into any number of heaps. $\endgroup$ – Salvador Dali May 23 '16 at 23:58
  • $\begingroup$ I think it is likely to stay $n-4$, but don't have a general proof. $\endgroup$ – Mark S. May 24 '16 at 1:39
  • $\begingroup$ @Mark: I shouldn’t be surprised either. $\endgroup$ – Brian M. Scott May 24 '16 at 1:40
3
$\begingroup$

As Jyrki commented, moves in this game do decompose piles into sums of piles, and the xor rule still applies when you have a sum of more than two piles.

With a little Mathematica code just using the mex and xor rules for the Sprague-Grundy values, I found that the values for a single pile from size $1$ to size $70$ are: $0,0,1,0,2,3,4,0,5,6,7,\ldots,66$. In particular, the value for a single pile of size $n$ (where $n>9$) appears to be $n-4$. This sort of pattern makes sense because as the numbers grow, there are so many ways to partition the pile that you can achieve every previous number as the xor of the values you can reach.

However, I haven't been able to see an obvious pattern in the winning moves, so I'm not sure how to prove that this pattern continues forever.


code:

moves[n_] := moves[n] = 
  Map[If[Union[#] == Sort[#] && Length[#] > 1, #, Nothing] &, 
   IntegerPartitions[n]]; 
mex[list_] := mex[list] = 
  Do[If[Not[MemberQ[list, i - 1]], Return[i - 1]], {i,Length[list] + 1}]; 
nimber[n_] := nimber[n] = 
  mex[Map[Apply[BitXor, Map[nimber, #]] &, moves[n]]];

Edit:

Using cgsuite, we can get much further. If we restrict the rules to say that you can decompose a pile into at most five piles, then the Sprague-Grundy values can be calculated very efficiently by cgsuite code: hr:=game.heap.HeapRules.MakeRules("&60;!."); hr.NimValues(500)

With this, we see that splitting into at most five piles is enough for the pattern mentioned above to persist all the way up to size $499$ with value $495$. Restricting to at most four piles puts a 0 between 12 and 13, but continues an $n-5$ pattern thereafter all the way up to an initial pile size of $499$ as well. (At most three piles gives too few options for a simple pattern).

$\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.