In Defiance of Titles

Just another WordPress.com weblog

Archive for March 2009

Spades in PHP: Play-by-Play versus Play-at-Once

leave a comment »

Earlier this week I posted about my PHP spades project for automated testing of bidding and playing strategies. In that post I highlighted my use of the strategy design pattern to make it easy to test a variety of approaches to the game; however, I didn’t provide much structural detail. Lucky you, as it turns out, because the structure I was using at the time was far from ideal.

My overall idea for running the tests was to be able to use a very thin controller script, something along these lines:

$game = new Spades_Game();
for ($i=0;$i<3;$i++) {
  $game->registerPlayer(new Spades_Player(new Spades_Strategy_Something()));
}
$scores = $game->play();

This simple “play-at-once” approach is very easy to call, as it leaves every last bit of the game’s business logic to the model layer. Unfortunately, it doesn’t leave a lot of room for flexibility, particularly in two areas:

  1. Since the entire game happens in a single function call, it’s impossible for the controller layer to keep track of the game’s progress for output and/or logging purposes.
  2. It’s also impossible for the controller layer to allow user input and thereby facilitate the introduction of human players.

So, today I spent a good chunk of time re-architecting the game structure. In terms of tracking progress, I started to think in terms of atomicity: what’s the smallest sequential part of a game of spades? Well, let’s break it down. A game in its entirety consists of as many hands as necessary to get one team to 400 points without a tie. Each hand consists of each player bidding once, followed by as many tricks as necessary to lay down the entire deck. Each trick consists of every player laying down a single card in sequence. Tricks are won by the team who played the highest card (spades being higher than other suits), and hands are scored based on the number of tricks each player bid on winning.

The most atomic parts of all that are individual players’ bids and plays. So, if the controller layer was to be able to track the progress of the game, it would need to be able to check in after each of those events to see what happened. This led to the following “play-by-play” structure:

$game = new Spades_Game();
for ($i=0;$i<3;$i++) {
  $game->registerPlayer(new Spades_Player(new Spades_Strategy_Something()));
}
while ($nextPlayer = $game->getNextPlayer()) {
  if ($game->getCurrentPhase() == Spades_Hand::PHASE_BIDDING) {
    $game->acceptBid($nextPlayer->placeBid(), $nextPlayer);
  } else if ($game->getCurrentPhase() == Spades_Hand::PHASE_PLAYING) {
    $game->acceptPlay($nextPlayer->playCard(), $nextPlayer);
  }
}
$scores = $game->getScores();

The nice thing about this is that, although there’s quite a bit going on behind the scenes, the controller layer really only needs to be aware of the Spades_Game, Spades_Player, and Spades_Strategy_X classes. As long as the game object returns a player, the controller layer knows that there’s more game to be played.

So what’s going on internally? Well, Spades_Game is basically a facade managing a sequence of Spades_Hand objects, which in turn manage a sequence of Spades_Trick objects. Take a look:

class Spades_Game
{
  // ...
  public function getNextPlayer()
  {
    $hand = $this->getCurrentHand();
    if (null === $hand) {
      return null;
    }

    $player = $hand->getNextPlayer();
    if (null === $player) {
      // this hand is over...score it, register it, and
      // check to see if the game has been won
      $this->_score();
      $this->_handsPlayed[] = $hand;
      if ($this->_isWon()) {
        return null;
      }

      // hasn't been won yet, so we need to start up
      // a fresh hand...
      $this->_incrementDealer();
      $this->_currentHand = new Spades_Hand($this);
      $player = $this->_currentHand->getNextPlayer();
    }
    return $player;
  }
  // ...
}

Notice that, at this point, there isn’t any logic regarding the phase we’re in (bidding or playing); since the two phases each occur once per hand, it makes more sense to manage them within the Spades_Hand class. Each phase is handled by separate logic, so Spades_Hand::getNextPlayer() makes use of a couple of protected methods to keep things distinct:

class Spades_Hand
{  
  // ...
  public function getNextPlayer()
  {
    switch ($this->getCurrentPhase()) {
      case Spades_Hand::PHASE_BIDDING :
        $player = $this->_getNextBidder();
        break;
      case Spades_Hand::PHASE_PLAYING :
      default :
        $player = $this->_getNextPlayer();
        break;
    }
    return $player;
  }

  protected function _getNextBidder()
  {
    if (count($this->getPlayerBids()) <= 0) {
      // nobody has bid yet, so this is the beginning of the hand;
      // deal, and then the player after the dealer is the first bidder
      $this->_cardsDealt = $this->getDeck()->deal($this->getPlayers(), $this->getDealer());
      $this->_currentTrick = new Spades_Trick($this->getGame());
      $position = $this->getDealer() + 1;
    } else {
      $lastbid = end($this->_bids);
      $lastpos = key($this->_bids);
      $position = $lastpos + 1;
    }
    if ($position > count($this->getPlayers()) - 1) {
      $position = 0;
    }
    $players = $this->getPlayers();
    $player = $players[$position];
    return $player;
  }

  protected function _getNextPlayer()
  {
    $trick = $this->getCurrentTrick();
    if (null === $trick) {
      return null;
    }
    $player = $trick->getNextPlayer();
    if (null === $player) {
      // the trick is over...score it, register it, and
      // check to see if the hand is complete
      $this->_score();
      $this->_tricksPlayed[] = $trick;
      if ($this->_isFinished()) {
        return null;
      }

      // not done yet, start a fresh trick
      $this->_currentTrick = new Spades_Trick($this->getGame());
      $player = $this->_currentTrick->getNextPlayer();
    }
    return $player;
  }
  // ...
}

Notice that the _getNextPlayer() half of the procedure is extremely similar to Spades_Game::getNextPlayer(); we’re still passing the buck along the chain to a smaller unit of play…the Spades_Trick instance.

class Spades_Trick
{
  // ...
  public function getNextPlayer()
  {
    if (count($this->_plays) == count($this->getPlayers())) {
      // everybody's played, so we're done...determine the winner
      // and get on out of here.
      $this->_determineWinner();
      return null;
    } 
    if (null === $this->_currentPlayer) {
      // first play...determine the lead player
      $this->_currentPlayer = $this->getLeadPlayer();
    } else {
      // cycle through to next player
      $this->_currentPlayer = $this->getPlayerAfter($this->_currentPlayer);
    }
    return $this->_currentPlayer;
  } 
  // ...
}

All these layers taken together make it possible for the controller layer to always have access to the next player in sequence, without having to know much of anything about that sequence.

One nice side bonus of this structure is that it would be dead simple for the controller layer to identify certain players as user-controlled, injecting their input into the system in the $game->acceptBid() and $game->acceptPlay() methods.

The next step in all of this, I suppose, will be to develop a simple web interface for viewing the results, and possibly trying to beat all these wonderful computer players.

Written by jazzslider

March 14, 2009 at 8:43 pm

Spades and the Strategy Pattern

with 5 comments

So lately my wife and I have been playing quite a bit of spades with some good friends of ours; if you’ve never played, it’s quite fun, but you don’t want to be on my team ­čÖé

The thing is, it strikes me as the kind of game a well-informed computer would be great at; that is, if one could remember everything that’s been played in a given hand and, from that, calculate the probability of any of one’s cards being beaten in a given trick, one could win the game far more easily. ┬áBut I have my doubts about this, so as any good developer would, I decided to test it programmatically.

Here’s the project (and I deliberately didn’t check to see if anyone’s done this before): write a command-line PHP script that runs any number of automated spades games, involving a variety of players utilizing different play algorithms. ┬áSince the algorithms are what we’re most interested in, I decided to use the strategy pattern: each player is an instance of the same basic Spades_Player class, but each has its own instance of one of several Spades_Strategy_Interface implementations that controls how it bids and how it chooses the card to play. ┬áHere are the interfaces:

interface Spades_Player_Interface
{
  public function __construct(Spades_Strategy_Interface $strategy, $name = null);

  // player should have an identity
  public function getName();

  // player is part of a particular Spades_Game, and
  // is seated in a particular position from 0 to 3
  public function getGame();
  public function setGame(Spades_Game $game);
  public function getPosition();
  public function setPosition($position);

  // player has several cards
  public function getCards();
  public function receiveCard(Spades_Card $card);

  // actual playing methods
  public function placeBid();
  public function playCard(Spades_Trick $trick);

  // player should also be able to respond to certain events
  public function preHand(Spades_Hand $hand);
  public function preTrick(Spades_Trick $trick);
  public function postPlay(Spades_Trick $trick, Spades_Play $play);
  public function postTrick(Spades_Trick $trick);
  public function postHand(Spades_Hand $hand);
}

Now on to the strategy pattern. You’ll notice a lot of the same methods here; as I understand it, that’s the idea behind this particular pattern. It implements a lot of its owner’s methods so that different instances of the same owner class can have very different behaviors. Here’s the code I used:

interface Spades_Strategy_Interface
{
  // strategy should know its player
  public function getPlayer();
  public function setPlayer(Spades_Player_Interface $player);

  // convenience methods for getting state information from the player
  public function getGame();
  public function getPosition();
  public function getCards();

  // player hook implementations
  public function preHand(Spades_Hand $hand);
  public function preTrick(Spades_Trick $trick);
  public function postPlay(Spades_Trick $trick, Spades_Play $play);
  public function postTrick(Spades_Trick $trick);
  public function postHand(Spades_Hand $hand);

  public function placeBid();
  public function playCard(Spades_Trick $trick);
}

And, just so you see how it works in practice, here’s a sample method from my actual Spades_Player implementation:

class Spades_Player implements Spades_Player_Interface
{
  // ...
  public function playCard(Spades_Trick $trick)
  {
    $toPlay = $this->_strategy->playCard($trick);
    $trick->receivePlay(new Spades_Play($toPlay, $this));
    return $toPlay;
  }
  // ...
}

So there it is, nice and simple. Testing a new strategy algorithm is as simple as defining a new PHP class.

It’s also probably a good idea at this point to define some sort of reference strategy to test against…something that any intelligent spades player ought to be able to beat. How about randomizing it? (Note that I’ve implemented a lot of the hook methods in a separate abstract class, so there’s a lot less to write here than the interface suggests.)

class Spades_Strategy_Random extends Spades_Strategy_Abstract
{
  public function placeBid()
  {
    return mt_rand(0, 4);
  }

  public function playCard(Spades_Trick $trick)
  {
    $playable = $trick->getPlayableCards($this->getCards());
    return $playable[array_rand($playable)];
  }
}

Hmm, that kind of looks like the strategy I use.

Anyway, there are quite a few places we could go from here; I’ve already implemented most of the classes you see mentioned in the code above (Spades_Game, Spades_Hand, Spades_Trick, Spades_Play, and Spades_Card), but the real fun is in writing new strategies. Some ideas I’ve had:

  • Probability-based: the player remembers which cards have been played and figures out how likely it is any of its playable cards can be beaten by any of its opponents. (More on this later; I’m not quite sure about the math here.)
  • Evolutionary: the player starts out playing at random, but always remembers whether a given card ends up beating a given trick state. For instance, if it plays the Ace of Clubs on top of the Two of Clubs and then ends up winning the trick, it’ll be more likely to play the Ace of Clubs against the Two of Clubs in later hands.
  • Cheater: you’ll notice that the Spades_Player::getCards() method is public, and astute readers may have already guessed that Spades_Game implements a public getPlayers() method; as a result, unscrupulous players would technically be able to take a peak at their opponents’ hands and play accordingly.

That’s all I’ve got for now; if anyone is interested, I may post the full code later once it’s finished. Thanks for reading!

Written by jazzslider

March 12, 2009 at 6:26 am