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.

About these ads

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 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")]) 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
            
            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." )
    
    

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: