Programming Assignment 1a - Solitaire, Part 2

The program description straightforwardly leads to an initial design:

main(String args[]) 
  final int 
    gameCount = processArguments(args)
    gamesWon = playGames(gameCount)
  System.out.println("Won: " + gamesWon + " lost: " + gameCount - gamesWon)

There's only one required command-line argument: the number of games to play. There are not interesting design question for command-line arguments, although it might be useful to consider what might happen if there were more than one command-line argument.

The game-playing requirement is also straightforward:

playGames(int gameCount)

  int won = 0

  while --gameCount > 0
    if playGame()
      won++

  return won

The design of playGame() is more interesting: how do you play a game of Eagle's Wing? However, it turns out that the crazy-monkey style of play leads to a simple design. Crazy-monkey play involves making any move possible without considering whether the move is good or bad. Keep this up until there are no more moves and then see if the game's a win or a loss. Crazy-monkey play is simple to design because there's no strategy.

Crazy-monkey play needs three things:

1. A way to generate moves.

2. A way to recognize when there are no more moves.

3. A way to recognize a winning game.

A bit of thought shows that generating moves consists of creating pairs of card piles; each pair represents a move between the first pile to the second (or vice versa). Eagle's Wing makes this simple because there's only one move available between any two card piles, assuming any move is possible at all. The Eagle's Wing API makes the card piles available as an enumeration; generating pairs is a small matter of two for loops over the card-pile enumerations. Fortunately, the static method CardPiles.pairIterate() generates all possible card-pile pairs, calling a method with each pair as a parameter.

Recognizing when a game has no more moves could be tricky, but the Eagle's Wing API provides the predicate movesPossible() to do the job. Similarly, recognizing when a game is won is a bit easier, but it doesn't matter because the API provides gameWon().

With these three API features the game player falls into place:

boolean playGame()

  EaglesWing game = EaglesWing.newGame()

  CardPiles.PairFun pairFun = new CardPiles.PairFun() {
    int f(CardPiles fromPile, CardPiles toPile) {
      game.move(fromPile, toPile)
      return 0
      }
    }

  do CardPiles.pairIterate(pairFun)
  while game.movesPossible()

  return game.gameWon()

And that's it for the design of a program to play Eagle's Wing. It's a simple design, but a surprisingly effective one capable of winning 46% of the games it plays:

$ java -ea player.Main -s 10 -p random 10000
Won:  4641 lost: 5359

$

A Biased-Monkey Design

One obvious problem with crazy-monkey play is it doesn't distinguish among moves; it just makes every possible move blindly as it comes up. Given that the objective of Eagle's Wing is to move all cards to the foundation piles, it might make sense to bias play so that moves to foundation piles occur before other moves are made.

int biasedMonkeyPlay()

  EaglesWing game = EaglesWing.newGame()

  do
    foundationMoves(game)
    nonfoundationMoves(game)
  while game.movesPossible()

  return game.gameWon()

foundationMoves() is implemented with a simple filter on the move pairs:

void foundationMoves(EaglesWing game)

  CardPiles.pairIterate(new CardPiles.PairFun() {
    int f(CardPiles fromPile, CardPiles toPile) {
      if (pileType(toPile) == foundationPile)
        game.move(fromPile, toPile)
      return 0
      }
    })

Likewise for nonfoundationMoves():

void nonfoundationMoves(EaglesWing game)

  CardPiles.pairIterate(new CardPiles.PairFun() {
    int f(CardPiles fromPile, CardPiles toPile) {
      if (pileType(toPile) != foundationPile)
        game.move(fromPile, toPile)
      return 0
      }
    })

nonfoundationMoves() only needs to look at the to-pile types because there are no legal moves using a foundation pile as the from pile. Observant readers will have noticed that nonfoundationMoves() and foundationMoves() are almost identical, differing only in the pile-type test. Good software design demands that the common parts of both methods be extracted to a single method parametrized by the difference; See the appendix for more details.

Unfortunately, biased-monkey play isn't much better than crazy-monkey play:

$ java -ea player.Main -s 10 -p biased 10000
Won:  5311 lost: 4689

$

Biased play improves the win percentage to around 53% from 46%.

Stronger Bias

The solution to this problem is to increase the bias for foundation moves by repeatedly checking for foundation moves until there aren't any more:

void strongFoundationMoves(final EaglesWing game)

  class StrongFoundationFun
  extends CardPiles.PileFun {

    boolean checkAgain;

    public int f(CardPiles fromPile, CardPiles toPile) {
      if pileType(toPile) == foundationPile
        if game.move(fromPile, toPile) == EaglesWingStatus.MOVE_SUCCESSFUL
          checkAgain = true
      }
    }

  StrongFoundationFun strongFoundationFun = new StrongFoundationFun();

  do
    strongFoundationFun.checkAgain = false
    CardPiles.pairIterate(strongFoundationFun)
  while strongFoundationFun.checkAgain

Similarly, the nonfoundationMoves() bias against foundation moves may be too strong: moves from the trunk, stock, or waste piles could uncover cards that could be moved to a foundation pile, but may not be because they're moved elsewhere later in the call to nonfoundationMoves(). The weak foundation bias can be strengthened by stopping non-foundation moves after the first successful one; foundationMoves() then gets a crack at any new cards uncovered.

void weakNonfoundationMoves(EaglesWing game)

  CardPiles.pairIterate(new CardPiles.PairFun() {
    int f(CardPiles fromPile, CardPiles toPile) {
      if pileType(toPile) != foundationPile &&
        game.move(fromPile, toPile) == EaglesWingStatus.MOVE_SUCCESSFUL
        return 2
      return 0
      }
    })

Together they allow strong-biased play:

int strongBiasedPlay()

  EaglesWing game = EaglesWing.newGame()

  do
    strongFoundationMoves(game)
    weakNonfoundationMoves(game)
  while game.movesPossible()

  return game.gameWon()

Strong-biased play is a bit better, improving to 58% from 53%:

$ java -ea player.Main -s 10 -p strongBiased 10000
Won:  5863 lost: 4137

$

However, it seems we're past the knee of the cost-benefit curve and that any further sigificant improvements will require significant work.

Appendix: The Unbearable Heaviness of Java

void foundationMoves(EaglesWing game)

  CardPiles.pairIterate(new CardPiles.PairFun() {
    int f(CardPiles fromPile, CardPiles toPile) {
      if pileType(toPile) == foundationPile
        game.move(fromPile, toPile)
      return 0
      }
    })

void nonfoundationMoves(EaglesWing game)

  CardPiles.pairIterate(new CardPiles.PairFun() {
    int f(CardPiles fromPile, CardPiles toPile) {
      if (pileType(toPile) != foundationPile)
        game.move(fromPile, toPile)
      return 0
      }
    })

are almost identical, differing only in the pile-type test. Good design demands that the common parts of these methods be extracted to a single method parametrized by the difference. Lisp-like languages, in this case Scheme, are good at writing software using procedural abstraction:

(define (biased-moves game acceptable-move)

  (CardPiles.pairIterate
     (lambda (from-pile to-pile)
       (if (acceptable-move from-pile to-pile)
         (game.move from-pile to-pile)))))

The lambda form creates an anonymous function, which is being passed into the pair iterator. The anonymous function calls another function, acceptable-move, to determine if the given pair represents an acceptable move. The function acceptable-move is passed in as a parameter.

Now foundationMoves() and nonfoundationMoves() can be defined simply in terms of biased-moves:

(define (foundation-moves game)
  (biased-moves game 
     (lambda (from-pile to-pile) (eq? (pile-type to-pile) foundation-pile))))

(define (foundation-moves game)
  (biased-moves game 
     (lambda (from-pile to-pile) (not (eq? (pile-type to-pile) foundation-pile))))

The second argument in each call to biased-moves is an anonymous function that determines if a given pair of card piles is an acceptable move. In the first case the move is acceptable of the to-pile is in the foundation; in the second case the move is acceptable if the to-pile is not in the foundation (this could be abstracted further, but the given code is straightforward enough as it is).

The Java implementation is similar, but requires more machinery. biased-moves can be defined as a child of CardPiles.PairFun:

class BiasedFun
implements CardPiles.PairFun {

  private final MoveBias moveBias;
  private final EaglesWing game;

  BiasedFun(EaglesWing g, MoveBias mb) {
    game = g;
    moveBoas = mb;
    }

  public int f(CardPiles fromPile, CardPiles toPile) {
    if (moveBias(fromPile, toPile)
      game.move(fromPile, toPile);
    return 0;
    }

Making BiasedFun a child of CardPiles.PairFun allows BiasedFun instances to be treated as CardPiles.PairFun instances via subtype polymorphism.

MoveBias is an interface defining the bias function to apply to a pile pair:

interface MoveBias {
  public boolean moveBias(CardPile fromPile, CardPile toPile);
  }

Now foundationMoves() and nonfoundationMoves() can be defined in terms of biased-moves:

void foundationMoves(EaglesWing game)
 
  final MoveBias foundationBias = new MoveBias() {
    public boolean 
    moveBias(CardPile fromPile, CardPile toPile) {
      return pileType(toPile) == foundationPile
      }
    }

  CardPairs.pairIterate(new BiasedFun(game, foundationBias));


void nonfoundationMoves(EaglesWing game)
 
  CardPairs.pairIterate(new BiasedFun(game, 
    new MoveBias() {
      public boolean 
      moveBias(CardPile fromPile, CardPile toPile) {
	return pileType(toPile) != foundationPile
	}
      })

In foundationMoves() the bias-function instance was stored in a local variable (foundationBias) that was passed on as a parameter to BiasedFun(); in nonfoundationMoves() the bias-function instance was created directly in the BiasedFun() argument list.

To be completely fair, it should be pointed out that Java is providing type-safety while the Scheme implementation isn't. Scheme allows any values to be passed into biased-fun and CardPiles.pairIterate as function values and it isn't until the values are used (that is, it isn't until run-time) that the error is discovered. The Java implementation, on the other hand, is strongly (in this case) and statically typed: any attempt to use anything other than MoveBias and CardPiles.PairMove values is detected at compile time. The real question is: Does Java have to make strong and static type safety so conceptually and mechanically expensive?