Too Busy For Words - the PaulWay Blog

Fri 17th Dec, 2010

Re-encoding Bridge

In re-reading my article on encoding bridge hands I realised that I made a stupid error in the calculation of how many bits would be needed to encode a complete hand including the order of the cards in each hand. 52 bits would encode not the choice of one in fifty-two cards, but 252 possible choices! The real number of bits required is actually 6*11 (to encode cards 52 - 32 with six bits) + 5*16 + 8*4 + 4*3 + 2*2 + 1 bits, coming to a total of 195 bits. With Base-64 encoding this comes to 33 characters; with Base-85 it comes to 31. So it's not quite as ludicrous as my original calculation, but it's still nearly twice as long as the more optimal coding.

The other thought I had after writing it was just how many hands would benefit from the one-bit-per-card tail handling. This is a bit of a hard one to answer with my level of maths, but basically the first thing to consider here is that the encoding of 104 bits in base 64 does not equal exactly 18 bits, it's about 17.333333 bytes, so we need eighteen characters to encode 104 bits worth of distribution. In order to get less than 17 characters, you'd have to save ten bits - in other words, the first forty-two cards have to be dealt in such a way that the last ten cards are only dealt to two players. You might save even more, because you don't have to use any bits when three players have thirteen cards. Two bits of saving - to get to 17 characters - is probably fairly likely, but ten bits saved is starting to push it; and you can still only get down to 13 chracters anyway...

(I'm not considering unique identifiers which are simply (randomly) assigned numbers or strings given to entries in a database. What I'm wanting is for two programs to be able to decode the same distribution of cards with only the deal identifier being shared.)

Last updated: | path: tech | permanent link to this entry


All posts licensed under the CC-BY-NC license. Author Paul Wayper.


Main index / tbfw/ - © 2004-2016 Paul Wayper
Valid HTML5 Valid CSS!