Games and Problem Solving

Many people like to play competitive games, thus they are seen as an activity that requires intelligence. This made them an easy target for scientists studying Artificial Intelligence, or the science of building things that appear intelligent. It quickly became clear to these early researchers that many games can be played and won using simple algorithms, rather than actual intelligence (of course, it often takes a great deal of intelligence to find the necessary algorithm)!

Develop an algorithm for winning the two-player game Nim, in which players take turns removing objects from heaps, one or two objects at a time but only from a single heap. The last player to take any objects is the winner. Nim probably originated in China (where it was called Tsyanshidzi, meaning "picking stones game"), the current name of this game probably comes from the German verb nimm (meaning "take!"). Nim-type games have existed for centuries around the world and were evidently played with what ever objects were at hand, stones, sticks, matches, bits of paper, or coins.

The first computer capable of playing Nim, called the Nimatron, was created in 1940. This one ton machine was built by the Westinghouse Electrical Corporation and was exhibited at the New York Worlds Fair. In 1951 a Nim playing robot, called Nimrod, was exhibited at the Festival of Britain, and later at the Berlin trade fair. The machine was so popular that spectators entirely ignored a bar at the other end of the room where free drinks were being offered. Eventually the local police had to be called in to control the crowds. These machines won over 90% of the games they played!

Nim is not a fair game. Given the right conditions at the begining of the game, there is a strategy such that the player who starts can never lose. Your task today is to develop a winning algorithm for several versions of the game of Nim. You should also note the situations in which your algorithm will lose the game.

Start Simply: One heap

The first step to developing an algorithm is to consider the simplest cases first, then increasingly harder cases, until you can find a general pattern that you can use to handle all cases. For Nim, the simplest case is when there is only one heap from which to take objects. This variant is often called the Subtraction Game, but was called Thai 21 when it was used as an Immunity Challenge on the reality show Survivor.

The number of objects, denoted by N, in the heap varies from game to game, but you can assume that both players know the initial value of N. To help get you started, consider the following values for N, the initial number of objects in the heap. With such a small starting value, you can enumerate all possible outcomes of playing the game. If done carefully, you may see a pattern in which values guarantee a win or a loss.

1. Consider the case where N is 3.
2. Consider the case where N is 5.
3. Consider the case where N is 8.

Give an algorithm to use each time it is your turn that guarantees you win the one heap version of the game. In which case will your algorithm fail to work because it is impossible for the first player to win.

Two Heaps

Next, consider the case when there are only two heaps from which to take objects. Initially, this version may seem much harder because there are considerably more choices for each move, but start your analysis by considering similar games to those above to see if you can derive a pattern. In particular, what value does the extra heap provide you as a player?

Again, the number of objects, denoted by N and M, in each heap will vary from game to game, but you can assume that both players know the initial values of N and M. For example, if the game was at the point where there was only one object in each pile, represented as (1, 1), then the current player is forced to empty one pile, leaving her opponent as the winner. On the other hand, if the current state is (1, 2), she can force her oppenent into the losing state above, making herself the winner.

Consider all possible outcomes when the game starts with N as 3 and M as 4.

Describe, but do not code, an algorithm to use each time it is your turn that guarantees you win the two heap version of the game. In which case will your algorithm fail to work because it is impossible for the first player to win?

Generalize: N-Heaps

Finally, can you determine how to generalize your previous strategies to win the game of Nim, no matter how many heaps there are?