Grundy's Game

Combinatorial game theory is a deep well to draw from in the math enrichment world. JRMF has Apple Picking, Countdown, Rook's Move, and Sprigs on the books. I thought we'd look at the classic Grundy's Game and a few variations. I'll take this as an opportunity to introduce a few concepts useful in analyzing combinatorial games, more broadly.

Setup

In Grundy's Game, two players start with some number of tokens in a pile, say \( 10 \). The first player starts by splitting the pile into two unequal piles, which we'll shorthand by addition. The first move on a pile of \( 10 \) tokens could result in piles of \( 1 + 9 \), \( 2 + 8 \), \( 3 + 7 \), or \( 4 + 6 \), but not \( 5 + 5 \). The second player chooses one of these two piles to then split into two unequal piles. The players take turns splitting piles in this way until no piles can be split unequally. The last player able to make a move is the winner. Below is an example game:

Example

The players start with \( 10 \) tokens in a pile.

• Player 1 splits the pile of \( 10 \) tokens into \( 3 + 7 \).

• Player 2 splits \( 3 + 7 \) into \( 3 + (2 + 5) = 2 + 3 + 5\).

• Player 1 splits \( 2 + 3 + 5 \) into \( 2 + (1 + 2) + 5 = 1 + 2 + 2 + 5 \).

• Player 2 splits \( 1+2+2+5 \) into \( 1+2+2+(1+4) = 1+1+2+2+4 \).

• Player 1 splits \( 1+1+2+2+4 \) into \( 1+1+2+2+(1+3) = 1+1+1+2+2+3 \).

• Player 2 splits \( 1+1+1+2+2+3 \) into \( 1+1+1+2+2+(1+2) = 1+1+1+1+2+2+2 \).

Since piles of size \( 1 \) cannot be split and piles of size \( 2 \) cannot be split unequally, the game is over and Player 2 has won.

When I've run this activity in the past, I've opted for bingo chips, since they're cheap, colorful, and heap nicely. Those or similar tokens will be fine for the main arc of this activity. For the variations, it will be helpful to maintain a sense of order and actually make use of the colors. This can be done with tokens with some care, but another option is to turn it from a pile-splitting game into a stick-breaking game using unifix cubes, Lego-like bricks, chaining monkeys, or objects of various colors that can link in a line.

Initial Questions

• If both players play perfectly, which player should win this game on a pile of \(10\) tokens?

• If the first player has the advantage, what is the best opening move? Is there more than one first move that can lead to victory?
• If the second player has the advantage, what should their responses look like to the first player's possible opening moves?
• Can you pin down a winning strategy, from start to finish of a game?

• How do things change when starting with different numbers of tokens?

Explorations

• For the game on \(10\) tokens, we can look at some opening moves and see how the second player might respond. The analysis might go a little quicker if we note that there are certain pile sizes that always take the same number of moves to split completely -- that is, so no further splitting is possible.

  Pile Size		Moves to Split Completely
  \(1\)		\(0\)
  \(2\)		\(0\)
  \(3\)		\(1\)
  \(4\)		\(2\)

  • If the first player splits \(10\) into \(4+6\), the second player can split the \(6\) into \(2+4\), leaving \(2+4+4\). This game will end with a Player 2 victory in \(0+2+2 = 4\) moves.
  • If the first player splits \(10\) into \(3+7\), the second player can split the \(7\) into \(3+4\), leaving \(3+3+4\). This game will end with a Player 2 victory in \(1+1+2 = 4\) moves.
  • The responses to \(1+9\) and \(2+8\) are a little trickier, but we can actually come up with a strategy that works for both of these and \(3+7\) at the same time! In all three of these cases, the second player use their turn to make \(1+2+7\). If we make a game tree of the ways \(7\) can split completely, this is what we see:
    
    In particular, we see that no matter how the first player tries to split \(7\), the second player can turn it into \(1+2+4\), at which point the game ends with a Player 2 victory in 2 moves.

  Since this covered all opening moves, we've seen Player 2 always has a winning strategy to steer the game to victory. In fact, as long as they remember that \(2+4+4\), \(1+2+7\), and \(1+1+2+2+4\) are good configurations, then the second player just has to aim for these states when one of them is possible and then make any move they like otherwise!

• As we've seen above, drawing out game trees can be a useful way to find a strategy. For small numbers of tokens, this can be a good way to organize your thoughts, but gets a little unwieldy after a while.

• Something interesting came up that we didn't fully make use of in our analysis of 10 tokens: reduction to a "balanced" case where there is a copycat strategy. When the first player started with \(10 = 4+6\) and the second player responded with \(4+6 = 2+4+4\), since \(2\) is completely split, all of the remaining action is on \(4+4\). Whatever Player 1 does next involves one pile of \(4\), and Player 2 can respond by doing the exact same thing on the other pile of \(4\). As long as the board is always left balanced, Player 1's move will always have a response, so Player 2 cannot lose. Whenever a player can create a symmetric arrangement, this copycat strategy exists:

  • Given \(13+14\), turn it into \((13)+1+(13)\).
  • Given \(10+12\), turn it into \((10)+2+(10)\).
  • Given \(3+9+9\), turn it into \((9)+1+2+(9)\).
  • Given \(3+5+8\), turn it into \((3+5)+(3+5)\).
  • Given \(7+11\), turn it into \((7)+4+(7)\). (The pile of 4 will take two moves to split completely, so it doesn't upset the copycat strategy as long as any play on that pile is immediately responded to there.)

• A space-saving version of the game tree can be created by tracking winning and losing states. In this cataloging system, we assign each state a W or L based on whether we would want to see it on our turn or not. For example, \(13+14\), \(10+12\), and \(3+9+9\) are W states because we know how win from that point on if we see them on our turn while \(2+4+4\), \(1+2+7\), and \(1+1+2+2+4\) are L states, because we would like our opponent to be faced with them on their turn. Taking reachable to mean one legal move away:

  • A state is L if all reachable states are W states.
  • A state is W if at least one reachable state is an L state.

  In other words, a position is bad if you can only hand your opponent a position that's good, while a position is good if you can hand your opponent a position that's bad.

  We can figure out whether small positions are winning or losing and then bootstrap larger positions from that. We'll adopt the convention of shorthanding states like \(1+2+2+3+4\) as \(3+4\), since piles of \(1\) and \(2\) are completely split, and analogously, states like \(1+2+2\) as \(0\).

  • It's easy to see that \(0\) is L, \(3\) is W, and \(4\) is L.
  • Since \(5\) is one move away from \(1+4 \equiv 4\), an L state, \(5\) is a W state.
  • The only state one move from \(3+3\) is \(1+2+3 \equiv 3\), a W state, so \(3+3\) is an L state.
  • \(6\) is one move away from \(2+4 \equiv 4\), an L state, so \(6\) is a W state.
  • \(3+4\) is one move from \(1+3+3 \equiv 3+3\), an L state, so \(3+4\) is a W state.
  • Since \(7\) is one move away from only \(1+6 \equiv 6\), \(2+5 \equiv 5\), and \(3+4\), all W states, \(7\) is an L state.

  We can tabulate these to make it easier:

  State		W/L
  \(0\)		L
  \(3\)		W
  \(4\)		L
  \(5\)		W
  \(3+3\)		L
  \(6\)		W
  \(3+4\)		W
  \(7\)		L
  \(3+5\)		W
  \(4+4\)		L
  \(8\)		W
  \(3+3+3\)		W
  \(3+6\)		L
  \(4+5\)		W
  \(9\)		W

• A major result in combinatorial game theory, the Sprague-Grundy theorem, is a sort of generalization of the notion of "balance" and our Winning/Losing state categorization. This is an incredibly interesting topic to dig into with more advanced students, but almost certainly will not emerge naturally. Each state of the game is given a nonnegative integer Grundy value (or nimber) based on the nimbers of states that are one move away. The nimber of a state is the minimum nimber that is not one of the nimbers of a reachable state, or \(\textrm{mex}\) (for minimum excluded value).

  • No states are reachable from \(0\), so its nimber is \(0\).
  • Only \(1+2 \equiv 0\) with nimber \(0\) is reachable from \(3\), so \(3\) has nimber \(\textrm{mex}(\{0\}) = 1\).
  • Only \(1+3 \equiv 3\) with nimber \(1\) is reachable from \(4\), so \(4\) has nimber \(\textrm{mex}(\{1\}) = 0\).
  • Only \(1+4 \equiv 4\) and \(2+3 \equiv 3\) are reachable from \(5\), so \(5\) has nimber \(\textrm{mex}(\{0,1\}) = 2\).

  Tabulating nimbers for the first several states:

  State		W/L
  \(0\)		\(0\)
  \(3\)		\(1\)
  \(4\)		\(0\)
  \(5\)		\(2\)
  \(3+3\)		\(0\)
  \(6\)		\(1\)
  \(3+4\)		\(1\)
  \(7\)		\(0\)
  \(3+5\)		\(3\)
  \(4+4\)		\(0\)
  \(8\)		\(2\)
  \(3+3+3\)		\(1\)
  \(3+6\)		\(0\)
  \(4+5\)		\(2\)
  \(9\)		\(1\)

  At first blush, this might seem like a more annoying way to compute W/L values, since each L is now a \(0\) and each W is a nonzero value. The power is through the Sprague-Grundy theorem, if we want the nimber of the state \(a \uplus b\) (\(\uplus\) instead of \(+\) to emphasize that this is not addition!), it's the same as the bitwise XOR ( \(\veebar\) ) of the nimbers corresponding to \(a\) and \(b\), i.e., \[ \textrm{nim}(a \uplus b) = \textrm{nim}(a) \veebar \textrm{nim}(b) \] To compute \( x \veebar y \), write each of \(x\) and \(y\) as a sum of distinct powers of \(2\). \( x \veebar y \) is then the number obtained when you add up (one copy of each of) the powers of \(2\) that occur an odd number of times. For example, for \( 312 \veebar 177 \), \[ 312 = 256+32+16+8, \] \[ 177 = 128+32+16+1, \] and \[ 312 \veebar 177 = 256+128+8+1 = 393. \] This means that compute the nimber of the three-pile state \(16+17+18\), we need only know the nimbers for \(16\), \(17\), and \(18\): \[ \begin{eqnarray*} \textrm{nim}(16 \uplus 17 \uplus 18) & = & \textrm{nim}(16) \veebar \textrm{nim}(17) \veebar \textrm{nim}(18) \\ & = & 3 \veebar 2 \veebar 4 \\ & = & (2+1) \veebar 2 \veebar 4 \\ & = & 4+1 \\ & = & 5. \end{eqnarray*} \]

  The first several nimbers are

  \( n \)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(11\)	\(12\)	\(13\)	\(14\)	\(15\)	\(16\)	\(17\)	\(18\)	\(19\)	\(20\)
  \(\textrm{nim}(n)\)	\(0\)	\(0\)	\(1\)	\(0\)	\(2\)	\(1\)	\(0\)	\(2\)	\(1\)	\(0\)	\(2\)	\(1\)	\(3\)	\(2\)	\(1\)	\(3\)	\(2\)	\(4\)	\(3\)	\(0\)

Wrap-Up Questions

• What are some good strategies for winning this game?
• Were there any pile sizes where the explanation of your strategy is particularly easy?
• Are there any patterns to whether the first or second player will have the advantage?

Extensions

• A nice question to ponder is why the "unequal piles" condition is necessary when splitting. What would happen in the version of the game where splitting into equal piles is allowed? Is that game somehow less interesting?

• Using red and blue unifix cubes to form a stick, how does this game change if you can only break sticks into unequal sticks as usual, but your breaks can only happen at places where the neighboring cubes have different colors? If the colors alternate red, blue, red, blue, ..., then this is just Grundy's Game. However, if there are runs of the same color, this can change how the game is played.

  In standard gameplay, a pile of size \(10\) can split into \(3+7\). There is no way to do this for the configuration below, however:

  

  Does the second player still have the advantage here? What happens for other sticks of length \(10\) with different colorings? There are \(2^{10} = 1024\) such sticks before we consider symmetries!

  (We could change the condition so that cuts can only happen where neighboring cubes are the same color, but you might be able to see why that doesn't add any new interesting problems to the general analysis!)

This post was sponsored by the Julia Robinson Mathematics Festival