John Faben's Homepage
  • Home
  • CV
  • Maths
    • Research >
      • Mouse Maze
      • My PhD Thesis
    • Teaching >
      • Counterparty Credit Risk
      • Outreach
  • Bridge
  • Blog
  • HIPE

Counting Bridge Auctions

5/3/2017

2 Comments

 
I played in the Scottish Winter Foursomes bridge competition in January. My team wasn't especially successful, getting knocked out just before the quarter final stage, but mostly stumbling our way into the quarter finals due to the vagaries of the draw. After the competition had finished, I sat in the pub with Jun and discussed various things. One of which, was the fact (which I remember from reading a Peter Winkler book) that there are *a lot* more auctions than deals in Contract Bridge. This is sometimes somewhat surprising to bridge players (and entirely uninteresting to non-bridge players), but it's true.

In order to understand the rest of this, you'll need to know how an auction in Contract Bridge works. I could try to write that out myself, but instead, I've stolen the section from the wikipedia page on bridge (slightly edited to remove the bits that aren't relevant).
 Auction
The dealer opens the auction and can make the first call, and the auction proceeds clockwise. When it is their turn to call, players may pass to the player on their left—and can enter into the bidding later—or bid a contract, specifying the level of their contract and either the trump suit or no trump (the denomination), provided that it is higher than the last bid by any player, including their partner. All bids must be between one (seven tricks) and seven (thirteen tricks). A bid is higher than another bid if either the level is greater (e.g., 2♣ over 1NT) or the denomination is higher, with the order being in ascending order: ♣, ♦, ♥, ♠, and NT (no trump). (note from JF - the suits are in ascending alphabetical order in English. As far as I can tell, this is actually the reason for the order - a lot of people who've been playing bridge for years haven't noticed)
If the last bid was by the opposing partnership, one may double the opponents' bid, increasing the penalties for undertricks, but also increasing the reward for meeting their contract. Doubling does not carry to future bids by the opponents unless future bids are doubled again. A player on the opposing partnership being doubled may also redouble, which increases the penalties and rewards further. Players may not see their partner's hand during the auction, only their own.
The auction ends when, after a player bids, doubles, or redoubles, every other player has passed, in which case the action proceeds to the play; or every player has passed and no bid has been made, in which case, the round is considered to be "passed out" and not played.
How many auctions are there?

Let's start by counting the number of auctions where the final contract is 1♣. There are 28 of them. Any of the 4 players can open 1♣, and then there are 7 ways for the auction to finish - it can be passed out, either of the two opponents can double, and either opener or his partner can redouble. I've written out all 7 possibilities assuming the first player opens 1♣ below: ​
N
E
S
W
N
E
S
W
N
E
1♣
P
P
P
 
 
 
 
 
 
1♣
X
P
P
P
 
 
 
 
 
1♣
P
P
X
P
P
P
 
 
 
1♣
X
XX
P
P
P
 
 
 
 
​1♣
X
P
P
XX
P
P
P
 
 
1♣
P
P
X
XX
P
P
P
 
 
1♣
P
P
X
P
P
XX
P
P
P
So how many auctions are there that end 1♦? For every auction than ends in 1♣, there are 22 that end in 1♦. Why 22? Well, you can replace any of the final three passes in any auction with 1♦, and then there are 7 different ways for it to end, as in the table above, and you also have the option of skipping the 1♣ bid entirely, and replacing it with a bid of 1♦, so that 3*7+1 = 22. There are 35 possible contracts (each of ♣, ♦, ♥, ♠, and NT at each of 7 levels). The same logic applies to all the other bids, so the total number of bridge auctions is: 
28 + 28*22 + 28*22*22 + 28*22*22*22 + .... + 28*22^34
​
= 28*(1 + 22 + ... + 22^34) 
= 28*(1-22^25)/(1-22)
= ​128,745,650,347,030,683,120,231,926,111,609,371,363,122,697,556
In case you don't feel like counting the digits, that's approximately 1.29*10^47. 

For contrast, the other obvious "big number" that appears in bridge combinatorics is the total number of possible deals. This is just 52!/(13!)^4 (if you care about vulnerability, it's a little bigger than that), or:

53,644,737,765,488,792,839,237,440,000.

It should be pretty clear that this number is a lot smaller than the number we have above, but just for confirmation, it is about 5.3*10^28. That is, there are about 2 quintillion times more auctions than their are deals. 
An auction for every deal?

Ok, so there are a lot more auctions than deals. That leads to an obvious question - is there a way of designing a bidding system such that each player always reveals their full hand in the auction? It's not completely obvious that the answer to this question is yes - there are obviously lots of surjective mappings from auctions to deals, but the feature we're looking for is that each player knows what bid to make when it's her turn, which is potentially quite a big restriction. However, it turns out that such a bidding system does exist. 

The first obvious try is this: the player with the first card (let's say the ♣2) opens 1♣. The player with the second card bids 1♦ and so on. If a player ever has multiple missing cards, they should just make the bid corresponding to the highest card they have - e.g., if you have all of the ♣2, ♣3 and ♣4 , but not the ♣5, you open 1♥. This is a promising start, but it only allows us to place 35 of the 52 cards successfully. On the other hand, we haven't even tried to use doubles and redoubles, so there's a lot of room for improvement.

As we discussed above, there are 22 different ways of getting from 1♣ to 1♦. There are 16 different ways of distributing two cards between the four players. Can you use 16 of the 22 effectively to determine the location of two different cards for each level of bidding? It turns out the answer is yes. Here's a couple of different ways of visualising this. We'll assume that North has the ♣2, and that they therefore open 1♣ (unless they also have the next two cards, in which case they skip directly to 1♦. The rest of the auction is determined by who has the next two cards.
♦2\♥2
N
E
S
W
N
1♦
1♣ X P P 1♦
1♣ P P X P P XX P 1♦
1♣ P P X P P XX 1♦
E
1♣ X P P XX 1♦
1♣ 1♦
1♣ X 1♦
1♣ X P 1♦
S
1♣ P P X P P ♦
1♣ X XX 1♦
1♣ P 1♦
1♣ P P X XX P 1♦
W
​1♣ P P X P P XX P P 1♦
1♣ X P P XX P P 1♦
1♣ P P X XX P P 1♦
1♣ P P 1♦
This table is clearly a mapping from the auctions to the possible holdings - each pair of cards is associated with a different auction, and all the auctions are legal. What is not obvious from this table is that at each stage in every auction each player knows which bid to make. That is, you don't want East to have to distinguish between situations where North and South might both still have a card, and she has now way of knowing which. 

It is not obvious, but it is true. Here's a second visualisation, which hopefully makes this clear - this one is effectively a decision tree for each player at each bid. I've used the notation (EW) to mean "East has the first card and West has the second card", and I've written a brief text description of the criterion each player is using to make their bid along the arrows. You can check for any auction that at each step, each player knows what to do. 
Picture
If you follow along any path through the diagram, you can see that at each decision point, each player only has to make decisions based on the cards in her hand.

Further Reading/Sources

Everything in this post is inspired by a discussion in Peter WInker's fascinating book Bridge at the Enigma Club, which also includes discussion of cryptographic bidding systems, and several other interesting bridge-related ephemera (what's the lowest number of high card points you can give NS such that they can make 3NT double dummy? What if you also get to place the EW cards?). I can't find my copy right now, so I'm not sure how much I've blatantly stolen from Winkler, and how much of this is original, but I can say that if you liked this post, you would almost certainly enjoy reading Winkler's book. 

There are several sources online that have the calculation for the number of bridge auctions (here and here). There's also this one by Paul Kuiniewicz, which is the first hit on Google for me, has the wrong answer. This worried me for a while, but I finally figured out it's because he got the number of possible ways an auction can start wrong - you can in fact have 0, 1, 2 or 3 initial passes, and his answer is exactly 3/4 of my answer, so that's all's well with the world. 

Richard Pavlicek, who has one of the most extensive and wide-ranging bridge sites on the web has an interesting discussion of 'Mapping bridge hands to numbers' - ie, he wants a unique deal for each number between 1 and 5.3x10^28, and a relatively low-complexity way of writing down the mapping, which has a similar flavour to the problem of mapping auctions to deals, although gets to a much less intuitive answer. He doesn't appear to have the total number of auctions, although I might have missed it.
2 Comments
Paul Gipson link
7/3/2017 08:53:21

The mapping of deals to numbers is a critical component of hand dealing programs and we've recently seen a major flaw exposed in the American program. Given three hands, it was possible to break the pseudo random number generator and predict the next 23 hands (typically 26 hands in an afternoon) that would be dealt in a usable time (less than 10 minutes).

The rest of the world is in better hands as they use Hans van Staveren's Big Deal algorithm. He explains this at https://sater.home.xs4all.nl/doc.html.

Cheers

Paul

Reply
Gabe link
23/12/2020 17:18:18

Hello mate, great blog

Reply



Leave a Reply.

    John Faben

    This is a blog. It doesn't currently contain anything, but one day it might, in which case this note will be incorrect, unless it changes.

    Archives

    August 2020
    July 2020
    February 2019
    August 2018
    July 2018
    June 2017
    March 2017
    September 2016
    July 2016

    Categories

    All

    RSS Feed

Proudly powered by Weebly