Algorithms for testing a poker hand for a straight draw (4 to a straight)?

Question

I'm in the throes of writing a poker evaluation library for fun and am looking to add the ability to test for draws (open ended, gutshot) for a given set of cards.

Just wondering what the "state of the art" is for this? I'm trying to keep my memory footprint reasonable, so the idea of using a look up table doesn't sit well but could be a necessary evil.

My current plan is along the lines of:

• subtract the lowest rank from the rank of all cards in the set.
• look to see if certain sequence i.e.: 0,1,2,3 or 1,2,3,4 (for OESDs) is a subset of the modified collection.

I'm hoping to do better complexity wise, as 7 card or 9 card sets will grind things to a halt using my approach.

Any input and/or better ideas would be appreciated.

Answer 1

The fastest approach probably to assign a bit mask for each card rank (e.g. deuce=1, three=2, four=4, five=8, six=16, seven=32, eight=64, nine=128, ten=256, jack=512, queen=1024, king=2048, ace=4096), and OR together the mask values of all the cards in the hand. Then use an 8192-element lookup table to indicate whether the hand is a straight, an open-ender, a gut-shot, or a nothing of significance (one could also include the various types of backdoor straight draw without affecting execution time).

Incidentally, using different bitmask values, one can quickly detect other useful hands like two-of-a-kind, three-of-a-kind, etc. If one has 64-bit integer math available, use the cube of the indicated bit masks above (so deuce=1, three=8, etc. up to ace=2^36) and add together the values of the cards. If the result, and'ed with 04444444444444 (octal) is non-zero, the hand is a four-of-a kind. Otherwise, if adding plus 01111111111111, and and'ing with 04444444444444 yields non-zero, the hand is a three-of-a-kind or full-house. Otherwise, if the result, and'ed with 02222222222222 is non-zero, the hand is either a pair or two-pair. To see if a hand contains two or more pairs, 'and' the hand value with 02222222222222, and save that value. Subtract 1, and 'and' the result with the saved value. If non-zero, the hand contains at least two pairs (so if it contains a three-of-a-kind, it's a full house; otherwise it's two-pair).

As a parting note, the computation done to check for a straight will also let you determine quickly how many different ranks of card are in the hand. If there are N cards and N different ranks, the hand cannot contain any pairs or better (but might contain a straight or flush, of course). If there are N-1 different ranks, the hand contains precisely one pair. Only if there are fewer different ranks must one use more sophisticated logic (if there are N-2, the hand could be two-pair or three-of-a-kind; if N-3 or fewer, the hand could be a "three-pair" (scores as two-pair), full house, or four-of-a-kind).

One more thing: if you can't manage an 8192-element lookup table, you could use a 512-element lookup table. Compute the bitmask as above, and then do lookups on array[bitmask & 511] and array[bitmask >> 4], and OR the results. Any legitimate straight or draw will register on one or other lookup. Note that this won't directly give you the number of different ranks (since cards six through ten will get counted in both lookups) but one more lookup to the same array (using array[bitmask >> 9]) would count just the jacks through aces.