More efficient way to store Playing Cards in bits?

Question

I am currently helping teach a Computer Programming class. (I am in my Senior Year in High School, TA-ing for my Computer Programming teacher.) Right now the students are learning about bit-wise operators, but some more advanced ones are asking me about using bits and bit-wise operations to store data in the bits. So far what we they is pretty simple, but effective giving 50% (give or take 5%) compression rate. We take our playing card, let's say an Eight of Diamonds, and turn it into a 7 bit value 0b1011000. This works for all generic playing cards Ace - King, and all suits, and you can just put the bit (or integer) into a function and you will get a playing card back.

Here is what they have come up with so far.

0b1 SS VVVV

0b1 keeps all the 'playing card turned bits' at a consistent length.

SS is the suit value

VVVV is the card value

Here is how they form their bits

suits = ['Hearts','Diamonds','Spades','Clubs']
ranks = ['Ace','Two','Three','Four','Five','Six','Seven','Eight','Nine','Ten','Jack','Queen','King']

For this lets use the Jack of Diamonds

Step 1. Isolate the Suit and convert into bis. The 'suit bits' are equal to the index number of the suit in binary so Diamonds would be 0b01 or 0b1

Step 2. Shift your suit bits left 4 bits. 0b01 -> 0b010000

Step 3. Isolate the Rank and convert into bits. The 'rank bits' are equal to the index of the number of the suit in binary so Jack (11) would be 0b1011

Step 4. Add your rank bits into your suit bits. 0b010000 + 0b1011 = 0b011011

Step 5. Add your combined rank\suit bits to 0b10000000 to give a consistent length across all values. 0b011011 + 0b1000000 = 0b1011011

In a full deck of cards (All 52 cards no jokers) there are 741 characters in the card names. A full deck of cards converted to bits is stored in 364 bits with 49% compression while still keeping 100% of the data.

I'm wondering if there's any more efficient way to store this data. I'm only in my 2nd year of Computer Programming, and I only have highschool level education, so I wouldn't know very much about this myself.

Here is their code http://repl.it/BA56

Monied

Answer 1

Another approach would be to give each card a number from 1 to 52

It could be interesting to define an order on colors such as the one defined in the Belote card game.

So : 0 = 1 of Clubs 1 = 2 of clubs ... 12 = king of club 13 = 1 of diamonds ... and so on.

It is easy by having an order on colors to map any number from 1 to 52 to a card.

Finally you only need number from 1 to 52 to represent the whole card game. That is number from '000000' to '110001' that is only 6 bit by card.

In term of size it is equivalent to the system you use, and I think you cannot reduce it more than 6bit by card.

Yielding

Answer 2

If you order the cards 2c,2d,2h,2s,3c,3d,3h,3s...Ac,Ad,Ah,As, then you can treat them simply as integers from 0 to 51, AND as bit-fields, because the suit becomes the two low-order bits. This also makes comparison by rank faster because you don't have to separate ranks to compare them (i.e., "rank > 10" just becomes "card > 35"). It also makes it simple to use the numbers in lookup tables. I have found this to be the most efficient general-purpose representation, and the one I use in my simulation library.

Emmerie

Answer 3

There are a couple ways you can reduce it further than six bits per card. First, enumerate your cards with a system like the other answers mentioned, like:

import itertools

suits = ['Hearts','Diamonds','Spades','Clubs']
ranks = ['Ace','Two','Three','Four','Five','Six','Seven','Eight','Nine','Ten','Jack','Queen','King']
cards = list(itertools.product(ranks, suits))

Any card is now representable as an index into the cards list, which requires enough bits to store a value in the range 0 to len(cards), calculable like:

from math import ceil, log2

def bits_for_index(sequence):
    return ceil(log2(len(sequence)))

So, bits_for_index(cards) returns 6.

But you can observe that for an ordering of the deck, after you choose each card, there is one less possibility for the next card (e.g., no shuffle will contain the Ace of Hearts twice). If you generate a shuffle by selecting a card from your ordering, deleting that card from your list of cards, then choosing the next from the remaining cards, the value of bits_for_index(cards) will eventually go down from 6 to 5, then 4, 3, 2, and 1.

The total number of bits required for this technique is calculated by sum(map(ceil, map(log2, range(52, 1, -1)))), which ends up being 249. You can print a shuffle and its binary representation with something like the following:

from random import randrange

def ordering(sequence):
    sequence = sequence[:]
    value = 0
    while sequence:
        index = randrange(len(sequence))
        print(sequence.pop(index))
        if sequence:
            value += index
            value <<= bits_for_index(sequence)
    return value

ordering_compressed = ordering(cards)
binary_representation = '{:0249b}'.format(ordering_compressed)
print('Compressed to', len(binary_representation), 'bits:', binary_representation)

To extract the ordering, you'd reverse the process, masking and shifting one bit, then two, then two, then three, and so on, until you have a list of indexes into the total cards list:

def extract_ordering(value, sequence):
    indexes = [0]
    while value:
        indexes.append(0)
        bits = bits_for_index(indexes)
        indexes[-1] = value & ((1 << bits) - 1)
        value >>= bits
    padded = [0] * (len(sequence) - len(indexes))
    indexes.extend(padded)
    sequence = sequence[:]
    for idx in reversed(indexes):
        print(sequence.pop(idx))

Also, you could compress a deck of cards further by enumerating all possible orderings and choosing one, which would require ceil(log2(factorial(len(cards)))) or 226 bits:

def ordering(sequence):
    return randrange(factorial(len(sequence)))

def extract_ordering(value, sequence):
    indexes = []
    digit = 1
    while value:
        indexes.append(value % digit)
        value //= digit
        digit += 1
    sequence = sequence[:]
    while indexes:
        print(sequence.pop(indexes.pop()))
    if sequence:
        print(*sequence, sep='\n')

This solution doesn't have quite so tidy a relationship between the bits in the ordering and each individual card, though. And it likely doesn't port quite so easily to languages without universal Big Integer support in their libraries.

Terylene

Answer 4

Efficiency on what? Storing or computing. There are some valid reasons to encode cards into bits for efficiency purposes but I don't think to represent a card with minimum number of bits is meaningful. Instead the idea of encoding cards into bits should be about evaluating or comparing cards/hands easily.

Then you can use 13 bits for the rank and 4 bits for the suit in total 17 bits such as

0b10000000000001000 (65544): Ace of Spades
  \___________/\__/
      rank     suit

whereas

0b00000000000010001 (17)   : 2 of Clubs
  \___________/\__/
      rank     suit

Now they already naturally encoded with an ordered value according to their rank and suit. All you need is to establish a circular ordering relationship so that an Ace is considered smaller than 2 if a Poker hand is checked for Straight. I am also pretty sure that starting from this data type one can come up with interesting bitwise ideas to evaluate hands.

I also know that there might be some people suggesting similar approach to use only 4 bits for the ranks and 2 bits for the suit, in total 6 bits only to represent a card which would also encode an ordering relationship just like the above case. However remember we are after efficiency in computing. Think about the case of checking for a Straight in Poker. You need to check a hand (5 cards) to see if their ranks are consequent. In this data type all you need is to "OR" the cards and check the result against a look up table (map) with only 8 (13-5) keys. When evaluating a hand you always have to check for a Straight and this will be a huge advantage since it doesn't involve sorting.

Hynda