# Nice but NIM

## Introduction

### Document It

• Watch the video…
• Write an algorithm to solve the bridge riddle. You need to get everyone, in pairs, across in 17 minutes before the zombies get you.

### Learn It

• Recap - "Nim" is a two-player game played with sticks or stones. The objects are divided into piles.
• The players alternate turns. On each player's turn they may remove any number of sticks from one of the piles, up to the number of sticks remaining in that pile; but they can only take from a single pile on a given turn.
• The goal is to take the last stick. Whoever takes the last stick wins.
• So the goal is to make the other person clear out all but one pile, so you can take all the sticks in that last pile. Etc.
• Let's play a game starting from the game state 1, 4, 7. You can go first.
• How many sticks are you going to take and from which pile?
1. XX (1 sticks)
2. XXXX (4 sticks)
3. XXXXXXX (7 sticks)

### Document It

• Save your certificate/s to show how many levels you passed on the NIM game in 5 minutes.

### Learn It: Strategy

• There is a known winning strategy to playing 'Advanced NIM'. Let's use a simple example to illustrate how to use this strategy.
• Let's say you have three piles with 1, 4 and 7 stones:
• X
• XXXX
• XXXXXXX
• To find out the optimal move, we first express the count of each pile as a binary number, using this table:
Decimal Binary
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
• Next we perform a special operation on these binary numbers, by following the following process:
• For each column of digits, if there are an even number of 1's, write a zero at the bottom of that column. If there are an odd number, write a one. This is called the `Bitwise exclusive or` operation.
Pile Sticks Binary Denary
1 X `0001` 1
2 XXXX `0100` 4
3 XXXXXXX `0111` 7
pile-sum: `0010` 2
• In the example above, the right-most column has a 1, then a 0, another 1. There are an even number of 1s (two of them), so we write `0` at the bottom of the column.
• The next column (third from the left) has only one `1` in it; an odd number. We write a `1` at the bottom of that column.
• The resulting 4-bit number (0010 in this example) is called the pile-sum.
• To win, we want to get the pile-sum to total `0000` after our turn.
• Looking over the numbers above, it looks like if we took the pile-sum away from the third pile, we'd changing a 7 (`0111` in binary) to a 5 (`0101` in binary). The pile sum would then be `0000`.
• On the other player's turn, it now doesn't matter which pile they take from, as long as you reduce the pile sum back to `0000` on your turn.
• You can now continue this process until you win the game by taking the last stick.
• If your opponent knows the strategy and leaves you with a pile sum of `0000`, then you will lose, assuming perfect play on their part.

### Code It

• This is a lot of mental calculation. It'd be better if we wrote a program in Python to tell us our moves, so that we can always win!
• To write this program, we'll need to take several steps.
• We need the ability to convert the denary numbers into their binary equivalent.
• This will need to ask for the three numbers and convert them into binary.
• We will need to XOR these binary numbers to get the pile sum.
• Finally, we should advise the player of what to do.
• Now we've a general plan, let's get started…
• Step 1: Make a function to convert denary to binary. A quick Google search tells us that Python has a built-in function to handle this.
• Step 2: `XOR` function. Google to the rescue again; Python also has some built-in functions to do the `XOR` operation for us, by using the `bin(a ^ b)` function.
• Our code now can be updated to include this new functionality…
• Step 3: Once we know this information, we can calculate which pile to remove sticks from, and how many to take.
• The Trinket below shows a solution for a 3-pile game. You can use this to complete up to level 4 on the online Nim game.

### Research It

• What is Exclusive Or (XOR)?
• How do we use it in Computer Science?

• Write a set of rules for someone who has never played '21' before so that they will always win. You may need to re-read the week 1 notes for this.
• OR…
• Use the helper program to win Nim level 2 on the online Nim game. Upload a screenshot of the victory screen as evidence.