3

I am working on a simulation of poker and now I have to rank hands effectively:

Every hand is a combination of 5 cards and is represented as an uint64_t.
Every bit from 0 (Ace of Spades), 1 (Ace of Hearts) to 51 (Two of Clubs) indicates if the corresponding card is part (bit == 1) or isn't part (bit == 0) of the hand. The bits from 52 to 63 are always set to zero and don't hold any information.

I already know how I theoretically could generate a table, so that every valid hand can be mapped to rang (represented as uint16_t) between 1 (2,3,4,5,7 - not in the same color) and 7462 (Royal Flush) and all the others to the rang zero.

So a naive lookup table (with the integer value of the card as index) would have an enormous size of 2 bytes * 2^52 >= 9.007 PB.
Most of this memory would be filled with zeros, because almost all uint64_t's from 0 to 2^52-1 are invalid hands and therefor have a rang equal to zero.
The valuable data occupies only 2 bytes * 52!/(47!*5!) = 5.198 MB.

What method can I use for the mapping so that I only have to save the ranks from the valid cards and some overhead (max. 100 MB's) and still don't have to do some expensive search... It should be as fast as possible!

If you have any other ideas, you're welcome! ;)

TacticalCoder
  • 6,275
  • 3
  • 31
  • 39
Robin des Bois
  • 355
  • 2
  • 6
  • 20
  • Try a hash table. Building it will be very slow, so build it once and save in a file. – ugoren Nov 10 '13 at 11:38
  • It's interesting that you think only certain cards are valid. Most poker hands have a rank based on 5 cards (maybe all?)... regardless of what those 5 cards are, _every one of them_ is valid. If your hand is only a pair of twos, the other three cards are still a valid part of the hand (significant only when up against another pair of twos). – mah Nov 10 '13 at 11:39
  • @mah it's not the cards that are valid or not, it's the hands represented by the encoding he describes. As you say, poker hands are usually 5 cards; yet with this encoding you can trivially represent hands of any number of cards from 0 to 52. This is the waste of space the OP is referring to. – JB. Nov 10 '13 at 13:37
  • Small step idea: let the bit flags exist on 16-bit boundaries per suit. bit0-ASpades, bit1-2Spaces .... bit16-AClubs ... This may make bit manipulation between suits easier. – chux - Reinstate Monica Nov 12 '13 at 18:53
  • The bitmap representation is good, but not ideal. I use a simpler 5-integer representation in http://github.com/ojcardlib , and its poker hand evaluator is 5 table lookups, and the tables are only about 1MB. – Lee Daniel Crocker Nov 15 '13 at 15:12
  • http://suffe.cool/poker/evaluator.html – paparazzo Apr 09 '17 at 01:41

5 Answers5

3

You need only a table of 13^5*2, with the extra level of information dictating if all the cards are of the same suit. If for some reason 'heart' outranks 'diamond', you need still at most a table with size of 13^6, as the last piece of information encodes as '0 = no pattern, 1 = all spades, 2 = all hearts, etc.'.

A hash table is probably also a good and fast approach -- Creating a table from nCk(52,5) combinations doesn't take much time (compared to all possible hands). One would, however, need to store 65 bits of information for each entry to store both the key (52 bits) and the rank (13 bits).

Speeding out evaluation of the hand, one first rules out illegal combinations from the mask:
if (popcount(mask) != 5); afterwards once can use enough bits from e.g. crc32(mask), which has instruction level support in i7-architecture at least.

Aki Suihkonen
  • 19,144
  • 1
  • 36
  • 57
  • Actually 64 bits is enough, since one can encode the hand in 51 bits and rank in 13 bits. The last bit for the hand would be implied -- and this would only be needed for hash collision detection. – Aki Suihkonen Sep 02 '16 at 05:22
1

If I understand your scheme correctly, you only need to know that the hamming weight of a particular hand is exactly 5 for it to be a valid hand. See Calculating Hamming Weight in O(1) for information on how to calculate the hamming weight.

From there, it seems you could probably work out the rest on your own. Personally, I'd want to store the result in some persistent memory (if it's available on your platform of choice) so that subsequent runs are quicker since they don't need to generate the index table.

Community
  • 1
  • 1
Chris Browne
  • 1,582
  • 3
  • 15
  • 33
1

This is a good source
Cactus Kev's

For a hand you can take advantage of at most 4 of any suit
4 bits for the rank (0-12) and 2 bits for the suit
6 bits * 5 cards is just 30 bit
Call it 4 bytes
There are only 2598960 hands
Total size a little under 10 mb

paparazzo
  • 44,497
  • 23
  • 105
  • 176
0

A simple implementation that comes to mind would be to change your scheme to a 5-digit number in base 52. The resulting table to hold all of these values would still be larger than necessary, but very simple to implement and it would easily fit into RAM on modern computers.

edit: You could also cut down even more by only storing the rank of each card and an additional flag (e.g., lowest bit) to specify if all cards are of the same suit (i.e., flush is possible). This would then be in base 13 + one bit for the ranking representation. You would presumably then need to store the specific suits of the cards separately to reconstruct the exact hand for display and such.

Arkku
  • 41,011
  • 10
  • 62
  • 84
  • Sorry, that's not an option, since 52^5 = 380204032 > 5.18M + max 100 MB. – Aki Suihkonen Nov 10 '13 at 11:48
  • @AkiSuihkonen Yes, if we take the max 100MB literally, but it doesn't sound like a hard limit and the difference is less than an order of magnitude. (Also I must admit that I interpreted the “max. 100 MB's” as plural, i.e., max. hundred_s_ of megabytes.) – Arkku Nov 10 '13 at 11:55
0

I would represent your hand in a different way: There are only 4 suits = 2bits and only 13 cards = 4 bits for a total of 6 bits * 5 = 30 - so we fit into a 32bit int - we can also force this to always be sorted as per your ordering

[suit 0][suit 1][suit 2][suit 3][suit 4][value 0][value 1][value 2][value 3][value 4]

Then I would use a separate hash for:

  • consectutive values (very small) [mask off the suits]
  • 1 or more multiples (pair, 2 pair, full house) [mask off the suits]
  • suits that are all the same (very small) [mask off the values]

Then use the 3 hashes to calculate your rankings At 5MB you will likely have enough caching issues that will make a bit of math and three small lookups faster

Glenn Teitelbaum
  • 10,108
  • 3
  • 36
  • 80