Nimber Arithmetic : A deeper dive in Nim

Reading time: 25 minutes | Coding time: 10 minutes

Before we move on to Nimber Arithmetic, we need to know what exactly a nimber is. In mathematics, the nimbers, also know as Grundy Numbers (Read this article), where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.

As per Sprague-Grundy theorem, every impartial game is equivalent to a Nim heap of a certain size, nimbers arise in a much larger class of impartial games. (Fun Fact: It may also appear in partizan games)

As stated above, Nimbers are endowed with two particular operations. nim-addition and nim-multiplication


Algorithm


We will be discussing the nim-addition and nim-multiplication in deeper context with how they are implemented in Combinatory Game Theory (in Applications). But before we begin our journey, allow me to introduce you to 2 type of impartial game positions :

  • A Game is in P-Position if the Player who just took the current turn wins.
  • A Game is in N-Position if the Player after the player who took the current turn wins.

Nim addition


That being said, let's now discuss nim-addition

Nimber addition (also known as nim-addition) can be used to calculate the size of a single nim heap equivalent to a collection of nim heaps. It is defined recursively by:

$$\alpha \oplus \beta = mex ( \{ \alpha^, \oplus \beta : \alpha^, < \alpha \} \bigcup \{ \alpha \oplus \beta^, : \beta^, < \beta \} ) $$

For finite ordinals, the nim-sum is easily evaluated on a computer by taking the bitwise exclusive or (XOR, denoted by ⊕) of the corresponding numbers.

The key operation in the solution to Nim is binary addition without carrying.To add two numbers in this manner, first write out their binary expansions,and then take the exclusive or (XOR) of the two numbers bit by bit:

XOR of 3 and 5

In the XOR operation, 1 + 1 = 0 = 0 + 0, 1 + 0 = 1 = 1 + 0. Another way to look at it is that if you are adding an odd number of ones the answer is 1, an even number of ones gives 0. We will write this kind of addition of two numbers x and y as x ⊕ y. But, in practical game, you'd most probably start off with 2 or more than 2 heaps , what then?

heaps = [] //Array of numbers representing objects in heaps
nimSum = 0
for (int i = 0 ; i < len(heaps); i++){
    nimSum = nimSum ^ heaps[i]
}
print (nimSum)

This Algorithm should work fine in all cases. Given below is one nim-addition matrix:

nim addition for numbers till 15

Nim multiplication


Now, moving on to nim-multiplication:

Nimber multiplication is defined recursively by

$$\alpha * \beta = mex ( \{ \alpha^, \beta \oplus \alpha \beta^, \oplus \alpha^, \beta^, : \alpha^, < \alpha , \beta^, < \beta \} ) $$

First of all, let me make it clear that this method is not really famous as the latter one with not many applications, neverthless, to give you a basic idea of it's non intutiveness I would like you to have a look at this python snippet :

f = lambda x,y:min(set(range(x*y+1))-{f(i%x,i/x)^f(x,i/x)^f(i%x,y)for i in range(x*y)})

which implements the recursive multiplication like this :

// Here * denotes nim multiplication
6 * 13
= (4 + 2) * (8 + 4 + 1)
= (4 + 2) * ((4 * 2) + 4 + 1)
= (4 * 4 * 2) + (4 * 2 * 2) + (4 * 4) + (4 * 2) + (4 * 1) + (2 * 1)
= (6 * 2) + (4 * 3) + 6 + 8 + 4 + 2
= ((4 + 2) * 2) + 12 + 6 + 8 + 4 + 2
= (4 * 2) + (2 * 2) + 12 + 6 + 8 + 4 + 2
= 8 + 3 + 12 + 6 + 8 + 4 + 2
= 15

Complexity


  • For Nim Addition: O(N) {where N is number of heaps}
  • For Nim Multiplication: Exponential Function Similar to the recursive definition

Implementations


  • Python: Nimber Matrix Display
  • Python: Win or Lose

Nimber Matrix Display


    def get_matrix(n):
    main_matrix = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        main_matrix[0][i] = i
        main_matrix[i][0] = i
    for i in range(1,n):
        for j in range(1,n):
            #print(" Performing {}^{} at ({},{})".format(x[0][j],x[i][0],i,j))
            main_matrix[i][j] = main_matrix[0][j]^main_matrix[i][0]
    return main_matrix
def get_nimber(matrix):
    for i in range(1,len(matrix[0])):
        for j in range(1,len(matrix[0])):
            if matrix[i][j] > (max(matrix[0])/2):
                matrix[i][j] = "."
            else:
                matrix[i][j] = "-"
    for i in range(len(matrix[0])):
        print(*matrix[i])
my_matrix = get_matrix(16)
get_nimber(my_matrix)
   

Winner Prediction


    import functools
    MISERE = 'misere'
    NORMAL = 'normal'
    def nim(heaps, game_type):
        """
        Computes next move for Nim, for both game types normal and misere.
        Assumption : Both players involved would play without making mistakes.
        if there is a winning move:
            return tuple(heap_index, amount_to_remove)
        else:
            return "You will lose :("
        """
        print(game_type, heaps, end=' ')
        is_misere = game_type == MISERE
        endgame_reached = False
        count_non_0_1 = sum(1 for x in heaps if x > 1)
        endgame_reached = (count_non_0_1 <= 1)
        # nim sum will give the correct end-game move for normal play but
        # misere requires the last move be forced onto the opponent
        if is_misere and endgame_reached:
            moves_left = sum(1 for x in heaps if x > 0)
            is_odd = (moves_left % 2 == 1)
            sizeof_max = max(heaps)
            index_of_max = heaps.index(sizeof_max)
            if sizeof_max == 1 and is_odd:
                return "You will lose :("
            # reduce the game to an odd number of 1's
            return index_of_max, sizeof_max - int(is_odd)
        nim_sum = functools.reduce(lambda x, y: x ^ y, heaps)
        if nim_sum == 0:
            return "You will lose :("
        # Calc which move to make
        for index, heap in enumerate(heaps):
            target_size = heap ^ nim_sum
            if target_size < heap:
                amount_to_remove = heap - target_size
                return index, amount_to_remove
    if __name__ == "__main__":
        import doctest
        doctest.testmod()       
   

Applications in Game of Nim


Now, about the applications of the above discussed two arithmetic sequences. We can use Nimber Addition to solve the famous game of Nim, So, how do we do it?

Notice that if we take the sum of all the nim-heaps, at the end the nimsum of all the heaps is equal to 0 (since adding 0 together any number of times gives 0). But there are other times that the nim-sum can be 0. Note that any x⊕x = 0, since any number XORed with itself is 0.

So, the winning strategy is easily :

  • Whenever possible, reduce the heaps to two non-zero heaps containing the same number of coins each. This obviously has a nim-sum of 0.Now just mimic your opponent’s move each time on the opposite heap to keep the two heaps equal until you are able to take the final coin.

  • Since doing binary addition is kind of hard to do in your head for large numbers, a more feasible strategy is often needed. An easy way to think about making the nim-sum 0 is to always leave even subpiles of the powers of 2, starting with the largest power possible, where a subpile is a pile group of coins within a nim-heap. So for example, leave an even number of subpiles of 2, 4, 8, 16, etc. Any time there are an
    even number of piles of each power of 2, the nim-sum must be 0.

Now, if we look at the major application of Nim multiplication, it can be seen in this fun problem of Seating the first few Billion Knights

The odd Knight of the round table problem asks for a consistent placement of the nth Knight in the row at an odd root of unity, compatible with the two different realizations of the algebraic closure of the field with two elements.

The first identifies the multiplicative group of its non-zero elements with the group of all odd complex roots of unity, under complex multiplication. The second uses Conway’s ‘simplicity rules’ in ONAG to define an addition and multiplication on the set of all ordinal numbers.

nim multiplication formula

Here’s the seating arrangement for the first 15 knights. Conway proved that all finite ordinals smaller than 22i form a subfield of F2. The first non-trivial one being {0,1,2,3} with smallest multiplicative generator 2, whence we place Knight 2 at e2iπ/3 and as 22=3 (using 0 index of the {0,1,2,3}) we know where to place the third Knight.

The multiplicative algorithm utilized in a 2.4Ghz 2Gb MacBook with Sage 4.6 (According to the source documentation) is :

sage: R.< x,y,z,t,u >=GF(2)[]

sage: S.< a,b,c,d,e > =
R.quotient((x^2+x+1,y^2+y+x,z^2+z+x*y,t^2+t+x*y*z,u^2+u+x*y*z*t))

sage: (c*e+b*e+a*b*c*d+b*c*d+a*b*d+a+1)^65537
c^2 + b*d + a + 1

This utilizes Multiplicative Nimber to a certain extent!


Questions


To get a perfect nimber matrix, what should be the number of rows for the same? ( here ^ is raise to the power)

2 ^ n
3 ^ n
5 ^ n
7 ^ n

Are the middle game semantics for misère and normal gameplay different for nim?

No
Yes

Further Reading