## 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.

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

```