Implementing Nim in R

Introduction

The game Nim is a classic of computer science. In this post we will implement an interactive version of Nim in R using a functional style of programming. The implementation will allow the user to play a game against a human opponent in an R console.

In a second post, we will use a bit of object-oriented programming (using R’s S3 system) to implement a quirky algebra called Nimbers, and show how these can be used to “solve” Nim. With this solution, we can then generalize the game by implementing a computer-opponent playing a perfect strategy.

In a (potential) final post, we will wrap this all up as a Shiny app, to do away with the need for an R installation to play the game.

A caveat before we start; Nim is, frankly, not a terribly fun game to play. So the reader shouldn’t be too concerned with the game itself, but rather focus on the functional programming patterns used to implement it.

How to play Nim

A game of Nim consists of two players and a certain number of heaps of, say, pebbles. The players take turns choosing a heap and removing one or more pebbles from that heap. The game ends when a player is unable to remove any pebbles (i.e. starts a turn with an empty board). That player has lost the game.

Example: A game starts with three heaps, with 3, 2, and 1 pebble(s) respectively. I start by removing 3 pebbles from the first heap. You then remove one pebble from the second heap. This leaves one pebble in each of heaps two and three. I remove one pebble from heap 3 and you remove the last one from heap 2. I’m now faced with an empty board, and have thus lost the game.

Implementation in R

We start by loading the purrr package (for the walk2 and case functions).

library(purrr)

We will represent a game board as a simple numeric vector:

initial_board <- 3:1
initial_board

## [1] 3 2 1

We also want a more appealing way to display a board:

disp_row   <- function(row, num) {
  cat(row, ":", rep("*", num), "\n")
}

disp_board <- function(board) {
  walk2(seq_along(board), board, disp_row)
}

disp_board(initial_board)

## 1 : * * * 
## 2 : * * 
## 3 : *

Players will be represented simply as the integers 1 and 2, and we can create a utility function for switching between them:

next_player <- function(player) {
  if(player == 1) 2 else 1
}

next_player(1)

## [1] 2

next_player(2)

## [1] 1

The game ends when all heaps are zero:

finished <- function(board) {
  all(board == 0)
}

finished(initial_board)

## [1] FALSE

finished(c(0, 0, 0))

## [1] TRUE

To make a move we simply take as input a board, a row, and a number (of pebbles to remove), subtract the number from the existing number of pebbles in that row and return a new board:

update <- function(board, row, num) {
  board[row] <- board[row] - num
  board
}

update(initial_board, 1, 3)

## [1] 0 2 1

We also need to make sure a player doesn’t try to make an invalid move (i.e. remove no pebbles or more pebbles than are available). Here we also start referring to heaps as rows, since it feels a bit more natural:

valid_move <- function(board, row, num) {
  num > 0 && board[row] >= num
}

valid_move(initial_board, 2, 3)

## [1] FALSE

valid_move(initial_board, 2, 2)

## [1] TRUE

Finally, we need a way to receive input from the player:

get_move <- function() {
  row <- as.integer(readline("Choose a row: "))
  num <- as.integer(readline("Number of stars to remove: "))
  c("row" = row, "num" = num)
}

We’re now ready to combine together all of these functions into a single function:

nim <- function(board = 5:1, player = 1) {
  if(finished(board)) {
    cat("Game over. Player", next_player(player), "wins!")
    return(invisible())
  }

  disp_board(board)
  cat("Player", player, "\n")
  play <- get_move()
  row <- play["row"]
  num <- play["num"]

  if(!valid_move(board, row, num)) {
    cat("Not a valid move. Try again.\n")
    nim(board, player)
  } else nim(update(board, row, num), next_player(player))
}

So nim takes a board and a player as input. It then starts by checking if the game is finished; if it is, then the other player has won and the game ends. Otherwise, we display the board and the active player and prompt for a move. If the move is invalid we show a warning and recursively restart the turn. If the move is valid, however, we also recurse, but this time with an updated board and new player.

(Recursion is not very natural to R, and often not a good idea. We could easily avoid recursion by wrapping the game in a while-loop instead, but it wouldn’t be quite as elegant. Besides, we would have to play a very large game before becoming concerned with blowing the stack through too many recursive calls.)

Here’s what a game looks like:

In summary, here is the entire game, in less than 30 lines of code:

next_player <- function(player) if(player == 1) 2 else 1
valid_move  <- function(board, row, num) num > 0 && board[row] >= num
finished    <- function(board) all(board == 0)
update      <- function(board, row, num) `[<-`(board, row, board[row] - num)
disp_row    <- function(row, num) cat(row, ":", rep("*", num), "\n")
disp_board  <- function(board) walk2(seq_along(board), board, disp_row)
get_move    <- function() {
  row <- as.integer(readline("Choose a row: "))
  num <- as.integer(readline("Number of stars to remove: "))
  c("row" = row, "num" = num)
}

nim <- function(board = 5:1, player = 1) {
  if(finished(board)) {
    cat("Game over. Player", next_player(player), "wins!")
    return(invisible())
  }

  disp_board(board)
  cat("Player", player, "\n")
  play <- get_move()
  row <- play["row"]
  num <- play["num"]

  if(!valid_move(board, row, num)) {
    cat("Not a valid move. Try again.\n")
    nim(board, player)
  } else nim(update(board, row, num), next_player(player))
}