Nim
Nim Rulebook
Table of Contents
Table of Contents
The Game of Nim
We first look at the simple game of Nim, which led to some of the biggest advances in the field of combinatorial game theory. There are many versions of this game, but we will look at one of the most common.
How To Play
There are three piles, or nim-heaps, of stones. Players 1 and 2 alternate taking off any number of stones from a pile until there are no stones left.
There are two possible versions of this game and two corresponding winning strategies that we will see. Note that these definitions extend beyond the game of Nim and can be used to talk about impartial games in general.
-
Normal Play: The player to take the last stone (or in general to make the last move in a game) wins. This is called normal play since most impartial games are played this way, although Nim usually is not.
-
Misere Play: The player that is forced to take the last stone loses.
An example normal play game is shown below:
| Sizes of heaps (A B C) | Moves |
|---|---|
| 3 4 5 | I take 2 from A |
| 1 4 5 | You take 3 from C |
| 1 4 2 | I take 1 from B |
| 1 3 2 | You take 1 from B |
| 1 2 2 | I take entire A heap leaving two 2's. |
| 0 2 2 | You take 1 from B |
| 0 1 2 | I take 1 from C leaving two 1's. |
| 0 1 1 | You take 1 from B |
| 0 0 1 | I take entire C heap and win. |
What is your winning strategy? Luckily, we can find one. Nim has been solved (we use the term solved loosely here, but there are several categories of "solutions" to games) for all starting positions and for any number of heaps.