CS1101S

Lecture 8: The Game of Nim

7 September 2012

Martin Henz

Overview

• Game of Nim
• Game state
• Game rules
• Computer strategy
• Representation of game state

Game of Nim

• Two players
• n piles with coins (in our case 2)
• Players taking turns, removing at least one coin from any pile
• The player who takes that last coin wins

Game state: Wishful Thinking!

function make_game_state(n, m) { ... }

function size_of_pile(game_state, p) { ... }

How to remove coins from pile?

• Implement remove_coins_from_pile(game_state, n, p)
• Make sure that only legal moves are made!

Poor Rabbit Rick!

Playing the game

• Implement play_with_turns(game_state, player)
• Player is 1 or 2
• Makes a move, and then calls itself recursively on the new state

Displaying the game state

function display_game_state(game_state) {
    alert("Pile 1: " + 
          size_of_pile(game_state, 1) + "\n" +
          "Pile 2: " + 
          size_of_pile(game_state, 2));
}

Game over

function game_over(game_state) {
    return total_size(game_state) === 0;
}

function total_size(game_state) {
    return size_of_pile(game_state, 1) + 
           size_of_pile(game_state, 2);
}

Announce Winner

function announce_winner(player) {
    if (player === "human") {
        alert("You lose. Try again.");
    } else {
        alert("You win. Congratulations.");
    }
}

Human Move

function human_move(game_state) {
    var pile_string = prompt("Which pile from?");
    var pile = parseInt(pile_string);
    var coins_string = prompt("How many?");
    var coins = parseInt(coins_string);
    return remove_coins_from_pile(game_state, 
                                  coins, pile);
}

Artificial Intelligence

function computer_move(game_state) {
    var pile = 
        (size_of_pile(game_state, 1) > 0) ? 1 : 2;
    alert("I take one coin from pile "+ pile);
    return remove_coins_from_pile(game_state, 1, 
                                  pile);
}

Representing the Game State: First attempt

function make_game_state(n, m) {
    return 10 * n + m;
}

Representing the Game State: Second attempt

function make_game_state(n, m) {
    return pair(n, m);
}
function size_of_pile(game_state, p) {
    if (p === 1) {
        return head(game_state);
    } else if (p === 2) {
        return tail(game_state);
    } else {
        return "error";
    }
}

Data Structure Design

• Specification: What functionality should the data structure provide?
• Implementation: How is it done?
• Specification is public, implementation private

Challenge: Implement Undo Function for Nim

• Specification: User can enter pile 0, which leads to undoing his last move
• Implementation idea: Use a stack data structure which provides the required operations
• Extend the game_state by a stack of moves
• Each move pushes a new entry on the stack, and each undo operation removes (pops) an entry.
• Practical details:
  • You find the implementation of the game in nim.zip.
  • Extract and open in Komodo Edit
  • Start Firefox and run the last commented lines of nim.js in the Web Console
  • You find an implementation of stack in the file the library lib/stack.js.

Summary

• A lot of wishful thinking
• Design principles: specification, implementation
• Abstraction allows for multiple implementations