Introduciton & Rules

I recently did a project for the course Experimental Mathematics about an extension the game Nim, called Nim squared. The rules are quite simple; on an n by m chess board there are on each square at most one peg. The two players take turns to remove pegs from the board, following the rules:

1. You can only remove pegs from one row or column each turn.
2. You must remove at least one peg.
3. The player who removes the last peg wins the game.

So for example the following is a game of 3 by 3 Nim squared:

1
2
3

xox     xox     ooo     ooo
xxx --> oxx --> oxx --> ooo
xoo     ooo     ooo     ooo

Since this is a perfect information game, we know that given some starting configuration, one the players can force a win, if they play optimally. If the previous player can force a win we call it a P-position and an N-position if the current player can force a win.

In fact, P/N-positions can be defined recursively as follows:

1. The ‘empty’ position (no pegs on the board) is a P-position
2. A non-empty position is an N-position if there exist a move by which the current configuartion can be transformed into a P-position. Otherwise the current configuartion is a P-position.

Finding the P-positions

Given some dimension, n by m, if you knew all the P-positions then one could write them all down, create a lookup table and easily make an algorithm which will always win in Nim squared. Thus we want to compute all the P-positions.

The first step towards this goal is to realise that there is a bijection between all game configurations and the list [0.. 2^(d_r d_c)] where d_r and d_c are the row dimension and column dimension, respectively. The mapping is given by reading each row of the board from left to right and writing “1” if there is a peg and “0” if there isn’t. For example:

1
2
3

xxox
oxxo <--> xxoxoxxoxoox <--> 110101101001 <--> 3433
xoox

Furthermore we can also encode a legal move as a board configuartion and then as some number as well. This is done by starting with the full position (all pegs on the board) then choosing a row or column and removing some combination of the pegs of that row/column. For example the move where we remove the first two pegs of column 3 can be represented as

1
2
3

xxox
xxox --> xxoxxxoxxxxx --> 110111011111 --> 3551
xxxx

The way we apply this move is by applying an entrywise and AND-operation (&&) of the current board with the ‘move board’:

1
2
3

xxox    xxox   xxox
oxxo && xxox = oxoo
xoox    xxxx   xoox

Translating this operation into the realm of the binary representation of the configurations we see that this is exactly the bitwise AND operation. This is great because computers are insanely fast at applying these operations.

Using these facts together with the recursive definition of P-positions, we arrive at the following algorithm, inplemented in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def genPos(dimr, dimc): 
    ppos = set()
    ppos.add(0) 
    moves = genAllMoves(dimr, dimc)
    lim = 2**(dimr*dimc)

    for state in range(1, lim):
        for move in moves:
            nextstate = state & move # bitwise AND
            if nextstate == state:
                continue
            if nextstate in ppos: 
                break
        else:
            ppos.add(state)
    return ppos

(Note that ppos will be sorted, so one could use a binary search for nextstate in ppos, however sets use hash tables which allow faster search algorithms in exchange for higher memory usesage.)

Here the genAllMoves function returns a list of all possible moves encoded as numbers. This function isn’t too hard to construct and won’t take too long to compute regardless.

The data and Patterns therein

Computing the number of P-positions for various dimensions n and m yields the following data

Immediately we see that, fixing one dimension, the number increases seemingly exponentially as the other dimension varies.

Another interesting pattern you’ll notice, if you look at the P-positions that you get, is that some of them have an ‘inverse’, where by inverse we mean flipping 1 to 0 and 0 to 1. We can actually easily check if a given p-position has an inverse by XOR’ing the P-position with the full board. In python this can be implemented as follows

1
2
3
4
5

hasinv = []
for p in ppos:
    q = p ^ (2**(dimr*dimc)-1) # bitwise XOR
    if q in ppos:
        hasinv.append(p)

If we look at the length of hasinv for various dimensions we get the following, quite interesting, table:

There’s a lot going on here. A lot of seeming sporadic 0’s, however if we fix one dimension to be 2, we get a sequence which alternates between 0 and all P-positions, i.e. the P-positions of a 2xm game either all have inverses (if m is even) or has no inverses (if m is odd). Very nice! However if we look at the 3xm games it’s a lot more complicated, sometimes we have inverses (but only a few) and sometimes we have none at all, in no immediately obvious pattern. Hmmm…

The 2xm games

If you look at the sequence you get from fixing one dimension to be 2, we get the sequence

1, 1, 4, 10, 38, 126, 472, 1716, 6470, 24310, 92504

which is exactly the sequence A032123 in the OEIS. This sequence has various different descriptions (e.g. as some binomials (with some mod 2), as the central column of the Losanitsch’s triangle, or as strings of beads), which we tried generalizing (binomials with some mod 3, or a 3 dimensional Losanitsch pyramid) in hopes of seeing the sequence for 3xm games, but to no avail. Perhaps the dear reader could take a jab at a generalizating of these (hint hint vink vink)?

It is also very possible this special case of Nim squared is extra special, as it turns out all P-positions of 2xm games are simply combinations of the four P-positions of the 2x2 game. (And in fact when m is odd we have an extra column of 0’s, why the odd 2xm games have no inverses). This is not the case for higher dimensions.

So the 2xm case is quite well understood, but the nature of the higher dimensions remain unknown.