Too Busy For Words - the PaulWay Blog

I was reading the newspaper the other day and I idly scanned over the section on analysis of bridge hands. It started by saying this was an analysis of 691 different plays on the same hand and went on to talk about a website that stored these different hands, played in tournaments, along with commentaries, scores achieved, and so forth. In a standard tournament of duplicate bridge each table's cards are shuffled once, then played in front of the player rather than mixed in the centre. At the end of the game each hand is put back into a tray and taken to the next table, and the players move around as well, so that by the end of the tournament each pair has played each hand against each other pair (for an odd number of tables and using the standard Mitchell rotation method.)

As a programmer, of course, my first reaction was "Hmmm, how would I represent a hand of bridge?" It would have to be easily identifiable - i.e. a particular deal should have a representation that can be quickly differentiated from another - and human-readable (i.e. relatively short and consisting entirely of plain characters). The first approximation was to start with the cards for North and, one by one, enumerate them. So North's hand would use 52 + 51 + 50 + ... 40 bits, then East's would use 39 ... 27 bits, and so forth. Thanks to Euler we know this would be 53*52/2 or a total of 1378 bits; encoding in base 64 gives 230 characters.

Then I realised I could do better - because this encoding also remembers order as well as position; we don't need to know which order North keeps the cards in her hand in, we only need to know what cards are in it. So instead we can imagine starting with an ordered deck - any ordering will do so long as everyone uses it. Then for each card we remember which of the four players it got dealt to. This gives two bits per card, or 13 bytes per hand - with base 64 encoding this gives 18 characters. Much easier!

(I then got side-tracked with the idea of making a small robotic dealer that would take an ordered deck and distribute it amongst the players according to the deal ID. But even smarter would be a robotic dealer that took a deck in any order and distributed it. The deck would be put in a hopper and each card in turn would be pulled across a scanner. The dealer would then work out which player that card went to from the hand ID and push that card toward that player. It could also fairly easily detect whether there were missing cards, erroneous cards like jokers, or duplicates in the process. But that's a project for another time.)

(And it would be possible to shave a couple of bits off the 52 bits - when two players have thirteen cards you need only store one bit to determine which of the two remaining player each card goes to. But only a relatively small number of hands that have been shuffled and dealt in a fair, random manner will have this happen, and it would make the code more complex and the display less regular for a minimal saving.)