Français

### The Nim Game

Customize the Starting Position

Total number of plays: 61414

Computer Wins: 51963

Player Wins: 9451

Computer Wins: 51963

Player Wins: 9451

How do you beat the computer? Click here to find out.

## The Winning Strategy

In most cases, you must always take as many matches so that the*Nim Sum*of the rows is zero. Repeat this until there are very few matches left, then you must take matches such that your opponent takes the final match.

### What is a *Nim Sum*?

Count the matches in each row, and convert the number into a sum of powers of 2 (8, 4, 2 and 1).
Then cancel out pairs of equal powers, and add what is left. So the *Nim Sum*of the starting position is:

Row 1 | = | 1 |
= | 1 x 1 |
= | 1 | ||

Row 2 | = | 3 |
= | 1 x 2 + 1 x 1 |
= | 2 | 1 | |

Row 3 | = | 5 |
= | 1 x 4 + 1 x 1 |
= | 4 | 1 | |

Row 4 | = | 7 |
= | 1 x 4 + 1 x 2 + 1 x 1 |
= | 4 | 2 | 1 |

Total of unpaired powers |
= | 0 |
0 |
0 |

As you can see, there are two red 4's, two green 2's, and two blue 1's and another two purple 1's. Both of the 4's cancel, both of the 2's cancel, and two pairs of 1's cancel out, leaving the

*Nim Sum*zero.

To win at the Nim game, you must always make a move that leaves a configuration with a zero

*Nim Sum*, that is, the position has no unpaired 4's, 2's or 1's. Otherwise, the opponent has the advantage, and they must make an error for you to win.

### How To Leave a Zero *Nim Sum*

First, you need to calculate the *Nim Sum*of the position you have, find any unpaired power, and get rid of the unpaired number by removing the proper number of matches. For example, if your opponent goes first, and remove 2 matches from Row 4. That leaves the following configuration:

Row 1 | = | 1 |
= | 1 x 1 |
= | 1 | ||

Row 2 | = | 3 |
= | 1 x 2 + 1 x 1 |
= | 2 |
1 | |

Row 3 | = | 5 |
= | 1 x 4 + 1 x 1 |
= | 4 | 1 | |

Row 4 | = | 5 |
= | 1 x 4 + 0 x 2 + 1 x 1 |
= | 4 | 1 |

Total of unpaired powers |
= | 0 |
2 |
0 |

Here, the

*Nim Sum*is 2. The two 4's cancel, and the four 1's cancel, but the 2 is unpaired. So the winning move is to get rid of the unpaired 2. Removing 2 matches from Row 2 will leave the

*Nim Sum*at zero, and you have a winning position.

Row 1 | = | 1 |
= | 1 x 1 |
= | 1 | ||

Row 2 | = | 1 |
= | 0 x 2 + 1 x 1 |
= | 1 | ||

Row 3 | = | 5 |
= | 1 x 4 + 1 x 1 |
= | 4 | 1 | |

Row 4 | = | 5 |
= | 1 x 4 + 0 x 2 + 1 x 1 |
= | 4 | 1 |

Total of unpaired powers |
= | 0 |
0 |
0 |

Now, any move your opponent makes will result in a non-zero

*Nim Sum*. If you play continue to play correctly, you will win the game.

### Final Notes

The default starting configuration has a*Nim Sum*of zero. The player that starts the game must always leave a non-zero

*Nim Sum*after the first move, which the second player can take advantage of, as we saw above. Therefore,

**you are always at a disadvantage if you start the game first at the default configuration!**If you want to win, let the computer begin the game. However, with a random starting position the

*Nim Sum*will probably be non-zero and the first player can force a win.

Also, it should be said that this method does break down when the game is almost over. For example, if you have two rows with one match each, this position has a

*Nim Sum*of zero, but the player who moves first in this position wins. The

*Nim Sum*method works for all positions with more than three matches. Keep that in mind as you are trying to beat the computer. Good luck!