CS 151 - Day 19

Cay S. Horstmann

Lab

• Work with a buddy
• One of you codes, the other types up the answers.
• One of you submits the code in the lab19 subdirectory of your personal repo, the other submits a file report.txt in the lab19 subdirectory of your personal repo.
• Put the name of the coding buddy into the report

A Simple Game

• 

  Pile of pebbles. Each player can take either one or two pebbles. A player wins if only one pebble is left after their turn.

• You are invited to take part in this game. You get the first turn. There are sixteen pebbles. Should you accept?
• This is a completely general problem. There are all sorts of games like that. In Java, we'd say:

  class AbstractGame<Position> {
    public abstract boolean win(Position pos);
    public abstract List<Position> move(Position pos);
    public Position winningMove(Position pos) { ... }
  }
  

  It turns out you can write a winningMove method by calling the win and move methods just so.
• Let's do this in JavaScript. We have no abstract methods, but this is what we can do:

  class AbstractGame {
    winningMove(pos) {
      for (const n of this.move(pos)) {  
        if (this.losingPosition(n)) return n // Can force the opponent to lose
      }
      return undefined // Couldn't find a winning move
    }
    
    losingPosition(pos) {
      if (this.win(pos)) return true // Just lost
      for (const n of this.move(pos)) { 
        if (this.winningMove(n) === undefined) return false // Not losing here
      }
      return true // Lose no matter what
    }  
  }
  

• There are no abstract method declarations in JavaScript, but how can the reader of the winningMove and losingPosition methods figure out what they are?

All Winning Positions

• Now let's define our game:

  class PebbleGame extends AbstractGame {
    move(p) {
      if (p > 2) return [p - 2, p - 1]
      else if (p === 2) return [1]
      else return []
    }
    win(p) {
      return p === 1
    }
  }
  

• What are winning positions?

  const myGame = new PebbleGame()
  
  for (let p = 1; p <= 20; p++) {
    console.log(p + ' -> ' + myGame.winningMove(p))
  }
  

  Put it all in a file lab19/nim.js and run node nim.js in the cs151/lab19 directory.
• Should you play with 16 pebbles?
• Now change 20 to 100 in the loop above. What happens?
• If you took CS146, you know the reason—overlapping recursive calls. And the remedy—memoization.
• We'll leave that as an exercise for the reader.
• A better known game is the game of Nim, where each player must take at least one pebble but at most half of the pebbles:

  class NimGame extends AbstractGame {
    move(p) {
      const result = []
      for (let i = p - 1; 2 * i >= p; i--)
        result.push(i)
      return result
    }
    win(p) {
      return p === 1
    }
  }
  
  

  Should you play with 16 pebbles? When should you not play?

Which Pattern?

• Enough of pebble games. Which design pattern was at work here?
• What made it harder to spot the pattern in JavaScript than in Java?
• The hard object crowd frown on extends. Let's say you are a believer. Which other design pattern could you use to analyze the positions of a game?
• Ok, go for it. Implement a GameAnalyzer with methods winningMove, losingPosition. It doesn't extend anything, and nothing extends it. In the constructor, provide an object with move and win methods.
• Is that really the desired design pattern? Fill out the pattern table.
• Extra time? Add memoization to the game analyzer. Simply keep a hash table for previously computed winningMove and losingPosition results. How do you get a hash table? Just use a JavaScript object!
• Now have a final look at your GameAnalyzer. In Java, you could have written the same, but it would have been much harder to describe the types. In Nim, a position is an integer, but in TicTacToe, it's a 3x3 array of strings. So, you'd have to use generic types:

  public class GameAnalyzer<PositionType> {
     public GameAnalyzer(Game<PositionType> game) { ... }
       // Or maybe <? extends PositionType>? Or super???
     public List<PositionType> winningMove(PositionType pos) { ... }
     ...
  }
  

  It's more robust, of course, but also more work.