In Defiance of Titles

Just another WordPress.com weblog

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!

Advertisements

Written by jazzslider

March 12, 2009 at 6:26 am

5 Responses

Subscribe to comments with RSS.

  1. […] 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 […]

  2. I would really be interested in this. I stumbled on your post while thinking about developing a online spades app, ideally it would be one real player against 3 ‘bots with random strategies.

    FatherStorm

    April 10, 2009 at 9:58 am

  3. I’ll try to get some more of the code published soon; unfortunately I never quite got the really interesting strategies right…card selection strategies were a lot easier to work out than bidding strategies were.
    Eventually I got sidetracked by other projects, so this is still very much a work in progress…but until I can get the rest of it online, hopefully what’s on the blog so far can help you get started. Let me know if you come up with some interesting strategy implementations in the meantime!

    jazzslider

    April 10, 2009 at 1:18 pm

  4. the strategies shift pretty strongly on the bidding side based on the game rules. at home we don’t play sandbagging, so there’s no penalty for under-bidding. as such, I generally underbid my hand in an attempt to make my oponents over-bid. under those rules I only count top-cards in my hand, or a near-top card if I have 2 or less of a suit, or low-spades as top-cards in a suit if I have 1 or 0 cards in that suit. when playing sand-bags, I count guarantees plus 50% of maybes roughly, or if no aces and low-count of other fqace cards, I’m more prone to bid a nil.

    FatherStorm

    April 13, 2009 at 12:35 pm

  5. Did you say that there are online spades players that can enter a code to enable them to see their partner’s hands? If so, does that work anywhere you play online spades or only in specific sites?

    I play tournaments in leagues all the time and I’ve felt several times that my opps were cheating by either phone, IM, being in the same room with 2 computers,etc. So they could do it with that code too?

    Karla

    July 26, 2009 at 10:17 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: