## Nim

### January 8, 2010

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

### 3 Responses to “Nim”

1. […] Praxis – Nim By Remco Niemeijer In today’s Programming Praxis we have to program the game Nim. Let’s get […]

2. Remco Niemeijer said

```import Data.Bits
import System.Random
import Text.Printf

valid :: (Int, Int) -> [Int] -> Bool
valid (p, t) ps = and [p >= 0, p < length ps, t > 0, t <= ps !! p]

showMove :: (Int, Int) -> IO ()
showMove (p, t) = printf "I remove %d stone%s from pile %d\n" t
(if t > 1 then "s" else "") (p + 1)

cpu :: [Int] -> IO (Int, Int)
cpu ps = do p <- randomRIO (0, length ps - 1)
t <- randomRIO (1, ps !! p)
let n = foldl xor 0 ps
let r = if n == 0 then (p, t) else (length a, b - xor b n)
where (a,b:_) = break (\x -> xor x n < x) ps
if valid r ps then showMove r >> return r else cpu ps

prompt :: Read a => String -> IO a
prompt s = putStr (s ++ " ") >> fmap read getLine

human :: [Int] -> IO (Int, Int)
human ps = do p <- fmap pred \$ prompt "Pile?"
t <- prompt "Stones?"
if valid (p, t) ps then return (p, t) else human ps

display :: [Int] -> String
display = unlines . zipWith (printf "%d: %d") [1 :: Int ..]

makeMove :: (Int, Int) -> [Int] -> [Int]
makeMove (p, t) = (\(a,b:c) -> a ++ b - t:c) . splitAt p

turn :: [([Int] -> IO (Int, Int), [Char])] -> [Int] -> IO ()
turn ~((f, w):ms) b = if all (== 0) b then putStrLn \$ w ++ " win"
else do putStr \$ display b
turn ms . flip makeMove b =<< f b

nim :: [Int] -> IO ()
nim ps = do f <- prompt "Enter 1 to move first or 2 to move second:"
turn (drop f \$ cycle [(cpu, "You"), (human, "I")]) ps
```
3. Mike said

Python version. For fun, it simulates the slow typing of an old 300 baud modem.

```from operator import xor
from random import choice, randint
from sys import stdout
from time import sleep

def computer( piles ):
'''Determine computer move.'''

nimsum = reduce( xor, piles )

if nimsum:
moves = [ ( pile, stones - ( nimsum ^ stones ) )
for pile, stones in enumerate( piles )
if stones^nimsum < stones ]

pile, stones = choice( moves )

else:
pile = randint( 0, len( piles ) - 1 )
stones = randint( 1, piles[ pile ] )

sleep( 0.7 )
tty( "\nI take {0} stone{1} from pile {2}.\n".format(
stones, ("s","")[stones==1], pile + 1 ) )

return pile, stones

def human( piles ):
'''Get and validate input from the human player.'''

while True:
tty( "\nHow many stones do you want to remove? " )
stones = int( raw_input().strip() )

tty( "From which pile? " )
pile   = int( raw_input().strip() ) - 1

if  0 <= pile < len(piles) and 1 <= stones <= piles[ pile ]:
break

return pile, stones

def show( piles ):
'''Display the piles of stones.'''

columnformat = "{0:4}".format
lineformat = "\n{0:6}: {1}".format

cols = map( columnformat, range( 1, len(piles) + 1 ) )
tty( lineformat( "pile", ''.join( cols ) ) )

cols = map( columnformat, piles )
tty( lineformat( "stones", ''.join( cols ) ) )

tty( "\n" )

def tty( s, baudrate=300 ):
'''simulate slow console output of old TTY.'''

pacing = 10.0 / baudrate
for c in s:
stdout.write( c )
stdout.flush()
sleep( pacing )

def nim():
'''Play nim.'''

piles = [ randint( 3, 11 ) for n in range( randint( 3, 11 ) ) ]
show( piles )

tty("\n\nWould you like to go first? " )
ans = raw_input().strip().upper()
player = human if ans.startswith( 'Y' ) else computer

while True:
pile, stones = player( piles )
piles[ pile ] -= stones

if sum( piles ) == 0:
break

player = computer if player == human else human
show( piles )

tty( "\nThere are no stones remaining, " )
tty( "I win!\n" if player==computer else "You win!\n" )
sleep( 1 )
tty( "\nNow, how about a game of Global Thermonuclear War?" )
sleep( 1 )
tty( "...Just kidding!" )
sleep( 0.5 )
tty( "\n\nBye." )

```