Nim
January 8, 2010
We represent a game position as a list of the numbers of the stones in each pile; the game ends when the list is reduced to all zeros. A move is a pair with a pile in its car and a number of stones to remove in its cdr. The nim-sum is calculated by a simple recursion:
(define (nim-sum pos)
(if (null? pos) 0
(logxor (car pos) (nim-sum (cdr pos)))))
The heart of the program is the function choose-move, which takes a position and returns a move. If the nim-sum of the position is zero, in the first leg of the if, the computer is in a losing position, and choose-move simply removes one stone from the first non-empty pile. Otherwise, choose-move loops through the piles until it finds one where the exclusive-or of the number of stones with the nim-sum is less than the number of stones, and makes the appropriate move:
(define (choose-move pos)
(let ((x (nim-sum pos)))
(if (zero? x)
(let loop ((pos pos) (k 1))
(if (positive? (car pos)) (cons k 1)
(loop (cdr pos) (+ k 1))))
(let loop ((pos pos) (k 1))
(if (< (logxor (car pos) x) (car pos))
(cons k (- (car pos) (logxor (car pos) x)))
(loop (cdr pos) (+ k 1)))))))
Apply-move takes a position and a move and returns the resulting position:
(define (apply-move pos move)
(let* ((k (- (car move) 1))
(fs (take k pos))
(bs (drop k pos)))
(append fs (cons (- (car bs) (cdr move)) (cdr bs)))))
We need to be able to display positions and moves for the interactive game:
(define (display-pos pos)
(do ((pos pos (cdr pos)) (k 1 (+ k 1)))
((null? pos))
(display k)
(display ": ")
(display (car pos))
(newline)))
(define (display-move move)
(display "I remove ") (display (cdr move))
(if (= (cdr move) 1)
(display " stone from pile ")
(display " stones from pile "))
(display (car move)) (newline))
The computer calls choose-move to determine its next move; ask-move displays the current position, then asks the human player to enter his move:
(define (prompt message) (display message) (read))
(define (ask-move pos)
(display-pos pos)
(let* ((pile (prompt "Pile? ")) (stones (prompt "Stones? ")))
(cons pile stones)))
The play function processes human moves and computer moves; it recognizes the end of the game when the count of all the stones remaining in all the piles is zero:
(define (play pos who)
(cond ((zero? (apply + pos))
(display (if (eq? who 'human) "I win" "You win"))
(newline))
((eq? who 'human)
(play (apply-move pos (ask-move pos)) 'computer))
(else (let ((move (choose-move pos)))
(display-move move)
(play (apply-move pos move) 'human)))))
The game starts with the nim function, which takes the number of stones in each pile as its arguments:
(define (nim . xs)
(let* ((msg "Enter 1 to move first or 2 to move second: "))
(play xs (if (= (prompt msg) 1) 'human 'computer))))
Here’s a sample game, so you can see how everything fits together:
> (nim 3 4 5)
Enter 1 to move first or 2 to move second: 1
1: 3
2: 4
3: 5
Pile? 1
Stones? 2
I remove 1 stone from pile 1
1: 0
2: 4
3: 5
Pile? 3
Stones? 1
I remove 1 stone from pile 2
1: 0
2: 3
3: 4
Pile? 3
Stones? 1
I remove 1 stone from pile 2
1: 0
2: 2
3: 3
Pile? 3
Stones? 1
I remove 1 stone from pile 2
1: 0
2: 1
3: 2
Pile? 3
Stones? 1
I remove 1 stone from pile 2
1: 0
2: 0
3: 1
Pile? 3
Stones? 1
You win
We use take, drop, and logxor from the Standard Prelude. The code is collected at http://programmingpraxis.codepad.org/aNviDpKG.
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." )