# 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?
- XX (1 sticks)
- XXXX (4 sticks)
- XXXXXXX (7 sticks)

### Try It

- Click on the link to play the game http://www.transum.org/Software/Nim/
- How did you win this time?
- Is it the same algorithm to win?

### 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?

### Badge It Silver

- 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.

### Badge It Gold

- Write a working two-player game of 21 in Scratch. Upload a screenshot of your code; the week one notes will help.
**OR…**- Modify the code above, so that you can complete level 5 and level 6 of the online Nim game. Upload a screenshot of the level 6 victory screen as evidence, and a seperate screenshot of your code.

### Badge It Platinum

- Implement a one-player version of '21' Nim in Scratch, so that you can play with a computer opponent. You may wish to look back at the last lesson's notes for hints.
- The computer should randomly choose to play either a 1, 2 or 3.
- Implement a strategy that means the computer will always win when it goes first.