2
$\begingroup$

I've been reading about combinatorial game theory, and some works start with the game of Nim. After that, they introduce Nimbers, which are numbers that represent Nim games. So far so good. I get that, and I understand Nimber addition.

But I don't understand how any of this helps to play Nim.

So I'm interested in knowing how to use Nimbers to play Nim better. Specifically..

  1. How do Nimbers represent Nim games?
  2. What does Nimber addition mean in the context of Nim?
  3. What does Nimber multiplication mean in the context of Nim?

If there's a worked-through example of playing Nim via Nimbers, that would be awesome.

$\endgroup$
2
4
$\begingroup$

It's been a while since I've read up on Nimbers (introduced to me by the immortal Martin Gardner), but if I remember correctly, nimbers are basically regular numbers representing the number of stones in a Nim heap. The nimber "sum" is the XOR of the nimbers, and represents a sort of "combined" heap, except that removing stones can either increase or decrease the resulting total nimber, but will always change the total. In particular, since nimbers are always nonnegative, if the total nimber is $0$, there is no place to go but up. Note that the case of all heaps empty has nimber $0$.

So this is the strategy: at the start of your turn, calculate the total nimber. If it is not $0$, determine a change that will make it $0$ and make that move (nim-add each heap to the total you've already calculated (start with the largest heap) and when you find one where the result is less than the heap size, reduce that heap to the result). If the total is $0$, hope and pray that your opponent makes a mistake.

Because it is always possible to reduce a total nimber to $0$ in one move, and since no move will keep a total nimber of $0$ at $0$, as long as you are the one reducing the nimber to $0$, your opponent can't win. They must always move in a way that increases the nimber, meaning that it is never $0$ at the end of their turn. Which means that they cannot reduce all heaps to $0$, since that position has a total nimber of $0$.

$\endgroup$
2
  • 1
    $\begingroup$ I should add for those not familiar with "Nimbers" that they are not defined as numbers with a different "addition". Instead, the sum is a method of combining Nim games, and the nimbers are equivalence classes under the relation that the sum game is a 2nd player win. It is only with some development that this is seen to be equivalent to XOR on numbers. $\endgroup$ Oct 29 '15 at 0:41
  • $\begingroup$ Perfect! I wrote some code that played Nim using XOR as the strategy and it's unbeatable, provided it goes first and doesn't start in a losing position (xor = 0). Now to study the Sprague-Grundy Theorem. If certain classes of games are equivalent to Nim, then finding a two way mapping from those games onto Nim and vice versa means a built-in unbeatable strategy for a bunch of games. $\endgroup$
    – R. Barzell
    Oct 29 '15 at 21:23

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.