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.
Programming Praxis 
[…] Praxis – Nim By Remco Niemeijer In today’s Programming Praxis we have to program the game Nim. Let’s get […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/01/08/programming-praxis-nim/ 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")]) psPython 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 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 ) 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." )