Nimbers

I was going to write a short post asking another question I've had in the course of my research, but then I realized I should try to explain some of the terms behind it first.

Thus: Nimbers.

Nimbers are a way of evaluating impartial games in a way that describes more than just "which player can win" (though it does that too). The simplest example is the term's namesake, Nim. I won't go in to describing the many versions of Nim, just the most basic: you are given a bunch of piles of objects (say sticks). Each turn, a player may take as many sticks as they like from one pile. The winner is the player who takes the last stick.

This is very simple in the case of only one pile: take all the sticks. With multiple piles, the winning move is to take from the larger pile so that the two have the same number of sticks (if they already do, you're in trouble). It turns out that we can quickly evaluate the winnability of a situation with any number of sticks: count the sizes and xor them together. If the total is zero, there is no winning strategy.

Thus, while the pile containing 4 sticks has a winning strategy (take them all) a game consisting of two piles of 4 cannot always be won (4 xor 4 = 0).

Also, the game consisting of the three piles 3, 5 and 6 has no winning strategy (3 xor 5 = 6, which xor'ed with itself is 0).

This reality comes from an evaluation technique that can be used to identify any impartial game! This is drawn recursively from the values of the children---the games which can occur from the parent in one move. In Nim, if we just have one pile, then the children of that pile are all piles with less sticks. Thus, that pile has the "power" to be changed into any smaller pile. If we have a pile of size 5, it could be turned into a pile of size 0, 1, 2, 3 or 4. Although in the case where there is only the one pile, the correct move would be to 0, there are still some more options here.

In the case where we have two piles, say 1 and 3, we have the power to move to any of those children: 0 and 3, 1 and 2, 1 and 1 and 1 and 0. Using our evaluation trick from before, we find those games have nim-values 3, 3, 0 and 1 respectively. Thus, this game should be inherently different from the game where we had a pile of size 5. Indeed, look at those values. The above one has a value of 5 (it's just one pile; that's easy). The second has a value of 2 (1 xor 3 = 2). Why is this?

Notice that for the second one, 2 is the first nim value that is not included in the children, which we also call the "mex" or "minimum excluded number". More formally, for any set S of natural numbers,

mex(S) = min{x in N | x not in S} where N are the natural numbers

This really gives us the power of an impartial game by seeing how many continuous values are included in the children. This is what we call the nimber of an impartial game, G:

nimber(G) = mex({x in N | there exists child G' of G where nimber(G') = x})

We can compare and see that the nimbers of our above two games match exactly with the nim-values we calculated (with xor'ing) before. The above principle can be applied to any impartial game, however. Unfortunately, this is a recursive operation which takes, in general, an exponential amount of time to calculate. Nim is easy to evaluate because there is the simple xor-trick to shortcut past the nimber definition.

Having said all that, here is a question I encountered while trying to evaluate some board games: if the nimbers for a game are bounded above, does this imply that there is an efficient algorithm, or shortcut, to evaluate impartial games? Further, if the bound is not a constant but a slowly-growing function, can we find efficient evaluation?

In the course of wishing I knew the answer to this (I was evaluating a game that appeared to have some sort of efficient patterns) I found nimbers emerge for the game that were higher than I thought were possible. I still hope there is some kind of relationship here, however...