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.
prints you've used for debugging, etc. Automatic tester doesn't like them!print_function and division, which should make this requirement very easy to satisfy.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):
It turns out that for any board position there are only two possibilities:
There are 2 important remarks about this statement:
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.
((5 ^ 4) ^ 3) ^ 2
5 ^ (4 ^ (3 ^ 2))
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".
# 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