Selecting an Optimal Next Move in Nim

Nim is a mathematical game where you have a number of piles and each pile contains a number of items. Players take turns at each taking at least one and at most all of the items from a single pile of their choosing. The winning player in nim (in its standard form) is the player who has left all piles empty following their move. Nim is traditionally played with 3 piles of 3, 4, and 5 items.

The way to guarantee a win is to always pick a move such that after the move has been executed, the binary digital sum (nim-sum) of each pile is equal to 0. The binary digital sum is the sum of the binary forms of the numbers, without carrying. This turns out to be the same as applying the exclusive-or bitwise operation over all piles.

Given the number of items in each pile, determine the optimal move you should execute in the form (pile to remove from, number of items to remove).
To calculate the nim-sum of the piles we have to apply XOR over all the piles. The easiest way to do this is with the reduce() function. If you haven't encountered reduce() before, it comes from the same functional roots as map() and filter(), but its purpose is to condense a list of type t into a single instance of t** by applying a function between each successive pair and 'folding' itself up. Here's an example of the sum() function implemented as a reduction:

>>> print reduce(lambda a, b: a + b, [1, 2, 4, 8])
15

This is evaluated as (((1 + 2) + 4) + 8). To get the nim sum, we apply a very similar procedure except instead of using a function to add two numbers together, we'll use a function to get the exclusive-or of two numbers. Fortunately Python's already given one to us: int.__xor__. The nim-sum of a game state is therefore:

nim_sum = reduce(int.__xor__, state)

But this is only half the job! We need to go through all possible moves we can make and find one that would leave the game state with a nim-sum of 0.

We're not too concerned about efficiency so we're gonna loop through every possible pile and for each pile, try to remove every possible number of items and see if any of the remaining game states have a nim-sum of 0. The game state will be represented as a list where each element represents the number of items in that pile. The following line of code will give us the result of removing num items from the pile pile:

game[:pile] + [game[pile]-num] + game[pile+1:]

All we're doing is modifying the selected pile then sandwiching the result in between the rest of the piles where it was before.

When you combine all this and add two loops you have yourself a function which, given a game state, will give you a move you can make which results in a nim-sum of 0.

def nextMove(g):
    for p in xrange(len(g)):
        for n in xrange(1, g[p]+1):
            if reduce(int.__xor__, g[:p] + [g[p]-n] + g[p+1:]) == 0:
                return p, n
    return None, None

---

**This is not always the case -- a reduce can theoretically return any type. However, if it is given a list of [t] it will generally return an instance of t.