Problem Solving : Nim

Many people see playing competitive games 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)! The first computer dedicated solely to gaming, called the Nimatron, was created in 1940 to play Nim. Today, you will work in pairs to develop an algorithm for winning the two-player game Nim, in which players take turns removing chips from a pile, one or two chips at a time. The last player to take any chips 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 chips were at hand, stones, sticks, matches, bits of paper, or coins. Nim is completely winnable every time (if you get to choose who goes first) since there is no randomness involved.  Your task is to figure out how to win this game, every time, by examining the game’s mathematical structure.

In pairs, practice a common problem solving process that will help you when starting any programming project:

Step 1: State the problem

Always start by making sure you understand the problem you are trying to solve by restating it concisely and as unambiguously as you can, including any constraints and assumptions.

I will do this step for you:

• You and your opponent begin with a pile with some known number of candy, tokens, coins, or something (we will refer to them as “chips”).
• Each player takes turns, removing either one or two chips from the pile.
• The winner is the last player to remove from the pile, leaving your opponent with no chips.

Step 2: Work Examples

Play the game, i.e., work examples, and also reflect on why you are making the moves you are, i.e., do research, and also record what you did and what the outcome was in each case. Start by considering the simplest cases first, then increasingly harder cases, until you feel like you understand the problem being solved.

The number of chips, denoted by N, in the pile varies from game to game, but you can assume that both players know the initial number. To help get you started, consider the following values for N, the initial number of chips in the pile. With such a small starting value, you can enumerate all possible outcomes of playing the game.

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

Step 3: Find Patterns and Make a Hypothesis

Study your work to find general patterns that lead to a win.

After working several examples and playing several games, you may be starting to develop an idea of how to play the game in a winning fashion and which values of N guarantee a win or a loss.

Use these patterns to make a hypothesis about your algorithm, i.e, how many chips you should take on your turn (no matter what your opponent will do).

Step 4: Test your Hypothesis

Play more games, using with your hypothesis algorithm to determine if it works or not.

If you believe it works in general, move on to the next step. Otherwise, iterate by playing more example games, making another hypothesis, and testing it.

If you are stuck, try to simplify the problem further with one or more of these strategies:

• Record your examples in different formats. See if you can draw a diagram or make a table. If you are dealing with long equations, make a variable that represents a large part of it, then rewrite the problem using your new variable.
• Work smaller versions of the problem. Turn any numbers into small numbers.
• Consider only one part of the problem. If you are dealing with a picture, try looking only at one quadrant of the picture. If you are coming up with a multi-step solution, concentrate only on the first part.
• Make more assumptions. Try making the problem easier by assuming you will only get certain kinds of input or that you will start in some helpful scenario.
• Cancel some constraints. Take away some of the “don’ts” from the problem statement.
• Work backwards. Pretend you know the solution or are at the end of the process and think about the step just before that, then before that, and look for a pattern.

Step 5: Verify the Solution

Why do you believe your hypothesis is correct: does it make intuitive sense or follow some mathematical rules?

Now that you think you have a winning algorithm, see if you can “break” it by describing a game situation not covered by your algorithm or by giving a game situation that results in a loss rather than a win. Write down a few of these situations to convince you (and eventually me) that your solution is 100% solid. Make sure to consider the case in which your algorithm will fail to work because it is impossible for the first player to win.

If you do “break” your algorithm, go back to step 3 and refine it.

Step 6: Write the Solution in Detail

When you solve a problem, it is not enough for you to know the solution, but you need to be able to clearly express that solution such that anyone (and eventually a computer) could follow it.

Make sure to be clear, concise, and cover all aspects of game play.

Optional: Multiple Piles

If you have time left, consider the case when there are two piles from which to take chips and a player can take 1 or 2 chips from any one of the piles during their turn.

Initially, this version may seem much harder because there are considerably more choices for each move, but work through it using the Problem Solving process again.

The number of chips, denoted by N and M, in each pile 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 chip 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 opponent into the losing state above, making herself the winner.

Start your analysis by considering similar games to those above to see if you can derive a pattern. In particular, what strategic value does the extra pile provide you as a player?

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

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

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