I have written extensive hand evaluation functions designed to be extremely efficient (for high speed monte-carlo's, complete enumerations, and so on) so listen up.

The idea here is to denote your ranks as powers of two.. duece = 1, three = 2, four = 4, five = 8, etc.. this allows you to use a bitwise 'or' operation to combine cards into bitmasks/hashes quite easily.

If you decimate the 7 cards a player has into 4 of these masks (A, B, C, and D.. one for each suit) then you have already greatly simplified the process of hand evaluation as you no longer need to sort the cards or anything.. also combine these 4 using bitwise 'or' into a 5th mask (E) representing all the ranks that appear in the hand.

Some helper functions/tables you will need include a bitwise population count ("how many bits are in this mask?") and a routine to seperate the lowest set bit from the rest of the mask (two outputs.. X and Y, X is the lowest set bit, and Y is the mask with that bit removed) .. These can be calculated using either lookup tables or bitwise manipulations. The tables are quite small (8192 entries) so its a pretty good option.

Also useful is a lookup table for straights. Straights are slow to evaluate without a lookup table. You can check for any straight using mask E, and then if needed, check for straight flushes using the other 4 masks (A, B, C, and D)

The population count of the masks A to D are usefull for finding flushes fast. If Count >= 5 then you have at least a flush.

The population count of the E mask is useful for deciding what types of pairish hands to look for.. if 7 bits are set then you know there arent any duplicate ranks.. if 6 bits are set then you know you need to find a single pair.. if 5 are set then the hand might be two pair or trips.. if 4 are set then it might be 2 pair (three pair really) a full house or quads.. if 3 are set then it might be a full house or quads.. if 2 are set then you definately got quads.. the technique for finding which pairs and so forth consist of several if statements combined with bitwise logic.

On to the most important thing.. ranking the hands high a low..

The 9 "primary" classifications of hands there are:

Straight Flush (8), Quads (7), Full House (6), Flush (5), Straight (4), Trips (3), Two Pair (2), One Pair (1), and No Pair (0).

There are nine of them. You can store this part of the evaluation in the upper 4 bits of the hand evaluation. This leaves the lower bits to store the remaining information necessary to discern precisely what the hand is, keeping in mind that we must be able to sort hands of the same primary type. (we can now already sort hands of different primary types)

There needs to be enough space left in the hand evaluation to store the one pair hands.. the one pair hands use the most space due to the amount of information you need to store.. the pair and 3 kickers. Each of these can be stored in 4 bits each by denoting the ranks as a value between 0 and 12 inclusive. This puts a limit on the evaluations at 20-bits (4-bits for primary, 16-bits for secondary), which luckily fits into a 32-bit integer and also semi-lucky is that each part aligns to a single hex digit.

It might seem like no pair and flush hands have 5 kickers, and they do, but we can use a trick to storing these hands just by using 13 bits of the 16 bits allocated to the secondary classification and simply store the bitmask of the 5 ranks.

Straight Flushes: (hex) 8000x
where x = the rank of the highest card in the straight

Quads: (hex) 700xy
where x = the quaded rank and y = the kicker

Full house: (hex) 600xy
where x = the triped rank and y = the paired rank

Flush: (hex) 5xxxx
where x = the bitbask of the 5 cards that make up the flush

Straight: (hex) 4000x
where x = the rank of the highest card in the straight

Trips: (hex) 30xyz
where x = the triped rank, y and z are the kickers (high to low)

Two pair: (hex) 20xyz
where x = the highest pair, y = the second highest pair, and z = the kicker.

One pair: (hex) 1xyzw
where x = the paired rank, y, z, and w = the kickers (high to low)

No pair: (hex) 0xxxx
where x = the bitmask of the 5 ranks that make up the 5 kickers.


Now given an eval() function which returns said evaluation, you can simply compare the values to see which hand is better (or if they are tied).

Things to keep in mind: Lookup tables are you friend.. a lookup table to detect straights can simply store the hand evaluation for all legal straights and 0 otherwise (0 is not mapped to a legal hand in this system) .. as well a single lookup table for flushes and straight flushes is possible and those too can simply store the hand evaluation

- Rockoon (Joseph Koss)

Hey AP - I found some code which took this/similar approach and had been hoping to step through it when I had the time/strength - your post should help a lot - thanks!

Quote:Original post by stubble
Hey AP - I found some code which took this/similar approach and had been hoping to step through it when I had the time/strength - your post should help a lot - thanks!

Well when you do finally get into the meat of it.. you will find that there is just a little bit of tedious, but simple, coding involved!

Some post-coding advice.. write a hold'em horse race simulator which pits two starting hands against each other and enumerates all possible outcomes and tabulate the results.. you can compare the results with the simulator at http://www.twodimes.net/poker/ which I am quite certain is flawless (it not only agrees with my own simulator, but several other peoples who I have come across over the past few years) .. consider the results of the twodimes.net simulator to be the standard with which to measure your own.

http://www.azillionmonkeys.com/qed/gamealgorithms.html and 'A fast poker hand evaluation'

I don't have anything to add to the whole evaluating hands dealt discussion, but I would like to recommend a method of handling card randomization/dealing that I used in an old poker sim I wrote a while back (it's method of evaluating the hands and picking a winner were rather clumsy and inefficient at the time).

What I did was to actually simulate the shuffling of the deck. I quickly slapped the following tidbit of code together as an example. This would be a perfect candidate to turn into a deck class that handled everything for you...



So you make 52 calls to rand(), and only 52 calls to rand, and you don't have to check if a card dealt is a duplicate or not.

Quote:Original post by jRaskell

*** Source Snippet Removed ***

So you make 52 calls to rand(), and only 52 calls to rand, and you don't have to check if a card dealt is a duplicate or not.

Seems to me that this shuffle will not give a good random distribution. The effects of the problem are very small for a deck of 52 cards but are easily noticed in a deck of 3. A repeated test of this shuffle method on an ordered input deck will show that order matters.

A small modification to this shuffle routine is all thats needed.

While you select a swap card from the entire deck, it should be selecting a swap card from only the remaining unshuffled deck.

So change:

swap = rand() % 52

to

swap = iterate + rand() % (52 - iterate)

In english the shuffle becomes "The next card is chosen randomly from the cards that are left"

- Rockoon (Joseph Koss)

See here for more about shuffling.

Of course, in C++ it is probably best to just make use of std::random_shuffle().

Thanks for the link Zahlman. Interesting read. Good input as well on the randomness of my rather simple routine (to you too, AP). Easy modification as well.