Paul Kuliniewicz

Old Lady’s bidding logic is based on constraint logic programming over finite domains. Old Lady starts off with a set of variables that describe which cards are in each player’s hand. Each bid is used to constrain the possible values of the variables — for example, if a player opens the bidding with 1♠, that means his hand has at least 13 points and at least 5 spades. As more and more constraints are added, more information is known about each hand’s contents, since there are fewer and fewer possible assignments of variables that satisfy all constraints.

More specifically, each hand is described by 52 variables, one for each card in the deck. Each variable can be either 0 or 1. Naturally, 0 means the card is not in the hand, and 1 means it is. Even more specifically, the code looks like this:

For convenience, the 52 variables are partitioned into four lists, one for each suit. Note that one constraint is already imposed here: the sum of the 52 variables must be exactly 13. Why? Because each player has 13 cards.

Of course, in one deal of bridge, there are four hands, and there’s the additional constraint that each card is in exactly one hand. The following code initializes each hand’s variables and then applies this no-overlap constraint:

Of course, one of the four hands’ contents are known, so the next step is to set the appropriate 13 variables to 1. Immediately, the constraint handling sets the other 39 variables for that hand to 0, as well as the variables for other hands that correspond to those 13 cards. The reasons should be obvious, but already it’s clear that those cross-hand constraints show how learning about one hand tells us something about the other three hands as well.

Why define the variables in this way? Because it makes lots of the common constraints used to choose and interpret bids easy to define. For example, checking the number of cards in a particular suit is easy: just add those 13 variables together:

In the above fragment, suit_sublist does exactly what you might think: it unifies SuitedCards with the list of 13 variables for the given Suit.

High card points are slightly more complex, but also fall to a very simple constraint like that. In high card points, each ace is worth 4, each king is worth 3, each queen is worth 2, and each jack is worth 1. The following code checks the high card points in a hand, either within a single suit or across all suits combined:

Not all the ways to evaluate a hand are quite so simple, however. For example, no trump bids often require the hand to be balanced across the four suits. In particular, “balanced” means 4-3-3-3, 4-4-3-2, or 5-3-3-2 distribution, where it doesn’t matter which suit has which length.

There’s no apparent way to write an algebraic expression to define what “balanced” means, but fortunately the finite domain constraint logic programming library has a few more tools we can use. We can give it a list of constraint variables and a list of possible assignments to those variables. For example, to force a 4-3-3-3 distribution, we could constrain [Spades, Hearts, Diamonds, Clubs] to be one of [4, 3, 3, 3], [3, 4, 3, 3], [3, 3, 4, 3], or [3, 3, 3, 4].

Naturally, we don’t want to have to list each possible order ourselves, so we can write a little code to give us the list of all possible permutations, with no duplicates:

With that, we can write code to take a list of desired distributions, find all permutations of each one, and constrain the lengths of the suits to match one of those possibilities:

And now defining what a balanced hand means is easy:

Note that - only means subtraction is certain contexts in Prolog. Any other time, it’s just another way to join terms together into a larger term. Prolog interprets A-B-C-D the exact same way as -(-(-(A, B), C), D). It just so happens that A-B-C-D matches conventional bridge notation for what a hand distribution looks like, making the code easier to read.

Another slightly tricky way to look at a hand is to count quick tricks. As the name suggests, this measures how many tricks the hand could easily take. Quick tricks within a suit are defined thusly:

• ace and king = 2 quick tricks
• ace and queen = 1.5 quick tricks
• ace = 1 quick trick
• king and queen = 1 quick trick
• king and something else = 0.5 quick tricks

Intuitively, quick tricks require having high cards in a suit, and the better your high cards, the more easily you can take a couple tricks quickly before your opponents can trump you. Again, there’s no algebraic way to define quick tricks, but we can take advantage of reifiable constraints. In other words, we can treat the truth or falseness of a constraint as its own variable, and compare it to other variables with logical operators like “and“, “or“, and “if and only if“. It’s a little ugly, but it’s not too difficult to specify all the possibilities for quick tricks in a single suit, and a way to add them together to get the quick tricks for an entire hand:

Note that since the variables I’m using must be integers, I “cheat” by measuring quick tricks in units of 0.5, so that for example ace-king is 4 demi quick tricks. Converting to plain old quick tricks is just a matter of dividing by 2.

Now for the tricky one. When you’re considering making an preemptive opening bid, you look at the number of tricks you expect your hand to take if trumps are in your long suit. We’re interested in all tricks, not just the quick ones. How exactly do you define that?

That’s a good question, actually. The book I’m following doesn’t give any guidance beyond offering a few examples. The implication is that there’s a judgment call based on how good your suits look, with some leeway depending on how optimistic or pessimistic you are. As Justice Potter Stewart might have observed if he played bridge, you can’t define how to count tricks in your hand, but you know it when you see it.

Needless to say, that isn’t much to go off of when you’re writing a computer program to do it.

The best I could come up with is the following heuristic. I won’t paste the code, since it’s a bit long and you’re probably tired of seeing Prolog if you haven’t stopped reading already, but the idea is to do this for each suit in your hand:

1. Make a list of the cards in your hand and a list of the cards not in your hand.
2. Assume the cards not in your hand are split evenly between the two opponents.
3. Simulate trying to win tricks with your hand. Play your highest card. If the opponents can beat it, they play their highest card and their lowest card, and you lose the trick. Otherwise, they play their lowest two cards, and you win the trick.
4. Repeat until either you or your opponents run out of cards.
5. If you still have cards, win one trick for each card you have left.
6. To make the heuristic a bit less pessimistic, if you started with at least 7 cards and lost more than 3 tricks, add one to your count of won tricks, guessing that your opponents won’t be able to play perfectly.

I’m not saying this is the right way to do it, but it seems to work well enough. At least, its results match the examples I’ve come across in the book so far, which must count for something.

The big problem with it, however, is that it only works in one direction. Everything else works both ways. For example, with suit_length, if you know the length of a suit, you can constrain the variables for that suit. With demi_quick_tricks, if you know a suit has 2 quick tricks in it, you know the hand has the ace and king. And so on.

But here, you need to know exactly what cards your hand has. You can’t go the other way: given the number of tricks, constrain what the hand could possibly be. Even worse, in my initial implementation, instead of failing outright when trying to go the other way, it would enumerate over all possible hands looking for one that matched the number of tricks. Given (39 choose 13) = 8,122,425,444 possible hands the player could have, that doesn’t terminate in anything even remotely approximating a reasonable time.

For the time being, I punt on this problem. My code checks which direction the count-tricks rule is being used, and if it’s in the backwards direction, it does nothing. Good enough for now, but that’ll have to be fixed eventually.

Unfortunately, the only algorithm I can think of to count the tricks in a suit is to exhaustively enumerate all 2¹³ = 8,192 possibilities, count the tricks in each, and use that as a lookup table. It’d be a pretty big lookup table, but not unreasonably so, so it might actually work in practice, especially if I can precompute it once on startup. At least, no better alternatives suggest themselves, so this might be the way I end up going.

Feel free to offer your own suggestions, if only for a better trick-counting heuristic.

As you can see in the repository’s feed over on the right, development of Old Lady continues. I’m at a good point to talk a bit about its current status at a higher level, for those of you not checking each diff to see what’s happening with each checkin.

Thus far I’ve been going through the introductory bridge book I bought, implementing its bidding system (a simplified version of Standard American, though the book never calls it that) along the way. The most recent commit as of this writing more or less finishes Chapter 6. With that, the computer can open bidding at the 1 level, handle a 1NT opening essentially all the way through, and get through the first four bids for other 1-level openings.

Well, mostly. There’s lots of cases that wind up in the “todo” state, the catch-all for parts I haven’t figured out or gotten to in the book yet, but where more bidding might need to happen. As a result, the computer can get through most of the bidding, but then not know what to do when it comes times to seal the deal and pick a final contract.

Thus far, the decision logic has been based on the contents of the player’s hand and the bidding history. It doesn’t look at the information it’s derived about other hands from the bidding history. In other words, if it’s choosing a response to partner’s 1♠ opening bid, it will look at “partner bid 1♠” and not “I know partner definitely has at least 5 spades and 13-22 points”. This works fine early on, but becomes a pain after a few rounds of bidding, thanks to combinatorial explosion. Late-auction bids will probably need to take this latter route, when a fairly good picture of partner’s hand should be available, and it can start making decisions like “which suits do partner and I have at least 8 cards in together, and do we have enough points for game?”

There’s several more chapters on bidding I haven’t implemented yet. In the short term, I’ll work on those and leave the aforementioned loose ends for later. The next chapters are:

• Opening bids at the 2-level or higher, and the bids that come after them. The decision logic here needs to consider the vulnerability of the partnerships, which is information the Prolog code doesn’t (yet) have access to.
• Bidding slams and grand slams. Right now, the highest bidding the computer will ever try to go to is game.
• Overcalls and takeout doubles; and the following chapter on competitive auctions. Right now, the computer gives up on bidding as soon as the other partnership bids anything. You might think that’s an easy way to stop the enemy computer plays from ever reaching a contract, but keep in mind that your partner also stops bidding! Not good.

After that, of course, is implementing the code for playing tricks. Right now a pretty dumb Python AI is there that doesn’t take advantage of any information learned from the auction or what cards have been played. The whole point of writing the bidding code in Python is to provide that information.

When all that is done, the computer players should be roughly as good as a beginner who’s been practicing, at which point you could actually consider Old Lady playable.

There’s lots of other features I’d like to add once I reach that point:

• Making the code much faster. There are cases where the computer will spend a very noticeable and excessive amount of time “thinking”. A lot of the code is definitely sub-optimal, but it’s too early to start optimizing yet.
• Support for other bidding systems. Standard American is just one of the ones out there, after all.
• Support for having each partnership use different bidding systems.
• Hints and other help for players who don’t know how to play bridge very well. This would include being able to explain the meaning behind bids and cards played.

It might be useful to write a domain-specific language for bidding systems. The closer they can be written in a way that matches how a person thinks of them, the better. That would also make it much easier to add help information for each bid. Ideally, the implementation in the DSL would be the help information for the bid.

But let’s finish implementing the basics before I start with any of that.

Implementing the bidding logic in Old Lady has become a real slog. Each new bid branches the decision tree even more, and each chunk of decision logic only applies to a handful of nodes in the tree. Right now I’m at the point where each check-in of a new set of code only applies to a fairly narrow case that can arise during the auction, but all those annoying little cases must be implemented.

It doesn’t take long until you start to wonder, just how many possible auctions are there in a round of bridge anyway?

As you’d probably guess even if you don’t play bridge, an auction is a sequence of bids. The ultimate goal of the auction is to arrive at a contract that one partnership will try to meet by taking tricks. (A secondary yet very important goal is to communicate with your partner through the bids you make what your hand looks like.) Ignoring whatever bidding system the players might be using, the rules of bridge constrain what the possible sequences of bids are.

While it’s theoretically possible to exhaustively enumerate all possible auctions, since we want to answer the question before we all die of old age, let’s use a little math to count faster.

The backbone of the auction are the bids that specify a possible contract. A contract is a rank (1 to 7) paired with either a suit (♣, ♦ ♥, or ♠) or no-trump (NT). That gives 7 x 5 = 35 possible contracts.

Contracts must be bid in ascending order, with the denominations ordered ♣ < ♦ < ♥ < ♠ < NT. For example, once 2♥ is bid, nobody can bid 2♣ or 1♠.

If we just look at the contracts that are bid during an auction, this means we don’t have to worry about the ordering of the contracts that are bid: the rules force one single possible ordering. Each contract may or may not be bid during the auction, for a total number of “backbones” of 2³⁵.

While that’s a pretty big number already (over 34 billion), we’re not even close to finished, since there’s plenty of other bids that don’t try to name a contract.

First, to get it out of the way, there is exactly one possible auction where no contracts are bid: all four players pass. We’ll ignore this special case for the time being and assume at least one contract is being bid in the auction.

Before the first contract is bid, up to three consecutive players may pass. We’ll call this series of passes at the beginning of the auction the “prelude”. There are 4 possible preludes in a non-trivial auction: no passes, one pass, two passes, and three passes.

Aside from passing, other possible bids are doubles and redoubles. A double can be bid by one of the opposing players after a contract is bid; it roughly means “there’s no way you’re going to make that contract”. A redouble can be bid after the other partnership bids double; it roughly means “wanna bet?”

Between two consecutive contracts in an auction is what we’ll call an “interlude”. There are a few things that can happen here:

• Zero, one, or two players can pass.
• The opposing partnership can double the contract, with possible passes before and after.
• The opposing partnership can double the contract, and the original partnership can redouble it. Again, passes may occur before, after, and in between these bids.

Counting how many ways these three cases are possible:

• If the contract is not doubled, there are 3 possibilities: no passes, one pass, or two passes.
• If the contract is doubled but not redoubled, there are 6 possibilities: either zero or two passes, then the double, then zero to two passes. 2 x 1 x 3 = 6.
• If the contract is doubled and redoubled, there are 12 possibilities: either zero or two passes, then the double, then zero or two more passes, then the redouble, then finally zero to two passes. 2 x 1 x 2 x 1 x 3 = 12.

All together, there are 3 + 6 + 12 = 21 possible interludes between each consecutive pair of contracts in the auction.

Finally, bidding ends when three consecutive passes are made after a contract is bid. Again, the contract can be doubled or redoubled. By a similar analysis for what we did for the interlude, there are 7 possible “epilogues”: 1 + 2 x 1 x 1 + 2 x 1 x 2 x 1 x 1 = 7. (Same analysis as before, but now the final set of passes must be three, so there are fewer possibilities in each case.)

Now, how to combine all these numbers together? Let’s use our terminology to look at the structure of a few simple auction templates:

• No contracts: pass pass pass pass
• One contract: prologue contract epilogue
• Two contracts: prologue contract interlude contract epilogue
• Three contracts: prologue contract interlude contract interlude contract epilogue

Let’s let i be the number of contracts in our auction. Whenever i > 0, the auction will have one prologue (3 choices), i – 1 interludes (21 choices each), and one epilogue (7 choices). That leaves the number of ways to choose i contracts out of the 35 possible contracts. Luckily, a little elementary combinatorics already gives us a function to compute that: 35 choose i.

So, for any given i > 0, the possible number of auctions with exactly i contracts is:

Which can be simplified a bit to:

Interestingly, if we plug in i = 0 to that formula, it just so happens to return 1, which is the number of auctions with no contracts in them. We don’t need the i > 0 restriction after all.

As a result, the total number of possible auctions in a single deal of bridge is exactly:

Which is roughly 9.7 x 10⁴⁶, or exactly 96,559,237,760,273,012,340,173,944,583,707,028,522,342,023,168.

That’s a lot, though the vast majority of them will never come up in practice. Luckily not all of them require special handing.

[Edit: For comparison, the number of possible ways to deal the cards in bridge in the first place is “only” about 5.4 x 10²⁸, or exactly 53,644,737,765,488,792,839,237,440,000.]

My nefarious ploy of publishing the status of my code repositories has succeeded, as I’ve forced myself to finally sink some time into Old Lady lest anyone see how dusty the code base had gotten. (Playing video games for several hours is only part of the excuse for that.)

I’ve been cranking through the introductory bridge book I bought, implementing its guidelines for bidding in Old Lady. Thus far, the computer players can handle 1NT openings pretty much all the way through, and can respond once to any other 1-level opening bid before they find themselves in a situation they don’t know how to handle.

Here’s a screenshot of the most interesting 1NT bidding I was able to produce while playing it for a little while. North (computer partner) opened 1NT, since he had 15 points and balanced distribution. I (playing South) had 13 points and a long (5+ cards) spade suit, so I replied with 3♠. That reply is forcing to game, requiring North’s next bid to be at least at the game level. (His 1NT opening indicated 15-17 points, plus my 13 points meant we had 28-30 points total, and 26 points is the threshold for bidding game.) North could choose between game in spades or game in no trump, depending on whether our hands had enough spades between us. My 3♠ bid indicated I had at least 5 spades, plus his 3 spades gave us 8 total, which is enough for bidding in spades, so he chose 4♠ as our contract.

For the record, we (meaning I, since North was dummy) did indeed collect our 10 tricks.

The Prolog code that handles the computer players’ bidding works pretty well as far as it’s been implemented, though it runs noticeably slowly. The speed problems will be fixed later. I’ve implemented the bidding code as a state machine. The initial state is “opening”, and the bids made after that determine what the new state is. The state determines which set of rules to use when choosing (or interpreting the meaning of) the next bid.

Specifically, the names of the states just happen to be the names of the rules that implement their initial logic, allowing me to use call/4 to jump into the right section of code. The bidding logic itself is spread across multiple SWI-Prolog modules that keep related states’ implementations together and hide the internal details. For example, one module handles opening bids; another handles bidding after a 1NT opening; a third handles responses to a 1-suit opening; etc.

Key to the bidding code is the large set of unit tests for each module that make sure they’re doing the right thing. The vast majority of these are taken from the quizzes in the aforementioned bridge book. I figure if the self-tests are good enough for me, they’re good enough for Old Lady. Automated testing is essential for Old Lady; because of the randomness in each deal, you can’t just keep playing hands manually until the situation you want to test comes up, and then look to see if the computers behave correctly.

For the adventurous, you can check the latest code out of the repository (bzr get http://www.kuliniewicz.org/oldlady/bzr/oldlady) and try it out. There’s still lots of bidding logic to implement, and the AI for the trick-taking portion of the game is still dumb as rocks, but it is at least playable. The configure script should actually make sure you have everything you need to run the program now.

Wow, it’s been far too long since I’ve posted something here.

Old Lady, my fledgling open-source bridge game, has finally been seeing some updates lately. The main blocker had been me hitting the limits of my knowledge of bridge strategy augmented with the information readily available on the Internet. While Old Lady follows the rules of bridge just fine, it’s absolutely horrid at playing well. And since the computer plays not only your opponents but also your partner, this isn’t as nice as a novice might think.

Anyway, during a recent trip to the library I found an introductory bridge book that does a pretty good job explaining basic bidding and play, along with the rationale behind it. I started implementing its guidance in Old Lady’s Prolog code, but didn’t get very far into it before having to return the book. And since the copy I bought off of Amazon hasn’t arrived yet, things are once again on hold. Briefly, this time.

Old Lady is still pretty much unplayable, but if you’re really curious you can grab the latest code out of its bzr repository at http://www.kuliniewicz.org/oldlady/bzr/oldlady/. At least now the configure script actually checks to make sure you have SWI-Prolog installed, though it still pretty much assumes you have all the modules (both Prolog and Python) installed. That’ll be fixed eventually.

I tentatively plan the next tarball release for when enough of the bidding system is implemented to make at least that phase of the game playable.