Winning colourful Nim with the eeny-meeny rule

• Colourless Nim
• Colourful Nim
  • A (possible) winning strategy for multiple piles
    • The eeny-meeny rule
    • Example calculations
    • Winning (or losing)
  • Some example games
    • Game 1: A single pile
    • Game 2: Two simple piles
    • Game 3: Two complicated piles
    • Game 4: Five complicated piles
  • Some proofs and not-proofs of the eeny-meeny rule
    • True for $k = 1$
    • True for $k = 2$
    • A useful result
    • A breather
    • True for $k = 3$
    • True for $k = 4$
    • True for $k > 4$?
• Further generalisations
  • 3-colour Nim?
  • Taking balls from both ends
  • Sequences of impartial games in general
• References and more links

Colourless Nim

Nim is a game where two players take turns removing (“nimming”) stones from different piles. On each player’s turn, they can remove as many stones as they like, but they all have to be from one pile. The player who makes the last move wins – or equivalently, the player who is left with no remaining moves loses.

This simple game turns out to run surprisingly deep in the field of mathematics known as combinatorial game theory, which is concerned for the most part with beating opponents at two-player perfect information games, like tic-tac-toe, checkers and Go. Specifically, there’s a result called the Sprague-Grundy theorem which states (informally) that every combinatorial game where each player has access to the same set of moves on each of their turns is equivalent to a game of Nim. Combinatorial games like this are called “impartial games”.

This means the following – if you’re playing an impartial game, and:

1. You are a perfect Nim player, and
2. You know how to convert positions in this game into an game of Nim

…then you can always win at that impartial game.

Luckily, perfect play at Nim is reasonably easy if you know the trick, a result called Bouton’s theorem, which says that you can always guarantee a win if, on your turn, you remove stones to make the bitwise XOR (sometimes called the nim-sum) of all the pile sizes equal to $0$.

Mentally calculating the bitwise XOR of lots of numbers sounds difficult, but it is surprisingly simple.

Colourful Nim

Now suppose you’re playing the game with a set of English pool balls which are red and yellow, and you add the rule that you can only remove sections of contiguous colour from the tops of each pile:

You could also play this game with cards facing up and down, knives and forks, bananas and apples, and so on. You just need two distinguishable items you can make piles out of.

If you want to try it out online, you can play it here.

The winning strategy for just one pile is reasonably straightforward to work out (consider which moves you can force your opponent to take). But when there are multiple piles, things are a lot more interesting and working out the best move is non-trivial.

A (possible) winning strategy for multiple piles

The following gives the perfect strategy for any number of piles.

…or at least I’m 99% sure it does. I haven’t succeeded in proving the strategy is correct for any number of piles and any number of colour changes, but have done so when there are any number of piles, each of which has at most 4 colour changes.

To describe the winning strategy, we’ll need some notation.

Notation: Write $(n _ 1, \ldots, n _ k)$ for a pile with $n _ k$ balls of one colour at the top, followed by $n _ {k-1}$ balls of the next colour, followed by $n _ {k-2}$ of the original colour, and so on, all the way until $n _ 1$ which gives the number of balls in the bottom section of the pile.

(oops, that illustration is not quite right. The last pile should have two red balls at the top, then one yellow, then one red, then one yellow and then one red).

Note that for all practical purposes when trying to win, it doesn’t matter if the pile starts yellow or starts red, it is really only the sequence of colour changes that matters.

The strategy is almost identical to ordinary Nim. In ordinary Nim, you win by making the XOR of all the pile sizes equal to zero. Now instead of making the XOR of all the pile sizes equal to zero, you make the XOR of the “Grundy values” of each pile equal to zero. Write $\mathcal G(n _ 1, \ldots, n _ k)$ for the Grundy value of the pile $(n _ 1, \ldots, n _ k)$.

It’s not necessary to know exactly what “Grundy value” means to win, we just need to know how to calculate it. But intuitively, the Grundy value of a pile tells you the size of the equivalent Nim heap as guaranteed to exist by the Sprague-Grundy theorem.

The empty game has Grundy value $0$, or in the notation, $\mathcal G() = 0$. If the pile is just of one colour, then the Grundy value is just the number of balls in that pile. In our notation, this means $G(n _ 1) = n _ 1$. This makes sense, a pile with no colour changes is equivalent to a game of Nim.

To calculate the Grundy value for piles with colour changes, things get a bit more complicated. To do this, you need the “eeny-meeny rule”.

The eeny-meeny rule

Say you’re looking at a pile $(n _ 1, \ldots, n _ k)$. The rule is:

So either $\mathcal G(n _ 1, \ldots, n _ k)$ is $n _ k$ or $n _ k-1$, and the eeny-meeny condition tells you if you need to subtract one. When is the eeny-meeny condition met?

• Start by looking at the top of the pile, $n _ k$, and work your way down each section of colour in steps, saying “eeny” and “meeny” alternately.
• Call $n _ k$ eeny compared to $n _ {k-1}$ if $n _ k < n _ {k-1}$ (exiguous, very small in size or amount).
• Call $n _ {k}$ meeny compared to $n _ {k-1}$ if $n _ k > n _ {k-1}$ (massive, large and heavy or solid).
• If you say “eeny” moving from $n _ k$ to $n _ {k-1}$ and $n _ k$ is eeny compared to $n _ {k-1}$ (i.e. $n _ k < n _ {k-1}$), then the condition is met! You should subtract one, so $\mathcal G(n _ 1, \ldots, n _ k) = n _ k - 1$ in this case.
• If you say “meeny” moving from $n _ k$ to $n _ {k-1}$ and $n _ k$ is meeny compared to $n _ {k-1}$ (i.e. $n _ k > n _ {k-1}$), then the condition is also met! You should subtract one, so $\mathcal G(n _ 1, \ldots, n _ k) = n _ k - 1$ in this case.
• If $n _ k = n _ {k-1}$, continue working your way down the pile.
• If $n _ k$ is meeny compared to $n _ {k-1}$ when it is supposed to be eeny or $n _ k$ is eeny compared to $n _ {k-1}$ when it is supposed to be meeny, then you can stop checking. The condition is not met, and you can stop looking.
• …
• There is one more special case: if you say eeny as you reach the end of the pile, then $n _ 2$ can be eeny compared $n _ 1$ with equality, so $n _ 2 \le n _ 1$ is a valid comparison.

In more mathematical notation, you’re applying the two formulas:

in the even case, and

in the odd case. Or, an equivalent Python program is the following:

def eeny_meeny(pos):
  # Assumes `pos` is a list like [n_1, ..., n_k].

  # For an empty pile, the value is zero.
  if len(pos) == 0:
    return 0

  # For a single-coloured pile, the value is just the
  # number of balls.
  if len(pos) == 1:
    return pos[0]
  
  # Get the value at the top of the pile
  n_k = pos[-1]
  
  # Work out if the eeny-meeny condition is met
  condition_met = False
  state = "eeny"
  i = len(pos) - 1
  
  while i >= 1 and not condition_met:
    n = pos[i]
    n_next = pos[i-1]
    
    if state == "eeny":
      if n < n_next: # n is eeny compared to n_next
        condition_met = True
      elif i == 1 and n <= n_next: # special case for eeny end
        condition_met = True
      elif n == n_next: # Keep going if equal
        pass
      elif n > n_next: # meeny when its supposed to be eeny
        break

    if state == "meeny":
      if n > n_next: # n is meeny compared to n_next
        condition_met = True
      elif n == n_next: # Keep going if equal
        pass
      elif n < n_next: # eeny when its supposed to be meeny
        break
      
    state = "eeny" if state == "meeny" else "meeny" # Flip the state
    i -= 1
    
  if condition_met:
    return n_k - 1
  else:
    return n_k

This looks quite complicated, but it is just a rule that lets you work out whether the Grundy value is the number of balls in the top section, or that number minus one. Here are some illustrations.

Example calculations

Winning (or losing)

After you’ve done this calculation for each pile, you’ll have a collection of Grundy values $g _ 1, \ldots, g _ m$ where $m$ is the number of piles. The best move to make is to make the bitwise XOR of all these values equal to zero, and in fact all other moves are losing.

More specifically, writing $g _ i \oplus g _ j$ for the bitwise XOR of two Grundy values $g _ i$ and $g _ j$, there are two cases:

• If you calculate $g _ 1 \oplus \cdots \oplus g _ m = 0$ at the start of your turn, then you are in trouble since if your opponent players perfectly, you have lost. In this case, your best bet is to move into the most complicated position you can spot, hoping they won’t be able analyse it.
• Otherwise, $g _ 1 \oplus \cdots \oplus g _ m \ne 0$. In this case, you can force a win. To do this, like in ordinary Nim, you should play a move that changes the bitwise XOR of all the piles to be zero.

Some example games

Game 1: A single pile

What’s the best move in this game with just a single pile?

In the notation, this first position is $(1, 2, 2, 2)$. Here’s how you can win:

Or, annotated with the Grundy value of each intermediate pile:

You don’t need the full complication of the eeny-meeny rule when there is just one pile, it’s reasonably easy to see which move wins. But it is vital when there is more than one pile.

Game 2: Two simple piles

What’s the move here?

The Grundy value of the first pile is $2$, and the Grundy value of the second is $1$. To win, you therefore make the Grundy value of the first pile also $1$, since $1 \oplus 1 = 0$. To do this, remove just one ball from the first pile. Here’s an example game where you make that move:

Game 3: Two complicated piles

Here’s a more complicated game, now the piles are unequal:

The move here is to take just one ball from the pile on the right. There’s lots of ways the game can unfold from this point, but you win in all of them. Here is one potential game:

Game 4: Five complicated piles

How many winning moves are there in the following?

…there are in fact no winning moves. This is because the Grundy values are $1$, $0$, $1$, $1$ and $1$, and $1 \oplus 0 \oplus 1 \oplus 1 \oplus 1 = 0$.

Any move you make will move to a position where the XOR is nonzero, and so if your opponent is using the eeny-meeny strategy, they will be able to win.

Some proofs and not-proofs of the eeny-meeny rule

This section is more technical and assumes some basic results and definitions in combinatorial game theory.

We defined a position as $(n _ 1, \ldots, n _ k)$. The possible moves from this position are to:

• $(n _ 1, \ldots, n _ {k-1})$, which corresponds to removing all balls in the top section
• For each $\ell < n _ k$, $(n _ 1, \ldots, n _ k - \ell)$, which corresponds to removing $\ell$ balls from the top section

For an arbitrary impartial game, the Grundy value of a position $\pmb p$ is defined as:

(here $\text{mex}$ is the minimum excludant, the smallest nonnegative natural number not appearing in the set). In our case, we have:

From this it is clear that $\mathcal G(n _ 1) = n _ 1$, since by induction

Results from the theory of impartial games tells us that if we can calculate the Grundy value for each pile in colourful Nim, say $g _ 1, \ldots, g _ m$, then we can find the Grundy value of the overall game (where the possible moves are considered across every pile) by taking the bitwise XOR of each: $g _ 1 \oplus \cdots \oplus g _ n$. As a consequence of other results, making sure that $g _ 1 \oplus \ldots g _ n = 0$ at the end of your turn is enough to guarantee a win.

So justifying the eeny-meeny rule is the same as proving the following:

True for $k = 1$

The eeny-meeny rule says nothing about piles where $k = 1$, but it’s useful to record here what we already know:

True for $k = 2$

The eeny-meeny rule for $k = 2$ says that:

We want to show that this is indeed equivalent to the actual definition:

To do this, we can induct on $n _ 2$. The base case is $n _ 2 = 1$:

which is indeed the eeny-meeny rule for $k = 2$.

Now consider $\mathcal G(n _ 1, n _ 2)$ where $n _ 2 > 1$. By strong induction, we can assume that for all $\mathcal G(n _ 1, n _ 2 - \ell)$, the eeny-meeny rule works, i.e.

By the definition of $\mathcal G$, we have that:

Now we consider cases.

Case 1: $n _ 2 \le n _ 1$. If this is true, then it must also be true that $n _ 2 - \ell \le n _ 1$ for all $\ell < n _ 2$. This means the eeny-meeny condition is satisfied for each $\mathcal G(n _ 1, n _ 2 - \ell)$, hence:

So this case gives the eeny-meeny rule as we hope.

Case 2: $n _ 2 > n _ 1$. Then $n _ 1 = n _ 2 - m$ for some $m > 0$. Then:

Plugging this into the definition for $\mathcal G(n _ 1, n _ 2)$, we have:

Since $n _ 1 = n _ 2 - m$, this means $\mathcal G(n _ 1, n _ 2) = n _ 2$ as we hope.

Combining the cases. Now this gives us a general formula for $\mathcal G(n _ 1, n _ 2)$:

which is exactly the eeny-meeny rule for $k = 2$.

A useful result

If you squint, the proof for the $k = 2$ case can be adapted to show a stronger and more general result, namely that:

You can prove this more precisely by induction on $k$. The base cases are:

which is what we have just verified above.

Now consider $\mathcal G(n _ 1, \ldots, n _ k)$ where $k > 2$. By strong induction on $k$, we can assume that $(\star)$ holds for $\mathcal G(n _ 1, \ldots, n _ {k-1})$.

We want to verify that $(\star)$ holds for this particular value of $k$. To do this, we now induct on $n _ k$, like how we inducted on $n _ 2$ for the $k = 2$ case.

Now inducting on $n _ k$, the base case we need to verify is that for $\mathcal G(n _ 1, \ldots, n _ {k-1}, 1)$:

as required. So that establishes the base case for the induction on $n _ k$.

Now assume $n _ k > 1$. Like in the $k = 2$ case, we’ll break it down by cases again:

Case 1: $n _ k \le \mathcal G(n _ 1, \ldots, n _ {k-1})$. If this is true, then it must also be true that $n _ 2 - \ell \le \mathcal G(n _ 1, \ldots, n _ {k-1})$ for all $\ell < n _ k$, and so inductively :

So $(\star)$ is correct in this case.

Case 2: $n _ k > \mathcal G(n _ 1, \ldots, n _ {k-1})$. Then $G(n _ 1, \ldots, n _ {k-1}) = n _ k - m$ for some $m > 0$. Then:

Plugging this into the definition for $\mathcal G(n _ 1, \ldots, n _ k)$, we have:

Since $\mathcal G(n _ 1, \ldots, n _ {k-1}) = n _ k - m$, this means $\mathcal G(n _ 1, \ldots, n _ k) = n _ k$ as we hope.

A breather

Here’s what we’ve shown so far: by definition, the Grundy value of a position is defined recursively by:

and as a base case.

We know now the following for certain:

and we have the more general formula:

This is still a long way from proving the full eeny-meeny rule, which says that in general:

and

In other words, the eeny-meeny rule gives a non-recursive formula for the Grundy value of an arbitrary position.

True for $k = 3$

We can use what we have shown so far to prove the eeny-meeny rule also works when $k = 3$, in other words justifying the correctness of the formula:

We know for sure that:

and that:

Plugging the formula for $\mathcal G(n _ 1, n _ 2)$ into the above and considering all possible cases, we get:

Simplifying slightly:

So we have two conditions: one we know is the actual Grundy value, and the eeny-meeny condition. We want to show they are the same.

Write

If we can show $\pmb G \iff \pmb E$, then we are done, since then the eeny-meeny rule corresponds to the true Grundy value.

Consider cases:

• Case 1: $n _ 3 < n _ 2$:
  • $\pmb E$ satisfied (by $\mathcal A$).
  • Case 1.1: $n _ 2 < n _ 1$:
    • $\pmb G$ satisfied (by $\mathcal 1$).
  • Case 1.2: $n _ 2 = n _ 1$:
    • $\pmb G$ satisfied (by $\mathcal 1$).
  • Case 1.3: $n _ 2 > n _ 1$:
    • $\pmb G$ satisfied (by $\mathcal 2$).
• Case 2: $n _ 3 = n _ 2$:
  • Case 2.1: $n _ 2 < n _ 1$:
    • Neither $\pmb G$ or $\pmb E$ are satisfied.
  • Case 2.2: $n _ 2 = n _ 1$:
    • Neither $\pmb G$ or $\pmb E$ are satisfied
  • Case 2.3: $n _ 2 > n _ 1$:
    • Both $\pmb G$ and $\pmb E$ are satisfied (by $\mathcal 2$ and $\mathcal B$).
• Case 3: $n _ 3 > n _ 2$
  • Neither $\pmb G$ or $\pmb E$ are satisfied.

Hence $\pmb G \iff \pmb E$, and so the eeny-meeny rule for $k = 3$ is correct.

True for $k = 4$

You can do the same thing for $k = 4$. We know that

and have just shown that

Substituting $\mathcal G(n _ 1, n _ 2, n _ 3)$ means you end up with

and you want to show that

is the same formula, where

So again, the problem reduces to showing the equivalence between two sets of inequalities. Indeed, $E \iff G$:

• Case 1: $n _ 4 < n _ 3$
  • $\pmb E$ is satisfied (by $\mathcal A$).
  • Case 1.1: $n _ 3 < n _ 2$
    • $\pmb G$ is satisfied (by $\mathcal 1$).
  • Case 1.2: $n _ 3 = n _ 2$
    • Case 1.2.1: $n _ 2 < n _ 1$
      • $\pmb G$ is satisfied (by $\mathcal 4$).
    • Case 1.2.2: $n _ 2 = n _ 1$
      • $\pmb G$ is satisfied (by $\mathcal 4$)
    • Case 1.2.3: $n _ 2 > n _ 1$
      • $\pmb G$ is satisfied (by $\mathcal 2$).
  • Case 1.3: $n _ 3 > n _ 2$
    • $\pmb G$ is satisfied (by $\mathcal 3$).
• Case 2: $n _ 4 = n _ 3$
  • Case 2.1: $n _ 3 < n _ 2$
    • Neither $\pmb G$ or $\pmb E$ are not satisfied.
  • Case 2.2: $n _ 3 = n _ 2$
    • Case 2.2.1: $n _ 2 < n _ 1$
      • Both $\pmb G$ and $\pmb E$ are satisfied (by $\mathcal 4$ and $\mathcal C$)
    • Case 2.2.2: $n _ 2 = n _ 1$
      • Both $\pmb G$ and $\pmb E$ are satisfied (by $\mathcal 4$ and $\mathcal C$)
    • Case 2.2.3: $n _ 2 > n _ 1$
      • Neither $\pmb G$ or $\pmb E$ are satisfied.
  • Case 2.3: $n _ 3 > n _ 2$
    • Both $\pmb G$ and $\pmb E$ are satisfied (by $\mathcal 3$ and $\mathcal B$)
• Case 3: $n _ 4 > n _ 3$
  • Neither $\pmb G$ or $\pmb E$ are satisfied.

So the eeny-meeny rule is the same as the actual Grundy value for $k = 4$.

True for $k > 4$?

As you can see, things get very hairy very quickly. You could apply the same technique for $k = 5$, but you would quickly end up in the dense mathematical thicket of cases, subcases, subsubcases and subsubsubcases. And worse, a manual proof like this is never going to be able to handle the general case for arbitrary $k$.

I can’t prove the general case, but have checked that the eeny-meeny rule works for 5, 6, and 7 colour changes where there are at most 6 balls in each section of colour, and would be very surprised if it fails to hold.

A general proof could look something like this: Induct on $k$, the number of colour changes. The base cases have already been proved above.

We want to show that:

More explicitly, this means showing that:

in the even case, and

in the odd case.

Start with the even case. By one of the results above, we have:

You’d then need to apply the inductive hypothesis and substitute $\mathcal{G}(n _ 1, \ldots, n _ {2k-1})$ with the general eeny-meeny rule for odd-sized piles. If, after simplifying, you end up with the eeny-meeny rule for even-sized piles you would’ve proved the even case.

Then move onto the odd case. Again, we have:

You’d then need to apply the inductive hypothesis again and substitute $\mathcal{G}(n _ 1, \ldots, n _ {2k-2})$ with the general eeny-meeny rule for even-sized piles. Again, if you then end up with the eeny-meeny rule for odd-sized piles, you would’ve proved the odd case.

And if you’ve proved these two cases, you’ve proved the eeny-meeny works in general.

Further generalisations

Colourful Nim is a generalisation of ordinary Nim – ordinary Nim is just the special case where there are no colour changes. But what are some ways you could generalise further?

3-colour Nim?

What about instead of having two colours, you have three?

Unfortunately, this is no more interesting or difficult than having 2 colours like above. The reason for this is that the colours don’t actually matter, only the colour changes. So the above game is equivalent to the 2-colour game:

So to play 3-colour Nim, just translate it into 2-colour Nim and play with the eeny-meeny rule like above.

Taking balls from both ends

What about if you can take balls from both ends of each pile?

This seems immediately more complicated. The general strategy would still stand, namely calculating the Grundy value of each pile and then making the XOR equal to zero. But the problem becomes how to efficiently calculate the Grundy value.

Here are the Grundy values (calculated by a computer) of all piles with three colour changes and with at most three balls per section:

If there is a simple relationship here, I can’t spot it.

Sequences of impartial games in general

A one-pile colourful Nim game could also be seen as a sequence of one-pile Nim games, where the loser of each sub-game goes first in the next-sub game.

But what if you make each game in the sequence more complicated? For example, you could instead play a sequence of three multiple-pile Nim games:

This is also much more complicated. One thing that definitely won’t work is calculating the Grundy value of each game in the sequence, and then considering the corresponding colourful Nim game, like so:

It’s a resonable guess that you can just omit these zero games and “compress” the stack before applying the rule, but this is not the case – consider the game $(1, [2,2])$ where $[2, 2]$ denotes a game with two Nim piles of two stones each. Since $[2, 2]$ has Grundy value $0$ by the XOR trick, this guess would say that the overall Grundy value is $1$, and hence winnable for us. But by trying to win this game yourself, you can see that this is impossible.

But it gets worse – the Grundy value of the overall game cannot be any function of the Grundy values of each intermediate game. To see this, consider this game:

(i.e. a sequence of $\ell$ games of Nim, at the top a $k _ \ell$ pile Nim game, followed by a $k _ {\ell - 1}$ pile game, and so on, until a $k _ 1$ pile game).

The Grundy value of this game cannot be a function of the Grundy values of the intermediate games, i.e.

for any $f$. If this were the case, $([1], [1,1])$ and $([1], [2,2])$ would have the same Grundy value, but this can’t be the case since $([1], [1,1])$ is a win for the first player, while $([1], [2,2])$ is a loss.

This means, among other things, that it’s not possible to come up with a uniform strategy for all sequences of impartial games just by considering the Grundy values of each impartial game in the sequence, and converting it to a game of Nim.

Another reason to expect that it is much more complicated is because a general strategy for playing sequences of games where you have the perfect strategies for the intermediate games would give you a general technique for misère play of any impartial game. The misère version of an impartial game is where you change the win condition so that whoever makes the last move loses.

Misère play is surprisingly often much more complicated than normal play – here’s the winning strategy for misère Nim, paraphrasing from [[On Numbers and Games, Conway]]^N:

“Play as you would in normal Nim, making the XOR of the heap-sizes zero, unless your move would leave only heaps of size one, (discounting empty heaps). In this case, move so as to leave either one more or one fewer one-heaps than the normal play move.”

If you had a general rule for playing sequences of impartial games, you could convert any game into its misère variant by considering the that game followed by a game of Nim with a single stone.

A general procedure for converting perfect play at the normal version of an impartial game to perfect play at the misère version would be remarkable, so it’s quite unlikely the generalisation to sequences of impartial games is straightforward.

References and more links

• [[On Numbers and Games, Conway]]^N, specifically:
  • Chapter 11: Impartial Games and the Game of Nim
  • Chapter 12: How to Lose when you Must
• [[The Book of Numbers, Conway]]^N
  • Chapter 10: Infinite and Infinitesimal Numbers, “Nimbers and the Game of Nim”
• “HACKENBUSH: a window to a new world of math” is a playful introduction to some of the esoteric ideas developed in combinatorial game theory.
• “Sprague-Grundy theory” by Gabriel Nivasch for more details on Sprague-Grundy theory.