The purpose of this lab is to implement an optimal algorithm & a user-friendly interface to play the game of Nim. This is an interesting challenge for 3 reasons:

The game of Nim is a rare case of a strategy game, which is "solved" in the sense that if an optimal move exists, it can be always quickly computed, and if no optimal move exists, it can be quickly proven to be the case. This is unlike the games of Chess or Go, for which new algorithms constantly appear, all take a long time to compute, and none deliver provably optimal results.

The optimal algorithm to play the game of Nim uses bitwise exclusive or, which is otherwise important in Software Engineering & Computer Science, and you'll have to know it in your further studies & in your future job.

User interface needs to support several modes: player vs player, player vs computer, computer vs computer. There are interesting usability & user experience choices to be made in the final user-facing implementation of the game.

This lab **is not** assessed. However, we're trialling a new way of giving students immediate feedback on their programming exercises. As a result this lab has different structure than other labs.

- This document gives a high-level overview and explains the necessary concepts underlying the lab.
- Exercises are split off into separate files. Each file includes the exercise boilerplate and exercise-specific description. You will have to work with them using a text editor, like idle or vscode or an IDE like pycharm. If you want to use jupyter, please copy and paste your jupyter solution back into the file when you're finished. Work through the files in the following order:
- present_board.py
- make_move.py
- exclusive_or.py
- bin_num.py
- bitwise_xor.py
- nim_sum.py
- optimal_move.py
- ui.py
- working_game.py

- (optional) When you're finished with a file, you can submit it for automated testing at http://grader.givegrade.me.uk. Your username is your GUID + first letter of your surname (small case), for example, the username of Adam Kurkiewicz is 1102499k. Your password is the last 8 digits of your barcode, for example 12345678. This step is optional -- you don't have to use automated marking.
**Automated Feedback Warning:**the software used for automated feedback was originally developed for programming contests, and terminology might be somewhat confusing. When you log in to the website, find the name of the exercise you've done on the left pane, and press*Submission*. You can then choose a file from your filesystem (e.g. present_board.py) and press*Submit*. Your code will be automatically tested for correctness.**Automated Feedback Warning:**make sure you remove all dangling`print`

s you've used for debugging, etc. Automatic tester doesn't like them!**Automated Feedback Warning:**make sure your solution works in Python 2 (for the automated grader) as well as Python 3 (official course requirement). Stubs of exercises already import`print_function`

and`division`

, which should make this requirement very easy to satisfy.**Automated Feedback Warning:**each exercise file waits for test input on the standard input. It might appear like your program is stuck in an infite loop but it probably isn't! This is to aid automated testing, and you can remove this if you don't want to submit your code to http://grader.givegrade.me.uk.**What**

In the game of Nim two players, Alice and Bob, are presented with a finite number of rows containing a variable number of elements. For the sake of presentation, let's say 5 rows:

```
Nim:
1: X X X X X
2: X X X X
3: X X X X X
4: X X
5: X X X
```

In each turn, a player chooses a row and how many items to remove from the row (the number of items has to be greater than zero). It's Alice's turn, and she decides to remove elements from row 3 and she wants to remove 2 elements:

```
Alice: 3, 2
Nim:
1: X X X X X
2: X X X X
3: X X X
4: X X
5: X X X
```

Row 3 is reduced by 2 elements from 5 to 3 elements. It's now time for Bob to play. Bob decides to remove items from row 1, and he wants to remove all 5 items:

```
Bob: 1, 5
Nim:
1:
2: X X X X
3: X X X
4: X X
5: X X X
```

The game continues with players taking turns, and eventually it's Alice's turn and the board looks like this:

```
Nim:
1:
2:
3:
4:
5: X X
```

Alice can now remove the last two elements from the last row. Because she is the last one to make the move, she wins and this is how the game ends.

```
Alice: 5, 2
Nim:
1:
2:
3:
4:
5:
Alice wins
```

**Note:** game of Nim is relatively well-known, and there are online implementations of the game, which may aid your understanding. A good example is here.

Please accomplish the following programming task before your scheduled lab

Task description in `present_board.py`

Task description in `make_move.py`

Task description in `exclusive_or.py`

Task description in `bin_num.py`

Task description in `bitwise_xor.py`

Most people when presented with a (very difficult) challenge of designing an algorithm to play Nim optimally follow a similar thought pattern (and quickly get stuck):

- There can't be a draw, so one of the players must have a winning strategy!
- The player who begins has a winning strategy!
- No, the player who goes second has a winning strategy!
- Let's try all possible move combinations of some position X
- But there is too many...

It turns out that for any board position there are only two possibilities:

- No good move exists. If it's our turn to move and our opponent plays perfectly, whatever move we choose, we loose. These board positions are called "N-positions".
- There is a winning move, and if it's our turn to move our opponent is guaranteed to loose, unless we make a mistake. These board positions are called "P-positions".

There are 2 important remarks about this statement:

- The fact that these are the only two options is not automatic. For example in chess, there is also a third option -- the draw. In go draws may or may not be possible depending on exact version of the rules being played (check out the "superko" rule and "komidashi"). What makes Nim different is that the number of elements on the board is finite to begin with and always decreasing (a pass or adding more elements isn't possible), which guarantees that one of the players will eventually remove the last element and win.
- The fact that one of the players has a winning strategy doesn't necessarily imply that the winning strategy is easy to discover or can be computed efficiently. In fact a stronger statement is true: for some games we know that the
**first player**to move*has*a winning strategy, but we still have no idea*what*that strategy is. If you're curious how this can possibly work, check out the strategy-stealing argument due to John Nash. What makes Nim special is that we can quickly decide, given any board, whether it is in a "N-position" or in a "P-position". The rest is easy: we have to always leave the board in a "N-position" after our move.

How can you tell if the board is currently in a N-position?

It turns out that all you have to do is to compute bitwise exclusive-or cumulatively over all row lengths. If the result is 0, then the board is in a N-position. If the result is non-zero, then the board is in a P-position.

For example, the board [5, 4, 3, 2] is in a N-position, because `((5 ^ 4) ^ 3) ^ 2 == 0`

. Since bitwise exclusive-or is associative, `5 ^ (4 ^ (3 ^ 2)) == 0`

also works.

The value of the cumulative exclusive-or is called the Nim sum. The Nim sum of the board position `[5, 4, 3, 2]`

is `0`

.

In [6]:

```
((5 ^ 4) ^ 3) ^ 2
```

Out[6]:

In [7]:

```
5 ^ (4 ^ (3 ^ 2))
```

Out[7]:

Task description in `nim_sum.py`

We know already how to tell a P-position from an N-position.

Also, we know that if we are facing a N-position and it's our move, the best we can do is make a random move and hope that our opponent makes a mistake further in the game. The reason we know this is that every move from a N-position is guaranteed to result in a P-position.

It turns out that if we are facing a P-position, we can efficiently compute a move, which will leave our opponent facing a N-position. If we manage to do it once, we can keep doing this until we win the game.

But how?

The trick is to compute the nim-sum of the current board, say `X`

, and the bitwise exclusive-or of each row size and `X`

. If the result is less than the row length, we record the index of that row as a "good index". It can be shown that our list of good indices will always be non-empty.

We can then pick any good row, say with `r`

elements and reduce its size to `X ^ r`

. This guarantees an N-position.

There's only one minor caveat: we prefer to operate with moves of the form `(row, elements)`

, which can be passed to the function `make_move`

rather than directly manipulating the rows. Instead of reducing the row length to `X ^ r`

, we can just return the difference of `X ^ r`

and the row size as the number of elements to remove from the row.

For example, if our board is `[5, 4, 3, 2, 1]`

, the nim-sum of the board is `1`

and the coressponding bitwise XOR of `1`

and each element of the board is `[4, 5, 2, 3, 0]`

. Doing an element-wise comparison we get $4 < 5$, $5 >= 4$, $2 < 3$, $3 >= 2,$ $0 < 1$. This means that only rows 1, 3 and 5 (with indices 0, 2, and 4) are "good", since $4 < 5$, $2 < 3$ and $0 < 1$ and any of the moves: `(1, 5 - 4) == (1, 1)`

, `(3, 3 - 2) == (3, 1)`

and `(5, 1 - 0) == (5, 1)`

would be optimal, where `(1, 1)`

for example means "remove one element from first row".

In [8]:

```
# Here's the user manual on the `random.randint` function.
# Please note: randint is left- right- inclusive!
import random
help(random.randint)
```

Task description in optimal_move.py

Task description in `ui.py`

Task description in working_game.py

If you've successfully accomplished parts A and B of the lab, congratulations, you're done!

If you'd like to fully understand the game of nim, we've put together a set of exercises & explanations for further self-study in `further_study.html`

. Please note that these exercises are no longer part of the lab, are not examinable, and require knowledge and techniques not covered in the course.

Made with ðŸ’™ by Adam Kurkiewicz