## How many bridge auctions are possible?

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^{35}.

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^{46}, 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^{28}, or exactly 53,644,737,765,488,792,839,237,440,000.]

## 3 Responses

Sounds like you’re having trouble getting Old Lady to play Bridge. Maybe run it through Wallace, and it can learn to play that way? I’m sure it’s really easy to implement.

Kuliniewtorics!

Ryan:

I don’t think Wallace would actually make a dent here. As Noam Elkies once said, “You can’t just get a bigger computer, you have to think harder.”

But, since you made that referential suggestion, I’m taking the opportunity to make this one:

“All you have to do is add some $\Gamma_{0} (M)$ structure and just run through your argument and it still works, and that gives everything you need.”

Ryan: While such a scheme could in principle invent some crazy bidding system, it would bear no resemblance to anything people would actually want to play.