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

    My Haskell solution (see for a version with comments):

    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 )
            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 ]:
            tty( "\nYour input is not valid. Please reenter." )
        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 )
            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:
            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." )

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: