Only old ladies play bridge

Given that, it’s inevitable what this program had to be called:

Old Lady 0.1.0 screenshot

Surprisingly, nobody seems to have written an open-source contract bridge program that wasn’t just a client for network play. That might mean that Old Lady is the first. Technically, at least. Currently, the rules of the game are implemented, but all the computer players really manage to do is play by the rules. Tactically and strategically, they’re dumb as rocks.

(Specifically, dumb as basalt. For reference, in no particular order, granite takes out subprime loans, obsidian invests in subprime loans, dolomite invests in the weekly lottery, flint uses 1337 unironically, gypsum believes the moon landing was a hoax, limestone believes the moon itself is a hoax, and shale thinks Mega Man 3 is better than Mega Man 2.)

(Also, perhaps it’s not so surprising it hasn’t been done, given how your stereotypical open-source programmers are young males and your stereotypical bridge players are old ladies. There’s not much overlap between those demographics.)

But I digress. While it might not immediately seem that having braindead opponents is such a bad thing, especially if you’re just learning how to play, bridge is a team game, and having a braindead partner is something else entirely. Currently, during the auction, the computer players always pass, and during the trick-taking phase, the computers will always play the lowest-valued card that will take the trick (if it isn’t currently being won by the partner), or throw away the lowest-valued card otherwise. It’s legal, but even a novice could defeat such players without much difficulty.

If you play chess, it’s a bit as though your opponent captured whenever possible, and otherwise moved the piece closest to square a1 towards the center of the board. You’re not going to win many games that way.

So, why bother with bridge? It’s actually an interesting game if you’re at all interested in communications. During the auction, your goal is to establish a contract: how many tricks you think your partnership will be able to take, and what suit (if any) should be trump. Of course, you’re not able to look at your partner’s hand, so you can’t tell what your best contract is just by looking at your own cards. However, the only communication with your partner you are allowed to make is through what bids you make.

As a result, bids don’t act just as a claim of what you want the final contract to be, but are also your only way for you and you partner to signal to each other about what your hands look like, using that knowledge to decide what contract to go for. There’s a whole host of bidding conventions that assign a meaning to each bid you can make in each situation, running the gamut from natural systems (where each bid also acts as a reasonable possible contract) to artificial systems (where many bids are not intended to become the contract at all, but merely serve as an arbitrary message).

To give you an example of the latter kind, under the Blackwood convention, a bid of 4NT (No Trump) doesn’t mean you think your partnership can take 10 tricks and not have a trump suit. Instead, it tells your partner you think your partnership can pull off a slam (a 6-level contract, taking all but one trick), and that you want him to tell you how many aces are in his hand, by bidding 5♣ if he has zero or four aces, 5 if he has one, 5 if he has two, and 5♠ if he has three; then you might bid 5NT to ask for how many kings are in his hand in a similar fashion, or otherwise bid the contract you actually want.

Now, your first thought might be that the bids you and your partner make act as a sort of covert channel, or at the very least a private one, and that you wouldn’t want your opponents to know what bidding convention your partnership is using. However, in bridge you are required to tell your opponents what your bidding convention is, and they can even ask your partner what your last bid means! I know, this is rife with pre-9/11 thinking, but apparently old ladies hate America and don’t care if bin Laden knows they have a fit for spades but few good honors in the side suits.

On top of that, there’s only at most 36 possible bids you can make at any point, which gives you all of 5.17 bits of information (rounding up) you can pass. And since this is an auction after all, bids have to keep going up — you can’t bid 2♣ after someone’s already bid 2♠ or 3♣. That further constrains how much detail you can effectively pass, since your bid must be no higher than the contract you will eventually try to establish. If you want to make 7NT signal “my hand ain’t worth expletive”, well, don’t expect to get many points. Conversely, making a high bid early on can effectively jam your opponents’ communications by taking away some of their maneuvering room.

So, bridge is very much a game of exploting small amounts of information to deduce what each player’s hand looks like, both to inform your bidding and what cards you play in each trick. And since one of the players in the partnership that wins the auction puts his entire hand face-up and has his partner play both that hand and his own, knowing how suits and high cards are distributed between the two hands you can’t see can be very helpful.

It seems that a computer player should be able to best a human because a computer could more fully exploit the information revealed during play. The computer after all has megabytes of memory, whereas the human is constrained by short-term memory and mnemonic tricks.

The computer players currently implemented for Old Lady do none of this, not even bothering to look at the face-up hand at all.

Of course, that leaves open the question of just how to program the computer to collect and use this information, given factors such as how the meanings of different bids change depending on context, and how few bids convey very precise information, and the thresholds for making one bid versus another can be fuzzied given confounding factors that may or may not be known by the other players. Also, ideally Old Lady would support many different conventions, so they should be readily swappable at run time.

The best approach to take for now is probably to focus on a single bidding convention and hard-code it in, and hope that the logic that would be general to most conventions will make itself apparent. There’ll be a lot of conditionals unless some natural way to express a convention purely as data makes itself evident. Something like a table of “if I know this, bid that”, which looks something like pattern matching or even reasoning in intuitionistic logic if you squint a bit. (The latter of those is probably overkill, but it’s hard to be certain at this point.)

It probably also doesn’t help that I’m a novice myself at the game. But then again, I don’t seem to have any competition in the open-source world, so my program beats their programs by default! In your face, hypothetical other people!

8 Responses

  1. Once again you have tempted me to seriously revisit my interest in game theory.

  2. KuliniBridge!

  3. I’m disappointed in you, Paul.

    Hello? Genetic algorithms?

  4. Deep Mauve

    /anybody? no?

  5. I got interested in bridge awhile back when I read how much Warren Buffet loved the game. I like his company so much that I bought a (B) share into his company and tried to learn his favorite game. The trouble is like you said, no good bridge open source program.

    Unfortunately, when you mention to family members and friends that you want to play it instead of something like euchre, you immediately get the “uh, that’s for old ladies that read that snippet part of the newspaper — I didn’t want to be associated with it or I didn’t hang around old ladies long enough to learn this black art.” So I never really had a knowledgable group to learn from.

    I think that if somehow you got access to an online bridge playing group that was group and then recorded their moves, you could use a simple Naive Bayes or Neural Network algorithm to get a pretty good result. I wonder if that corpus of data exists somewhere.

    But if you get good and need a partner, I’ll be your dummy anytime.

  6. Jamie: Curses! My secret plan revealed!

    Ryan: Kulinibridge is the new Kulinibox?

    fluffy: Maybe for the 9.x series. I’m partially hoping that implementing a bridge AI will help me learn at least basic strategy. Even with a relatively simple bidding system, there’s a fair bit of information you have to remember. A for-computers-only system could end up being bizarre-looking, but might wring as much information as possible out of the communications channel.

    Eric: *crickets*

    Jeff: Actually, if I asked to play euchre, I’d probably be asked, “uh, what’s that?” Not having grown up in Indiana and all. Though oddly enough, the only time I ever played euchre was in Missouri. Also, bridge turns out to be a more complex game than you’d think would be favored by old ladies. Unless maybe it’s just that none of them are any good. I don’t know; I’ve never played bridge with any.

    I’ve heard from the person who introduced me to bridge a few weeks ago that the bridge areas on Yahoo Games have a surprising paucity of socially inept morons. I haven’t tried to see if that is indeed the case or not.

  7. Once I get back on my Linux box I’ll give the Old Lady bridge a try.

    Hint: Start programming bidding strategy by using simple ol’ Standard American… with Jacoby Transfers, Blackwood Convention, and old fashioned Stayman Convention. That outta be good enough for an American audience.

    Yahoo! bridge is very, very social and quite friendly. Try the social lounge or beginner lounge. Always, always, always congratulate opponents or thank your partner for a job well done.

    For those new to the game, bridgebase is a great way to learn how. Paul, you might want to download the training programs from http://www.acbl.org. A free program called EasyBridge has algorithms that speak clearly what they’re thinking and doing. You should be able to get a lot of ideas from that.

    I can’t wait for the newer versions to come out so I can test Paul’s bridge playing logic.

    Final thought, Paul: don’t forget to display a dialog box exclaiming “That’s good bridge!” when your team gets burned by a trick on a contract.

  8. Oh I forgot… once Old Lady Bridge becomes mature (pun intended), enter it in the World Computer Bridge Championship and see how it does:

    http://www.ny-bridge.com/allevy/computerbridge/index.htm

Comments are closed.