Programming Praxis

This exercise marks the one-hundredth exercise since the beginning of Programming Praxis. Thanks to all my readers, who give me the energy to continue writing these exercises. To celebrate, we ought to have a party, and parties need games, so in this exercise we implement a program to play the game of nim.

Nim is played by placing stones in piles; there may be any number of piles, and any number of stones in each pile. Two players alternate turns in which each player removes as many stones as desired from any pile desired; all the stones removed must come from the same pile, it is not permitted to take stones from multiple piles. The player who removes the last stone from the last non-empty pile is the winner. (In some variants of the game the player who removes the last stone is the loser, but we will not consider those variants.)

The winning strategy was devised by Charles Bouton in 1901 and revolves around a mathematical calculation called the nim-sum, which is the exclusive-or of the number of stones in each pile; for instance, with piles of 25, 32, 19, 4, and 17 stones, and representing the exclusive-or operation as ⊕, the nim-sum is calculated as 25 ⊕ 32 ⊕ 19 ⊕ 4 ⊕ 17 = 63. If a player can remove stones from a pile in such a way that he reduces the nim-sum to zero, he can always force a win. Such a move can be computed by exclusive-or’ing the nim-sum with the number of stones in each pile in turn, choosing a pile for which the result of that exclusive-or is less than the number of stones in the pile, and removing from that pile sufficient stones to reduce the pile to the result of that exclusive-or; for instance, removing one stone from the second pile in the example above reduces the nim-sum of the piles to zero, forcing a win. However, if the nim-sum is already zero at the beginning of a player’s turn, he will lose against proper play, so any move may be chosen at random.

Your task is to write a program that plays nim against a human player. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2