Nim

Nim is a simple game. To begin, the first player draws several columns with varying amounts of circles in each column. The second player chooses whether they want to go first or second. Players then take turns marking off circles with an X. During your turn, you can mark off as many circles as you want, but only from one column. Whoever marks off the last circle is the winner.

Example Nim game between two players with blue set to win on the next move.

Strategy

If you understand the mathematics of this game, you can guarantee a win for yourself, provided you can choose who goes first. If you can't choose who goes first, you can still win if your opponent makes a mistake. To understand the strategy, lets start with the simple cases and work up from there.

If there is only one column of circles, the strategy is trivial. Choose to go first, mark all the circles and you win!

If there are two columns, the strategy is to keep the two columns equal in size. If you make sure that each column has the same number of empty circles, at some point your opponent will be forced to mark the last circle in one of the columns. There will now be one column left and it will be your turn, so you can easily win as described above. Therefore, if the game starts with the two columns already equal, you should choose to go second. If the game starts with unequal columns you should go first and make them equal. Then on subsequent turns, mirror your opponent's move into the other column to keep them equal.

If there are three or more columns it gets a little trickier. By understanding the two column strategy we can make some simplifications to help us when there are more. The import thing to recognize is that two columns of equal size, at the end of your turn, will guarantee you a win. So, in a game with more columns, if any two of them are equal in size, then you can safely ignore them and focus on the other columns. Because, if you can win the sub-game of only the other columns, then you will be left with the two equal columns and you can win that as well. For example, suppose we have three columns with lengths 4, 4 and 5. We already know from the "two column" strategy that we can win the 4, 4 pair if we go second. So, we'll focus just on winning the column of 5. We know from the "one column" strategy that we can win by marking all the circles. So, the full strategy for this game is to go first, mark all 5 circles in that column and then mirror your opponents moves from then on in the other two.

This is the key insight for a full strategy to winning the game. Matching up equal sized columns and focusing on the remainder. Sometimes this isn't possible by itself because several of the columns can be of unequal size, and so we come to the last concept that we need to learn, which we'll call power groups. This involves matching up groups of circles within one column to another column. Think of it as matching sub-columns. The only tricky thing (because of the math) is that the groups must be in the powers of two (1, 2, 4, 8, 16 ...). For example, a column of three circles would be broken down into two power groups of sizes 1 and 2, and a seven circle column would be broken down into power groups of size 1+2+4.

This image shows how you would mentally break down the columns into power groups to decide how many circles to take on your turn. Here we can see that the groups of size 1 (yellow) are balance. The groups of size 2 (blue) are balanced. There are three groups of size 4, which is an odd number, so it is unbalanced. We match up two of them (green) and our strategy would be to mark off the other four circles (colored white) to make the game balanced at the end of our turn.

The full strategy can therefore be summarized into one sentence. Mentally break down the columns into groups that all have a size equal to a power of two, and then keep all of these groups balanced such that there are an even number of each size at the end of your turn.

Here is another example. In the situation on the left you have three power groups that are unbalanced. There are an odd number of groups of sizes 1, 2 and 4. The way to balance this on your turn is to mark one circle from the group of 4. This will turn it into a new group of size 3 which breaks down into power groups of sizes 1 and 2. Now it's balanced.