Efficient use of random bits

Factual Questions
1

Hi all. I have a sort-of computer sciencey question, I have no formal training in it, I’m half-remembering stuff from a book by David Mackay on Information Theory that I don’t have to hand at the moment.

I have a file consisting of lots of random bits. I want to simulate dealing lots of Bridge hands, that is, 4 players each getting 13 cards from a standard jokerless pack of playing cards.

Here’s what’s going through my head. The total number of distinct hands (distribution of all the cards amongst four players, where it matters who gets which bunch of 13, but not what order the cards come to an individual player) is 52C13 * 39C13 * 26C13 =~ 5.36e28 (hope the crude ASCII notation is clear). Therefore it should be possible to encode such a hand in 96 bits ( log2 5.36e28 =~ 95.43 ). My two sticking points are:

How does one actually go about mapping the 96-bit sequences onto the hands? I.e. turning ‘1011010101101000…’ into ‘South: Spades AJ95 Hearts 72…’

How does one use the leftover 0.56… of a bit? It suggests to me that slightly half of all possible 96-bit sequences would not correspond to a meaningful hand. Do I just have to discard such sequences and reach for the next 96 bits? Or is there a way of extracting some of that information and then getting the next (say) 8 bits in the file and constructing a hand from that? Bear in mind that I want all hands to be equally probable.

2

I have a CS degree with a programming background, although I never studied information theory. Are you looking for a theoretical abstract answer, or are you actually going to program this? Because looking at your problem statement my approach to programming it would be quite different than your explanation of the theory.

I’m not following your “52C13 * 39C13 * 26C13 =~ 5.36e28” logic/notation, but I would say that each card could be coded in 6 bits. You need to represent 52 values, and 6 bits is the minimum needed to go from 0 to 52 (6 is too many but 5 isnt’ enough). Then 6 x 13 = 78, so you only need 78 bits to encode any hand. I didn’t try to deconstruct how you reached 95.43, so I can’t explain why we get such different answers. Do you mean that you could represent the entire deal, rather than a single hand, with 96 bits?

But in practice we don’t try to minimize the bits; bits are cheap. So I would use a full word to encode each card, and each hand would be an array of 13 words. It’s just easier to program.

That’s why I ask whether you are looking at this as a theoretical question or a practical one.

3

For the benefit of others who might not understand the notation:
52C13 = 52 choose 13 = 635,013,559,600
39C13 = 39 choose 13 = 8,122,425,444
26C13 = 26 choose 13 = 10,400,600

Using 6-bits per card for every card dealt will wind up using 312 bits, not 78, since the goal of the OP was to encode the entire deal of 4 hands.

You can fit the deal into 96 bits but it’s not going to be too easy to decode. The easiest way is to encode just give hands some sequential numbers from 0 to ~5.36e28 based on some sort of strict ordering, but decoding is going to be a major PITA.

4

Well, thinking about this a bit more I’ve kind of worked out a ‘satisfactory’ answer for myself, but thanks for the replies.

I’m looking to program this. Basically I have a big file of random bits. I want to use them to come up with a random unbiased shuffled pack (actually, millions of such shuffles). I’m using the big file (rather than any pseudorandom number generator in my programming language (which I haven’t even decided on yet, except it’ll be one of those with a single-letter name - C, R or J)) under the assumption that I can trust the bits in it to be random. I was somewhat inventive in ensuring their randomness!

Now if I just wanted a random permutation of the 52 cards, there’d be 52! arrangements which is approximately (“=~”) 8.07e67. The reason I get the lower number is because I don’t care what order each player gets their cards in. That cryptic looking expression I wrote, calculates the smaller number (as muttrox explained, ‘choose 13 from 52, then 13 from 39, then 13 from 26’).

The problem, as muttrox identified, is reading in a random 96 bits and then ‘decoding’ them into a given permutation, in such a way that all permutations are equally likely. ‘PITA’ is an understatement. Also, the fact that log2(5.36e28) is about 95.4 bits means that some of the strings of 96 bits won’t correspond to any deal (and if I came up with a scheme that made them do so, the program would be biased in favour of those deals that had more than one bit pattern representing them).

Anyway, I’ve decided it is easier to work with the random permutation of 52 cards than the selection of three lots of 13 without replacement (the fourth hand of course need not be encoded explicitly). That needs more bits, at least 226, but the encoding should be easier. I’ve actually found three methods on the web of implementing the shuffle from the random-bit-stream (enumerating permutations with factoradic numbers, the Fisher-Yates shuffle, and this one (the bit about shuffling, obviously!)). Now I’ve just got to figure out which one is more bit-efficient (bits may be cheap generally, but random bits come at a premium, don’t they?), and I’m good to go.

The objective of all this, btw, is to eventually write the best Bridge playing program evar. This is step 0 of 184693.

Of course, the alternative to all this is to get on with my scarcely started Bioinformatics masters thesis that’s due in about three weeks, but where’s the fun in that? :cool:

5

Sure it’s possible, but you’ll just end up with a pointer to a huge look-up table. You need to look for a coding method that takes up a reasonable amount of space and is not computationally difficult to decode, and 6 bits per card, 78 bits per hand, 312 bits per board, is pretty good.

And 312 bits is only 47 bytes.

So you take your random file and build a hand from each segment of 47 bytes.

6

Google is your friend.

7

WTF? ‘groman’ doesn’t look anything like ‘muttrox’. :o

8

Ah, thanks for that link, it looks like just the thing (plus the rest of that guy’s site will keep me occupied for weeks).

9

Having a “big file of random numbers” is a waste of time and space. Any decent pseudo-random generator will handle the problem for you that will be indistinguishable (in real life) than any scheme you came up with yourself. First rule of programming is don’t re-invent the wheel. Especially something as well trod as generating random numbers.

Now, if you were doing statistical analysis that was looking for very subtle patterns in very large data sets you might want to look at advanced ways of generating random numbers, or how different algorithms will behave, but none of those would justify having a big file of random numbers rather than just generating them on the fly.

10

Tournament hands are now computer dealt, so the problem must have been solved. Why reinvent the wheel (save as an exercise)?

11

I would code this as 52 2-bit fields (104 bits) where each field contained the player to whom the specific card was dealt. Much easier to decode and almost as densely packed. Of course we waste 8 whole bits on those invalid states where each player did not get 13 cards.

12

The easiest is probably to reverse the logic and generate the cards in order (so avoiding the need to check for replicated deals) to the players at random. The players take the form of a 4 by 13 array. My initial thought is to address this indirectly so that once a player has 13 cards their reference can be removed and the randomisation reduced by 1, but this would require to test on each deal just as whether they have 13 cards would and the number of ‘dead hands’ towards the end are not likely to make any real time saving.

13

How inventive?

14

It’s possible that you did have some inventive source of random, but overall in my experience, inventive attempts to make things random work about as well as inventive perpetual motion machines.

Out of curiosity, what IS a ‘muttrox’? :slight_smile: