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

[…] 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):

Python version. For fun, it simulates the slow typing of an old 300 baud modem.