On the Subject of Nim

But not too much.

Beat the module in the match-taking game of Nim.

How to play

In Nim, two players take turns taking as many matches as they want, from a single row. Take the last match to win (normal play, no misère game).

Click on a row as many times as the number of matches you wish to take. After a couple of seconds thinking time, the module will take a turn.

When you lose the game, you get a strike and the module resets to a new random configuration.

How to win

The key to the theory of the game is the binary digital sum, or “bitwise xor”, of the row sizes. This is referred to as the nim-sum, and can be written with this symbol: ⊕. An example of the calculation with rows of size 3, 4, and 5:

             Decimal    Binary
    Row A          3       011
    Row B          4       100
    Row C          5       101 ⊕
             -----------------
                   2       010

The nim-sum of rows A, B, and C is 3 ⊕ 4 ⊕ 5 = 2.

The winning strategy is to finish every move with a nim-sum of 0. This is always possible if the nim-sum is not zero before the move. If the nim-sum is zero, then the next player will lose if the other player does not make a mistake. To find out which move to make, let X be the nim-sum of all the row sizes. For each row, let Y be the nim-sum of X and the row-size. If Y is less than the row-size, the winning strategy is to reduce that row to Y. In the example above, with a nim-sum of X=2:

    A ⊕ X = 3 ⊕ 2 = 1 (Since binary 011 ⊕ 010 = 001)
    B ⊕ X = 4 ⊕ 2 = 6
    C ⊕ X = 5 ⊕ 2 = 7

The only row that is reduced is row A, so the winning move is to reduce the size of row A to 1, by removing two matches. More info on Wikipedia.